Ten problem ma wiele ważnych rozwiązań. Jeden z nich działa trochę jak opis, ale zamiast krojenia wielokątów w „losowe” miejsca, możesz to zrobić celowo w sposób zaprojektowany w celu zminimalizowania ilości obliczeń.
Oto podstawowy algorytm. Jego wejściowy składa się z dowolnego kierunku płaszczyzny cyklu, wieloboku P obszaru niezerową, obszar docelowy od zera do powierzchni wielokąta i dodatnią progowej T (w jednostkach powierzchni). Jego celem jest podzielenie P linią prostopadłą do kierunku przeciągnięcia na dwie części, jedną na prawo od linii, a drugą na lewo od linii, tak aby różnica między obszarem prawej ręki a obszarem docelowym a nie była większy niż t .
Niech L będzie dowolną zorientowaną linią prostopadłą do kierunku przeciągnięcia. Zdefiniuj f (L) jako obszar P znajdujący się po prawej stronie L, minus a . W tych terminach zadaniem jest znalezienie zera f . Ponieważ jest mało prawdopodobne, aby f był różniczkowalny, ale ciągły, użyj albo metody bisekcji, metody siecznej , albo - mojej ulubionej - metody Brenta . Wszystkie są proste i gwarantowane połączenie. Użyj t dla tolerancji zbieżności dla argumentu.
to jest to! Zastanówmy się, co należy do tego zakodować. Znalezienie roota jest rutynowe - możesz użyć do tego ogólnego fragmentu kodu - więc praca GIS sprowadza się do kodowania f . Takie postępowanie wymaga
1. Splitting the polygon by a line.
2. Computing the area of the piece(s) to the right of the line.
Obie operacje są realizowane w prawie każdym systemie GIS opartym na wektorze. Jeśli nie, możesz zastąpić linię bardzo dużym prostokątem reprezentującym półpłaszczyznę po prawej stronie linii. Krok 1 staje się
1'. Clip the polygon to the rectangle.
To naprawdę podstawowa operacja.
Aby rozpocząć wyszukiwanie roota, musisz znaleźć przedział, w którym zero f będzie gwarantowane. To proste: rzutuj obwiednię wielokąta („ramkę ograniczającą”) w kierunku przeciągnięcia linii. Projekcja to żądany przedział.
To pytanie ma długą historię. Zaimplementowałem ten algorytm dla ArcView 3.x dawno temu i opisałem go wiele razy na starych forach użytkowników ESRI. Google
Huber podzielona strona wielokąta: forums.esri.com
do dyskusji, łącza do kodu, ulepszeń i odmian (takich jak dzielenie wielokątów na części o pożądanych rozmiarach, które są możliwie jak najbardziej kompaktowe) oraz algorytmy danych rastrowych.
Oto jak wyglądają kontynentalne stany USA (w rzucie równego obszaru) z dolną trzecią częścią każdego stanu zacieniowaną. Najwyraźniej kierunek zamiatania był pionowy.
