Wykryto, czy zbiór punktów w tablicy, które są wierzchołkami złożonego wielokąta, został zdefiniowany w kolejności zgodnej z ruchem wskazówek zegara lub w przeciwnym kierunku?

Question

EDYCJA: Zaktualizowałem program z odpowiedzią i działa świetnie!

Robię program (możesz go wypróbować), który pozwala użytkownikom narysować wielokąty, które następnie trianguluje. Mogą kliknąć, aby dodać wierzchołki i nacisnąć Enter, aby dokonać triangulacji. W każdym razie algorytm działa dobrze tak długo, jak mówię, jeśli punkty zostały narysowane w sposób zgodny z ruchem wskazówek zegara lub przeciwny do ruchu wskazówek zegara (w tej chwili mam go ustawiony tylko do pracy z wielokątami zgodnymi z ruchem wskazówek zegara). Próbowałem to zrozumieć przez kilka dni, ale nie mam pojęcia, jak ustalić, czy punkty są zgodne z ruchem wskazówek zegara czy przeciwnie. Spróbuj rysować kształty za pomocą wspomnianego wcześniej programu, aby uzyskać lepszy pomysł, możesz doświadczyć tego, o czym mówię, lepiej, niż potrafię to wyjaśnić.

Oto jak punkty są zdefiniowane:

function Point(x, y) { 
    this.x = x; 
    this.y = y; 
} 

var vertices = []; 

// Called on click 
function addPoint(mouseX, mouseY) { 
    vertices.push(new Point(mouseX, mouseY)); 
} 

Oto obraz wielokąta zegara:

Oto obraz przeciwnym wielokąta:

Jeśli mógłbyś mi pomóc dowiedzieć się, jak określić "punkt widzenia w prawo" punktów, byłbym bardzo wdzięczny!

Answer 1

Oblicz poligon za pomocą shoelace formula, ale bez znaku wartości bezwzględnej. Jeśli wynik jest dodatni, punkty są sortowane przeciwnie do ruchu wskazówek zegara, a jeśli ujemne - zgodnie z ruchem wskazówek zegara.

function polygonArea() { 
    var area = 0; 
    for (var i = 0; i < vertices.length; i++) { 
     j = (i + 1) % vertices.length; 
     area += vertices[i].x * vertices[j].y; 
     area -= vertices[j].x * vertices[i].y; 
    } 
    return area/2; 
} 
var clockwise = polygonArea() > 0; 

Answer 2

Ogólną ideą byłoby przyjrzenie się wypukłemu kadłubowi wielokąta i odgadnięcie jego orientacji. Uważam jednak, że nie trzeba budować całego kadłuba, aby znaleźć orientację, ale tylko jeden segment należący do niego.

Więc:

• Znajdź dwa punkty swoimi polygones tak, że wszystkie pozostałe punkty są po jednej stronie tej linii.
• Jeśli wszystkie punkty znajdują się po lewej stronie (wystarczy sprawdzić jeden z punktów), przeciwnie do ruchu wskazówek zegara. Jeśli są po prawej stronie, to zgodnie z ruchem wskazówek zegara.

Przykład:

Na górnej figurze 4-5 pozwolić na rysunku po prawej stronie, 5-11 pozwolić na rysunku po prawej stronie, ... Na dolnym rysunku: 6 7 niech rysunek po lewej stronie, 7-14 niech postać po lewej, ...

Ostrzeżenie: Podczas "chodzenia" na swoim wielokącie, nie restartuj numeracji, w przeciwnym razie będzie źle. Na górnej figurze 4- (n-1) niech figurka po lewej stronie!

Answer 3

Twoja intuicyjna definicja clockwisedness nie jest dobrze zdefiniowana. Na przykład, jeśli rysuję podkowa:

/---a-b--\ 
/ _d_c_ \ 
//  \ \ 
| |  | | 
| |  | | 
    \ \  // 
    \ \ // 
    --  -- 

Jeśli 0 = a < b < b < d i patrzę na a i b chciałbym wnioskować z opisu, że kształt został sporządzony w prawo, ale jeśli 0 = c < d < a < b Chciałbym stwierdzić, że kształt został rysowane w kierunku przeciwnym do ruchu wskazówek zegara.Ponieważ oba te scenariusze dotyczą tego samego kierunku, w którym punkty zostały narysowane, tylko z różnych punktów początkowych, mogę tylko stwierdzić, że brakuje twojej definicji.

Podkowa, którą rysowałem, nie jest najlepsza; chodzi o to, że jest to prawie okrąg z niewielkim otworem u dołu, umożliwiającym narysowanie drugiej strony w przeciwnym kierunku.

Jeśli jesteś zainteresowany w określaniu rzeczy bardziej ściśle, to proponuję coś wzdłuż następujące wiersze:

rozważeniu wszelkich skończonych prosty wielokąt jako oddzielając płaszczyznę na dwa odrębne obszary (jedną skończoną i jeden nieskończony), zawsze możemy uznać, że skończony obszar jest wnętrzem wielokąta. W takim scenariuszu definiujemy zamawianie wierzchołków zgodnie z ruchem wskazówek zegara, w którym kolejność punktów przebiega z zewnętrzną stroną po prawej stronie. Nazywa się to curve orientation.

Po uzyskaniu bardziej jednolitej definicji wdrożenie może być tak proste, jak zliczanie numeru nawijania. Weź punkt środkowy dowolnej zamówionej pary, powiedzmy 0 i 1, weź odcinek linii na prawo od zamówionej pary (pod dowolnym kątem, powiedzmy prostopadle) i policz, ile przecięć ma z innymi segmentami linii: Krzywa jest zgodna z ruchem wskazówek zegara liczba jest nieparzysta.

Jest to proste do wdrożenia, liniowe w czasie O(n) i dodaje stałą przestrzeń O(1).

Answer 4

Ta funkcja funkcjonalna specjalizuje się w OpenLayers. Jak widać stan wielokąta w prawo jest obszarem Potwierdź.

function IsClockwise(feature) 
{ 
if(feature.geometry==null)return -1; 
var vertices=feature.geometry.getVertices(); 
var area=0; 
for (var i = 0; i < (vertices.length); i++) 
    { 
    j = (i + 1) % vertices.length; 
    area += vertices[i].x * vertices[j].y; 
    area -= vertices[j].x * vertices[i].y; 
    // console.log(area); 
    } 
return (area < 0); 
} 

Answer 5

W przypadku gdy ktoś używa Three.js na ShapeUtils pochodzi z wbudowanym isClockWise metody, które wewnętrznie używa metody area określić znak na obszarze analizowanym.

isClockWise: function (pts) { 

    return ShapeUtils.area(pts) < 0; 

} 

Metoda ShapeUtils.isClockWise można znaleźć here.

area: function (contour) { 

    var n = contour.length; 
    var a = 0.0; 

    for (var p = n - 1, q = 0; q < n; p = q ++) { 

     a += contour[ p ].x * contour[ q ].y - contour[ q ].x * contour[ p ].y; 

    } 

    return a * 0.5; 

}, 

Metoda ShapeUtils.area można znaleźć here.