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

16

Dado un conjunto de coordenadas, ¿Cómo encontramos las coordenadas de los límites?
<==Figura1
Dadaslascoordenadasenelconjuntoanterior,¿Cómopuedoobtenerlascoordenadasenellímiterojo?Ellímiteeselpolígonoformadoporlascoordenadasdeentradaparalosvértices,detalmaneraquemaximizaelárea.

Estoytrabajandoenunaaplicaciónquebuscapropiedadesdentrode'x'millasdeunaciudad.Loquetengoes:

  1. Coordenadasdetodaslaspropiedades.
  2. Unconjuntodecoordenadasparacadaciudad(tengounacoordenadaparacadacódigopostal.Ycomolamayoríadelasciudadestienenmásdeuncódigopostal,cadaciudadtieneunconjuntodecoordenadas)

Larazónporlaquesolicitoeláreamáximaesparaquenotengaunpolígonocomoelquesemuestraacontinuación:

< == Figura 2

Lo que necesito es el algoritmo para establecer el conjunto de coordenadas para el límite. Un algoritmo que me permitirá establecer las coordenadas de los límites para Figura 1 .

    
pregunta Khaja Minhajuddin 24.01.2011 - 17:28

6 respuestas

20

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 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): 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 a un vector fijo, entonces el algoritmo toma tiempo O (n). [ pseudo código ]
  • QuickHull: Al igual que el algoritmo de ordenació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 conquista - O (n log n): este algoritmo también es aplicable al caso tridimensional.
  • Cadena monótona: O (n log n): una variante de la exploración de Graham que clasifica los puntos por lexicografía por sus coordenadas. Cuando la entrada ya está ordenada, el algoritmo lleva tiempo O (n).
  • Algoritmo de casco convexo incremental - O (n log n)
  • Matrimonio antes de la conquista: O (n log h): algoritmo sensible a la salida óptimo.
  • Algoritmo de Chan - O (n log h): algoritmo sensible a la salida óptimo más simple.
respondido por el underdark 25.01.2011 - 19:37
8

1) Casco convexo en GRASS GIS: enlace

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

    
respondido por el Pablo 24.01.2011 - 19:32
3

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

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

    
respondido por el radek 24.01.2011 - 19:25
3

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

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

    
respondido por el Nicklas Avén 24.01.2011 - 18:23
1

Si desea que un algoritmo haga esto (en lugar de los paquetes que pueden hacerlo), creo que debería triangular los datos; o básicamente definir una línea de cada punto a cada 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 / rodamiento exterior más pequeño.

Podrías acelerar el trazado tirando primero las líneas que se cruzan. El límite externo no tendrá intersecciones.

btw - ¡FME también lo hará con los transformadores ConvexHullAccumulator o ConvexHullReplacer!

    
respondido por el Mark Ireland 24.01.2011 - 20:50
1

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

Consulte ConvexHull.cs

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

    
respondido por el WolfOdrade 25.01.2011 - 22:17

Lea otras preguntas en las etiquetas