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:
- Współrzędne wszystkich właściwości.
- 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 .
algorithm
polygon-creation
vertices
convex-hull
Khaja Minhajuddin
źródło
źródło
Odpowiedzi:
Istnieje wiele algorytmów do rozwiązania tego problemu ( Wikipedia „Convex_hull_alnodes” ):
źródło
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):
źródło
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 .
źródło
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.
źródło
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!
źródło
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
źródło