Znaleźć współrzędne graniczne z podanego zestawu współrzędnych punktowych?

18

Biorąc pod uwagę zestaw współrzędnych, jak znaleźć współrzędne graniczne.
zestaw współrzędnych <== Rysunek 1
Biorąc pod uwagę współrzędne w powyższym zestawie, w jaki sposób mogę uzyskać współrzędne na czerwonej granicy. Granica to wielokąt, który jest tworzony przez współrzędne wejściowe dla wierzchołków, w taki sposób, że maksymalizuje obszar.

Pracuję nad aplikacją, która wyszukuje nieruchomości w odległości „x” mil od miasta . Mam:

  1. Współrzędne wszystkich właściwości.
  2. Zestaw współrzędnych dla każdego miasta (Mam jedną współrzędną na każdy zamek błyskawiczny. A ponieważ większość miast ma więcej niż jeden zamek błyskawiczny, Każde miasto ma zestaw współrzędnych)

Pytam o maksymalny obszar, dlatego nie wymyśliłem wielokąta takiego jak ten poniżej:

krzywy wielokąt <== Rysunek 2

Potrzebuję algorytmu, aby opracować zestaw współrzędnych dla granicy. Algorytm, który pozwoli mi wymyślić współrzędne graniczne dla rysunku 1 .

Khaja Minhajuddin
źródło
4
Nie, nie duplikat, to jest wypukły kadłub, nie wklęsły
Nicklas Avén
1
Szukasz kodu, odniesień teoretycznych lub rozwiązań w określonych istniejących środowiskach oprogramowania?
WolfOdrade 24.01.11
1
@ Khaja Nie, nie chcesz maksymalizować obszaru, chcesz go zminimalizować wśród wszystkich wypukłych wielokątów zawierających punkty. (Jedynym sposobem na zmaksymalizowanie tego obszaru jest użycie całego świata jako wielokąta zawierającego.)
whuber
1
@ whuber Tak, teraz rozumiem, o co ci chodzi, chcę wypukłego wielokąta o minimalnej powierzchni. Moim ostatecznym celem jest przeprowadzenie wyszukiwania zbliżeniowego. Sposób, w jaki chcemy, aby wyszukiwanie zbliżeniowe działało: W danym mieście (wypukły kadłub), jeśli szukamy domów (każdy dom ma współrzędną) w promieniu „x” mil, powinien dać mi wszystkie domy znajdujące się wewnątrz wypukły kadłub lub znajdują się w ortogonalnej odległości mniejszej niż „x” mili
Khaja Minhajuddin

Odpowiedzi:

21

Istnieje wiele algorytmów do rozwiązania tego problemu ( Wikipedia „Convex_hull_alnodes” ):

  • Pakowanie prezentów, czyli Jarvis March - O (nh): Jeden z najprostszych algorytmów. Ma złożoność czasową O (nh), gdzie n jest liczbą punktów w zestawie, a h jest liczbą punktów w kadłubie. W najgorszym przypadku złożoność wynosi O (n2).
  • Skan Grahama - O (n log n): Nieco bardziej wyrafinowany, ale o wiele bardziej wydajny algorytm. Jeśli punkty są już posortowane według jednej ze współrzędnych lub pod kątem do stałego wektora, algorytm zajmuje O (n) czasu. [ pseudo kod ]
  • QuickHull: Podobnie jak algorytm szybkiego sortowania, ma on oczekiwaną złożoność czasową O (n log n), ale w najgorszym przypadku może ulec degeneracji do O (nh) = O (n2). [ ilustrowany opis ]
  • Dziel i rządź - O (n log n): Ten algorytm ma również zastosowanie do przypadku trójwymiarowego.
  • Łańcuch monotoniczny - O (n log n): wariant skanu Grahama, który sortuje punkty leksykograficznie według ich współrzędnych. Gdy dane wejściowe są już posortowane, algorytm zajmuje czas O (n).
  • Algorytm przyrostowego wypukłego kadłuba - O (n log n)
  • Małżeństwo przed podbiciem - O (n log h): Optymalny algorytm wrażliwy na wyniki.
  • Algorytm Chana - O (n log h): Prostszy optymalny algorytm wrażliwy na wyjście.
podmrok
źródło
Dziękujemy za umieszczenie tych @underdark ... który z nich jest dla ciebie wyborem?
Marin,
3

To, czego chcesz, to wypukły kadłub. W PostGIS jest funkcja (właściwie GEOS), która daje wypukły kadłub, ST_ConvexHull (geometria) .

Na wikipedii jest wiele informacji o wklęsłych kadłubach.

Nicklas Avén
źródło
1

Jeśli chcesz, aby algorytm to zrobił (zamiast pakietów, które mogą to zrobić), pomyślałem, że będziesz musiał triangulować dane; lub w zasadzie zdefiniuj linię od każdego punktu do każdego innego punktu. Następnie, zaczynając od (powiedzmy) punktu o najwyższej wartości Y, prześledź trasę dookoła na zewnątrz, podążając za połączoną linią o najmniejszym zewnętrznym kącie / łożysku.

Możesz przyspieszyć śledzenie, najpierw wyrzucając przecinające się linie. Granica zewnętrzna nie będzie miała skrzyżowań.

btw - FME zrobi to również z transformatorami ConvexHullAccumulator lub ConvexHullReplacer!

Mark Ireland
źródło
1

Jeśli chcesz spojrzeć na istniejący algorytm zaimplementowany w kodzie, NetTopologySuite ma odpowiedni algorytm

Zobacz ConvexHull.cs

Nawiasem mówiąc, NTS i kilka innych bibliotek są zamknięte w fajnym projekcie o nazwie DotSpatial, który można znaleźć tutaj

WolfOdrade
źródło