Cómo encontrar el límite de las coordenadas de un determinado conjunto de coordenadas

Question

Dado un conjunto de coordenadas, ¿Cómo podemos encontrar el límite de coordenadas.
<== Figura 1
Dadas las coordenadas en el anterior conjunto, ¿Cómo puedo obtener las coordenadas en el límite de rojo. Límite es el polígono que se forma por la entrada de las coordenadas de los vértices, de tal manera que se maximiza el área.

Editar:

Yo soy lo siento, no era preciso acerca de por qué necesitaba esto. Estoy trabajando en una aplicación que busca en las propiedades dentro de " x " millas de la ciudad. Lo que tengo es:

1. Las coordenadas de todas las propiedades.
2. Un conjunto de coordenadas para cada ciudad (tengo una coordenada para cada postal. Y puesto que la mayoría de las ciudades tienen más de un zip, Cada ciudad cuenta con un conjunto de coordenadas)

La razón por la que estoy pidiendo el área máxima es para que no vienen con un polígono como el siguiente:
<== Figura 2

Lo que necesito es el algoritmo de venir para arriba con el conjunto de coordenadas de la frontera. Un algoritmo que me permita llegar con límite de coordenadas de la Figura 1. Espero que aclare un par de cosas.

Answer 1

Hay muchos algoritmos para resolver este problema (Wikipedia "Convex_hull_algorithms"):

• Envoltura de regalos aka Jarvis de marzo - O(nh): Uno de los algoritmos más simples. Tiene O(nh) tiempo de complejidad, donde n es el número de puntos en el juego, y h es el número de puntos en el casco. En el peor de los casos la complejidad es O(n2).
• Graham scan - O(n log n): un poco más sofisticado, pero mucho más eficiente algoritmo. Si los puntos están ya ordenadas por una de las coordenadas o el ángulo de un vector fijo, entonces el algoritmo toma O(n) tiempo. [pseudo código]
• QuickHull: Como el algoritmo de quicksort, tiene el tiempo de espera complejidad de O(n log n), pero puede degenerar a O(nh) = O(n2) en el peor de los casos. [descripción ilustrada]
• Divide y vencerás - O(n log n): Este algoritmo también es aplicable a las tres dimensiones del caso.
• La monotonía de la cadena - O(n log n): Una variante de Graham scan que ordena los puntos lexicográficamente por sus coordenadas. Cuando la entrada ya está ordenada, la toma de algoritmo O(n) tiempo.
• Incremental convex hull algoritmo O(n log n)
• El matrimonio antes de la conquista - O(n log h): una salida Óptima sensibles algoritmo.
• Chan algoritmo O(n log h): más Simple, una salida óptima sensibles algoritmo .

Answer 2

1)Convex Hull en GRASS GIS: http://grass.fbk.eu/grass64/manuals/html64_user/v.hull.html

2)Convex Hull en Qgis Herramientas Vectoriales (muy fácil de usar):

Answer 3

Lo que quiero es que el Convex hull. En PostGIS no es una función (en realidad GEOS) que le da el Convex hull, ST_ConvexHull(geometría).

En la wikipedia hay una gran cantidad de información acerca de cóncava a los cascos.

Answer 4

Hawth Herramientas para ArcGIS tiene esta funcionalidad. Además de una secuencia de comandos para ArcInfo 10.

También hay convex hull herramienta en QuantumGIS a través de ftools plugin.

Answer 5

Si quieres un algoritmo para hacer esto (en lugar de paquetes que puede hacerlo), a continuación, me gustaría pensar que usted necesita para triangular los datos; o, básicamente, definir una línea desde cada punto a cualquier otro punto. Luego, a partir de (por ejemplo) el punto con el mayor valor Y, traza una ruta alrededor de la parte exterior siguiendo la línea conectada con el menor ángulo exterior de rodamiento.

Usted sería capaz de acelerar el seguimiento de tirar líneas que se intersectan en primer lugar. Los límites externos no tienen intersecciones.

btw - FME va a hacer esto también con el ConvexHullAccumulator o ConvexHullReplacer transformadores!