Trouver les coordonnées des limites à partir d'un ensemble donné de coordonnées ponctuelles?

18

Étant donné un ensemble de coordonnées, comment trouver les coordonnées des limites.
ensemble de coordonnées <== Figure 1
Compte tenu des coordonnées dans l'ensemble ci-dessus, comment puis-je obtenir les coordonnées sur la frontière rouge. La limite est le polygone qui est formé par les coordonnées d'entrée des sommets, de manière à maximiser la zone.

Je travaille sur une application qui recherche des propriétés dans un rayon de 'x' miles d'une ville . Ce que j'ai c'est:

  1. Coordonnées de toutes les propriétés.
  2. Un ensemble de coordonnées pour chaque ville (j'ai une coordonnée pour chaque zip. Et comme la plupart des villes ont plus d'un zip, chaque ville a un ensemble de coordonnées)

La raison pour laquelle je demande la superficie maximale est pour que je ne trouve pas de polygone comme celui ci-dessous:

polygone tordu <== Figure 2

Ce dont j'ai besoin, c'est de l' algorithme pour trouver l'ensemble de coordonnées de la frontière. Un algorithme qui me permettra de trouver des coordonnées de frontière pour la figure 1 .

algorithm polygon-creation vertices convex-hull Khaja Minhajuddin
la source
1
copie possible de la coque concave: définition, algorithmes et solutions pratiques
Ian Turton
4
Non, pas de doublon, c'est une coque convexe, pas concave
Nicklas Avén
1
Vous recherchez du code, des références théoriques ou des solutions dans des environnements logiciels existants spécifiques?
WolfOdrade
1
@Khaja Non, vous ne voulez pas agrandir la zone, vous voulez la minimiser parmi tous les polygones convexes contenant les points. (La seule façon de maximiser la zone est d'utiliser le monde entier comme polygone contenant.)
whuber
1
@whuber Ouais, maintenant je vois ce que tu veux dire, je veux un polygone convexe avec la zone minimale. Mon but ultime est de faire une recherche de proximité. La façon dont nous voulons que notre recherche de proximité fonctionne est la suivante: dans une ville donnée (coque convexe), si nous recherchons des maisons (chaque maison a une coordonnée) dans un rayon de "x" miles, cela devrait me donner toutes les maisons qui sont soit à l'intérieur du coque convexe ou à une distance orthogonale de moins de "x" miles
Khaja Minhajuddin

Réponses:

21

Il existe de nombreux algorithmes pour résoudre ce problème ( Wikipedia "Convex_hull_algorithms" ):

  • Emballage cadeau aka Jarvis mars - O (nh): L'un des algorithmes les plus simples. Il a une complexité temporelle O (nh), où n est le nombre de points dans l'ensemble, et h est le nombre de points dans la coque. Dans le pire des cas, la complexité est O (n2).
  • Balayage de Graham - O (n log n): algorithme légèrement plus sophistiqué, mais beaucoup plus efficace. Si les points sont déjà triés par l'une des coordonnées ou par l'angle d'un vecteur fixe, alors l'algorithme prend le temps O (n). [ pseudo code ]
  • QuickHull: comme l'algorithme de tri rapide, il a la complexité temporelle attendue de O (n log n), mais peut dégénérer en O (nh) = O (n2) dans le pire des cas. [ description illustrée ]
  • Diviser pour mieux régner - O (n log n): cet algorithme est également applicable au cas tridimensionnel.
  • Chaîne monotone - O (n log n): une variante de Graham scan qui trie les points lexicographiquement par leurs coordonnées. Lorsque l'entrée est déjà triée, l'algorithme prend le temps O (n).
  • Algorithme incrémental de coque convexe - O (n log n)
  • Mariage avant la conquête - O (n log h): algorithme optimal sensible à la sortie.
  • Algorithme de Chan - O (n log h): algorithme sensible à la sortie optimal plus simple.
obscur
la source
Merci d'avoir listé ces @underdark ... lequel est votre choix?
Marin
3

Ce que vous voulez, c'est la coque convexe. Dans PostGIS, il existe une fonction (en fait GEOS) qui vous donne la coque convexe, ST_ConvexHull (géométrie) .

Sur wikipedia, il y a beaucoup d'informations sur les coques concaves.

Nicklas Avén
la source
1

Si vous voulez un algorithme pour faire cela (plutôt que des packages qui peuvent le faire), je pense que vous auriez besoin de trianguler les données; ou définir fondamentalement une ligne de chaque point à chaque autre point. Ensuite, en commençant par (disons) le point avec la valeur Y la plus élevée, tracez un itinéraire autour de l'extérieur en suivant la ligne connectée avec le plus petit angle / relèvement extérieur.

Vous seriez en mesure d'accélérer le traçage en jetant d'abord les lignes qui se croisent. La limite externe n'aura pas d'intersections.

btw - FME le fera aussi avec les transformateurs ConvexHullAccumulator ou ConvexHullReplacer!

Mark Ireland
la source
1

Si vous êtes intéressé à regarder un algorithme existant implémenté dans du code, NetTopologySuite dispose d'un algorithme pour le faire

Voir ConvexHull.cs

Soit dit en passant NTS et un tas d'autres bibliothèques sont enveloppés dans un projet cool appelé DotSpatial, trouvé ici

WolfOdrade
la source