Algorytm znajdowania nieregularnych centroidów wielokątów (punkt etykiety)

Muszę znaleźć środek ciężkości (lub punkt etykiety) dla wielokątów o nieregularnym kształcie w Mapach Google. Pokazuję InfoWindows dla paczek i potrzebuję miejsca do zakotwiczenia InfoWindow, które na pewno będzie na powierzchni. Zobacz zdjęcia poniżej.

W rzeczywistości nie potrzebuję niczego konkretnego w Mapach Google, tylko szukam pomysłu, jak automatycznie znaleźć ten punkt.

Moim pierwszym pomysłem było znalezienie „fałszywego” centroidu, biorąc średnie łaty i lngs i losowo umieszczając stamtąd punkty, aż znajdę taki, który przecina wielokąt. Mam już kod punktu w wielokącie. To po prostu wydaje mi się okropnie „hacky”.

Powinienem zauważyć, że nie mam dostępu do żadnego kodu po stronie serwera, który wyprowadza geometrię, więc nie mogę zrobić czegoś takiego jak ST_PointOnSurface (the_geom).

Szybkie i brudne: jeśli „fałszywego” środka masy nie ma w wielokącie, użyj najbliższego wierzchołka do tego punktu.

Możesz na to spojrzeć: http://github.com/tparkin/Google-Maps-Point-in-Polygon

Wygląda na to, że korzysta z algorytmu Ray Casting, który powinien pasować do prezentowanego przypadku.

Tutaj jest post na blogu. http://appdelegateinc.com/blog/2010/05/16/point-in-polygon-checking/

(Starszy) algorytm ESRI oblicza środek masy i po przetestowaniu go pod kątem włączenia do wielokąta przesuwa go w poziomie, jeśli to konieczne, aż znajdzie się w wielokącie. (Można to zrobić na wiele sposobów, w zależności od podstawowych operacji dostępnych w środowisku programistycznym.) Zazwyczaj tworzy to punkty etykiety dość blisko wizualnego środka wielokąta: wypróbuj to na ilustracji.

Rozwiązałem swój problem, rozszerzając popularny kod epoli z http://econym.org.uk/gmap . Zasadniczo skończyłem na tym, że:

• Utwórz serię promieni, które zaczynają się od „fałszywej centroidy” i rozciągają się na każdy narożnik i bok (łącznie 8)
• Stopniowo utwórz punkt 10,20,30 ... procent w dół każdego promienia i sprawdź, czy ten punkt znajduje się w naszym oryginalnym wielokącie

Rozszerzony kod epoli poniżej:

google.maps.Polygon.prototype.Centroid = function() {
var p = this;
var b = this.Bounds();
var c = new google.maps.LatLng((b.getSouthWest().lat()+b.getNorthEast().lat())/2,(b.getSouthWest().lng()+b.getNorthEast().lng())/2);
if (!p.Contains(c)){
    var fc = c; //False Centroid
    var percentages = [0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9]; //We'll check every 10% down each ray and see if we're inside our polygon
    var rays = [
        new google.maps.Polyline({path:[fc,new google.maps.LatLng(b.getNorthEast().lat(),fc.lng())]}),
        new google.maps.Polyline({path:[fc,new google.maps.LatLng(fc.lat(),b.getNorthEast().lng())]}),
        new google.maps.Polyline({path:[fc,new google.maps.LatLng(b.getSouthWest().lat(),fc.lng())]}),
        new google.maps.Polyline({path:[fc,new google.maps.LatLng(fc.lat(),b.getSouthWest().lng())]}),
        new google.maps.Polyline({path:[fc,b.getNorthEast()]}),
        new google.maps.Polyline({path:[fc,new google.maps.LatLng(b.getSouthWest().lat(),b.getNorthEast().lng())]}),
        new google.maps.Polyline({path:[fc,b.getSouthWest()]}),
        new google.maps.Polyline({path:[fc,new google.maps.LatLng(b.getNorthEast().lat(),b.getSouthWest().lng())]})
    ];
    var lp;
    for (var i=0;i<percentages.length;i++){
        var percent = percentages[i];
        for (var j=0;j<rays.length;j++){
            var ray = rays[j];
            var tp = ray.GetPointAtDistance(percent*ray.Distance()); //Test Point i% down the ray
            if (p.Contains(tp)){
                lp = tp; //It worked, store it
                break;
            }
        }
        if (lp){
            c = lp;
            break;
        }
    }
}
return c;}

Wciąż trochę zuchwały, ale wydaje się, że działa.

Kolejny „brudny” algorytm, aby to zrobić:

• Weź obwiednię geometrii (Xmax, Ymax, Xmin, Ymin)

• Pętla do momentu ( Xmin+rand*(Xmax-Xmin), Ymin+rand*(Ymax-Ymin) ) znalezienia losowego punktu w obrębie geometrii (za pomocą Google-Maps-Point-in-Polygon )

W świetle ostatniego wyjaśnienia, że ​​wolisz lokalizację ściśle wewnętrzną, możesz wybrać dowolny punkt w transformacji osi środkowej, który nie znajduje się również na granicy wielokąta. (Jeśli nie masz kodu dla MAT, możesz go przybliżyć przez negatywne buforowanie wielokąta. Wyszukiwanie binarne lub sieczne szybko wygeneruje mały wewnętrzny wielokąt zbliżony do części MAT; użyj dowolnego punktu na jego granicy).

Dlaczego nie użyć środka ciężkości tylko do pozycji pionowej (szerokości geograficznej)? Następnie możesz ustawić etykietę poziomo, wybierając średnią długość geograficzną na tej szerokości geograficznej . (W tym celu należy znaleźć wartość długości geograficznej krawędzi wielokąta na określonej szerokości geograficznej, co nie powinno sprawiać kłopotów).

Uważaj również na kształty U i bardziej złożone. :) Być może dla tych, wybierz średnią z najbardziej prawej pary długości (każda para odpowiada plasterkowi wielokąta), ponieważ okno informacyjne jest zorientowane w ten sposób?

Daje to również nieco większą kontrolę nad pozycjonowaniem; na przykład fajnie byłoby ustawić okno informacyjne na 66 lub 75% w pionie, aby pozostawić więcej widocznego wielokąta. (Lub może nie! Ale masz pokrętło, aby dostosować.)

A może wystarczy użyć punktu, który użytkownik kliknął, aby go wybrać, jeśli jest on wybrany przez użytkownika, który jest.

Też próbuję to rozwiązać. Nałożyłem warunek na moje wielokąty, że nie mogą one przekraczać linii, co wchodzi w to, co opiszę.

Więc moje podejście wykorzystuje triangulację. Weź losowy wierzchołek (prawdopodobnie weź wierzchołek na skrajnym N, E, W lub S może uprościć rzeczy).

Z tego wierzchołka narysuj linie do wierzchołka oddalonego o jeden wierzchołek, tj. Jeśli twój wierzchołek to wierzchołek 3, spójrz na wierzchołek 3 + 2.

Zbuduj linię z oryginalnego wierzchołka do tego wierzchołka. Jeśli skonstruowana linia:

1. nie przekracza żadnej innej linii i
2. jego punkt środkowy nie znajduje się poza wielokątem

Następnie zbudowałeś trójkąt, który znajduje się w wielokącie. Jeśli pomyślnym wierzchołkiem było n + 2, to twój trójkąt to {n, n + 1, n + 2}, który będziemy określać jako {v, v1, v2}. Jeśli nie, wypróbuj następny wierzchołek i kontynuuj, aż wszystkie wierzchołki zostaną wypróbowane.

Kiedy znajdziesz trójkąt, znajdź jego środek, poprowadząc linię od wierzchołka v do punktu środkowego v1 i v2. Środek tej linii z pewnością znajdzie się wewnątrz trójkąta i wewnątrz wielokąta.

Jeszcze tego nie zakodowałem, ale widzę, jak się nad tym zastanawiam, że wielokąt z przecinającymi się liniami w rzeczywistości spowoduje pewne egzotyczne warunki, w których to nie zadziała. Jeśli masz taki typ wielokątów, musisz przetestować każdy segment linii na wielokącie i upewnić się, że nie został przekroczony. Pomiń odcinki linii, które są skrzyżowane i myślę, że to zadziała.

Przydatna może być https://github.com/mapbox/polylabel (javascript i C ++). Wdrożenie C # tutaj: https://gist.github.com/dfaivre/acfef42cdbf411555956e9eba65dd30d .

Oryginalne pytanie SO tutaj: /programming//a/38522611/79113