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

18

Dado un conjunto de coordenadas, ¿Cómo encontramos las coordenadas del límite?
conjunto de coordenadas <== 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:

polígono torcido <== 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 .

Khaja Minhajuddin
fuente
44
No, no duplicado, este es un casco convexo, no cóncavo
Nicklas Avén
1
¿Está buscando código, referencias teóricas o soluciones en entornos de software existentes específicos?
WolfOdrade
1
@ Khaja No, no desea maximizar el área, desea minimizarla entre todos los polígonos convexos que contienen los puntos. (La única manera de maximizar el área es utilizar el mundo entero como el polígono que contiene.)
whuber
1
@whuber Sí, ahora veo lo que quieres decir, quiero un polígono convexo con el área mínima. Mi objetivo final es hacer una búsqueda de proximidad. La forma en que queremos que funcione nuestra búsqueda de proximidad es: en una ciudad determinada (casco convexo), si buscamos casas (cada casa tiene una coordenada) dentro de "x" millas, debería darme todas las casas que están dentro del casco convexo o están a una distancia ortogonal de menos de "x" millas
Khaja Minhajuddin

Respuestas:

21

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.
bajo oscuro
fuente
Gracias por enumerar estos @underdark ... ¿cuál es tu elección?
Marin
3

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.

Nicklas Avén
fuente
1

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!

Mark Ireland
fuente
1

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í

WolfOdrade
fuente