¿Encontrar coordenadas de límites a partir de un conjunto dado de coordenadas de puntos?

Dado un conjunto de coordenadas, ¿Cómo encontramos las coordenadas del límite?
<== Figura 1
Dadas las coordenadas en el conjunto anterior, ¿Cómo puedo obtener las coordenadas en el límite rojo? Límite es el polígono que está formado por las coordenadas de entrada para vértices, de tal manera que maximiza el área.

Estoy trabajando en una aplicación que busca propiedades dentro de 'x' millas de una ciudad . Lo que tengo es:

1. Coordenadas de todas las propiedades.
2. Un conjunto de coordenadas para cada ciudad (tengo una coordenada para cada código postal. Y como la mayoría de las ciudades tienen más de un código postal, cada ciudad tiene un conjunto de coordenadas)

La razón por la que solicito el área máxima es para que no se me ocurra un polígono como el siguiente:

<== Figura 2

Lo que necesito es el algoritmo para obtener el conjunto de coordenadas para el límite. Un algoritmo que me permitirá encontrar coordenadas de límites para la Figura 1 .

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

• Envoltura de regalos, también conocida como Jarvis march - O (nh): uno de los algoritmos más simples. Tiene una complejidad de tiempo O (nh), donde n es el número de puntos en el conjunto yh es el número de puntos en el casco. En el peor de los casos, la complejidad es O (n2).
• Escaneo de Graham - O (n log n): Algoritmo ligeramente más sofisticado, pero mucho más eficiente. Si los puntos ya están ordenados por una de las coordenadas o por el ángulo de un vector fijo, entonces el algoritmo tarda O (n) tiempo. [ pseudocódigo ]
• QuickHull: Al igual que el algoritmo de clasificación rápida, tiene la complejidad de tiempo esperada 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 al caso tridimensional.
• Cadena monótona - O (n log n): una variante del escaneo de Graham que ordena los puntos lexicográficamente por sus coordenadas. Cuando la entrada ya está ordenada, el algoritmo tarda O (n) tiempo.
• Algoritmo incremental de casco convexo - O (n log n)
• Matrimonio antes de la conquista - O (n log h): algoritmo óptimo sensible a la salida.
• Algoritmo de Chan - O (n log h): algoritmo óptimo más simple de salida sensible.

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

2) Casco convexo en Qgis Vector Tools (muy fácil de usar):

Hawth's Tools for ArcGIS tiene esto funcionalidad . Además de un script para ArcInfo 10.

También hay una herramienta de casco convexo en QuantumGIS a través del complemento ftools .

Lo que quieres es el casco convexo. En PostGIS hay una función (en realidad GEOS) que te da el casco convexo, ST_ConvexHull (geometría) .

En wikipedia hay mucha información sobre cascos cóncavos.

Si desea que un algoritmo haga esto (en lugar de los paquetes que pueden hacerlo), creo que necesitaría triangular los datos; o básicamente define una línea desde cada punto a cualquier otro punto. Luego, comenzando en (digamos) el punto con el valor Y más alto, trace una ruta alrededor del exterior siguiendo la línea conectada con el ángulo / rumbo exterior más pequeño.

Podría acelerar el trazado tirando primero las líneas de intersección. El límite externo no tendrá intersecciones.

Por cierto, ¡FME también lo hará con los transformadores ConvexHullAccumulator o ConvexHullReplacer!

Si está interesado en ver un algoritmo existente implementado en código, NetTopologySuite tiene un algoritmo para hacer esto

Ver ConvexHull.cs

Por cierto, NTS y ​​un montón de otras bibliotecas están envueltas en un proyecto genial llamado DotSpatial, que se encuentra aquí