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

Biorąc pod uwagę zestaw współrzędnych, jak znaleźć współrzędne graniczne.
<== 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:

<== 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 .

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.

1) Wypukły kadłub w GRASS GIS: http://grass.fbk.eu/grass64/manuals/html64_user/v.hull.html

2) Wypukły kadłub w narzędziach wektorowych Qgis (bardzo łatwy w użyciu):

Narzędzia Hawtha dla ArcGIS mają tę funkcjonalność . Plus skrypt dla ArcInfo 10.

Istnieje również wypukłe narzędzie kadłuba w QuantumGIS poprzez wtyczkę Ftools .

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.

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!

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