Konwergencja punktu łamania w algorytmie losu

Question

Wprowadzam algorytm losowy Fortune do obliczania diagramów Voronoi. Moje główne odniesienie to "Geometria obliczeniowa: algorytmy i zastosowania" de Berg et al., I chociaż ich omówienie tematu jest bardzo jasne, przekazują one kilka małych, ale ważnych szczegółów, z którymi miałem problemy z samodzielnym wykonywaniem pracy. Szukałem pomocy w Internecie, ale inne strony internetowe dają nawet wyższy przegląd niż podręcznik lub podają dokładnie ten sam pseudokod od książki.

Potrzebuję sposobu, aby ustalić, czy para punktów przerwania określona przez potrójne łuki na linii plaży zbiega się lub rozchodzi, w celu wykrycia nadchodzących zdarzeń koła. Wydaje się, że aby podjąć decyzję, potrzebowałabym wiedzy na temat kształtu krawędzi komórek Voronoi, które wyznaczają punkty przerwania w miarę postępu algorytmu Fortune. Na przykład, gdybym mógł znaleźć nachylenie krawędzi wyznaczonej przez punkt przerwania, mógłbym obliczyć, gdzie przecinają się dwie linie utworzone przez punkty przerwania i ich odpowiednie nachylenia, i zdecydować, czy zbiegają się w oparciu o ten wynik. Jednak nie mam pojęcia, jak uzyskać informacje o stokach, tylko aktualna pozycja punktów przerwania.

Jedyną informacją, z którą muszę pracować, jest lokalizacja x, y trzech miejsc i bieżąca współrzędna y linii odlewniczej (używam poziomej linii konturu).

Właściwie, mam jeden pomysł na określenie zbieżności. Biorąc pod uwagę dwie lokalizacje, punkt przerwania między dwiema częściami zdefiniowanej przez nich linii brzegowej jest regulowany tylko przez bieżące położenie linii przeciągnięcia. Zastanawiałem się nad nagrywaniem pozycji dwóch punktów przerwania, chwilowo przesuwając linię wyciągnięcia o niewielką ilość i rejestrując ich nowe pozycje. Ponieważ krawędzie w normalnym diagramie Voronoi nie wyginają się, jeśli odległość między nową parą punktów przerwania jest mniejsza niż odległość między starą parą, to punkty przerwania zbiegają się; w przeciwnym razie się rozchodzą. Ale wydaje się to zarówno niebezpieczne (nie mam pojęcia, czy to zawsze działa), jak i brzydkie. Z pewnością musi istnieć lepszy sposób.

Wszelkie pomysły zostałyby docenione, a pseudokod (w C# -like składni, jeśli to możliwe), szczególnie tak. Mam również świadomość, że istnieją biblioteki geometrii obliczeniowej, których mogę użyć do uzyskania diagramów Voronoi, ale jest to ćwiczenie osobiste, dlatego chcę samodzielnie wdrożyć wszystkie części algorytmu.

Answer 1

Witamy Drake. Zaimplementowałem go, sprawdzając, czy punkty przerwania fizycznie zbiegają się na środku koła w "fikcyjnym" zwiększeniu pozycji linii. To faktycznie nieco komplikuje się, ponieważ w niektórych przypadkach środek okręgu może znajdować się prawie lub dokładnie w pozycji pochylonej, tak więc skok pędu musi być proporcjonalny do różnicy między bieżącą pozycją pocięcia a środkiem koła generowanym zgodnie z zaleceniami użytkownika.

Say:

1. currentSweeplineY = 1.0f; circleCenterY = 0.5f (i poruszamy się w dół, tj. W malejącym kierunku y).

2. Set sweepYIncrement = (circleCenterY - currentSweepLineY)/10.0f (Dzielnik 10,0f jest arbitralnie wybrany).

3. Check new breakpoint positions at new sweepline position.

4. Check distance to circle center.

5. If both distances are less than current distances, the breakpoints converge.

Wiem, że jest to prawdopodobnie bardzo kosztowne, ponieważ musisz wielokrotnie obliczać pozycje punktów przerwania, ale jestem pewien, że zajmie się wszystkimi możliwymi przypadkami.

W każdym razie znajduję poważne problemy z błędem precyzji zmiennoprzecinkowej w innym miejscu algorytmu. Zdecydowanie nie tak proste, jak początkowo myślałem.

Answer 2

Jest to dość zawstydzające, ale po przespaniu problemu odpowiedź wydaje się oczywista. Piszę to, aby, miejmy nadzieję, pomóc uczniom w przyszłości z tym samym pytaniem co ja.

Krawędź Voronoi między dwoma miejscami prostopadle dzieli się na pół (wyimaginowany) odcinek linii łączący obiekty. Można uzyskać nachylenie krawędzi, przyjmując prostopadłość nachylenia segmentu linii łączącej, a następnie wykonać test przecięcia linii na dwóch krawędziach, ale jest jeszcze łatwiejszy sposób.

Dopóki trzy lokalizacje są not collinear, krawędzie, które prostopadle dzielą na pół segmenty między lokalizacjami są również styczne do okręgu, którego krawędź zawiera wszystkie trzy miejsca. Dlatego punkty przerwania zdefiniowane przez potrójny punkt Voronoi zbiegają się, jeśli środek okręgu zdefiniowany przez te trzy lokalizacje znajduje się przed witryną środkowej, gdzie "z przodu" i "z tyłu" zależy od układu współrzędnych i wyrównania linii odrysowej. wybrałem.

W moim przypadku mam poziomą linię wobulacji, którą przesuwam od minimalnego y do maksymalnego y, więc punkty przerwania zbiegają się, jeśli współrzędna y środka koła jest większa niż współrzędna y środkowego obszaru i rozchodzą się inaczej.

Edytuj: Kristian D'Amato słusznie wskazuje, że powyższy algorytm pomija pewne przypadki zbieżności. Ostatni algorytm, który wykorzystałem, znajduje się poniżej.Oczywiście nie jestem pewien, czy jest to w 100% poprawne, ale wydaje się, że działa we wszystkich przypadkach, w których go wypróbowałem.

Given left, middle, right sites 
    if they are collinear, return false 
    center = ComputeCircleCenterDefinedBy3Points(left, middle, right) 
    return IsRightOfLine(left, middle, center) && IsRightOfLine(middle, right, center) 

IsRightOfLine(start, end, point) 
    ((end.X - start.X) * (point.Y - start.Y) - (end.Y - start.Y) * (point.X - start.X)) <= 0 

Answer 3

Jeśli strony są uporządkowane zgodnie z ruchem wskazówek zegara wokół środka okręgu, łuk się zbiega. Jeśli są one uporządkowane w kierunku przeciwnym do ruchu wskazówek zegara wokół środka okręgu, łuk jest rozbieżny. (lub odwrotnie, w zależności od implementacji). Testowanie cw lub ccw wypada z kodu, którego używasz do znalezienia środka okręgu.

Oto fragment kodu C# do obliczania circumcenter d punktów a, b, c:

 Vector2 ba = b - a; 
     Vector2 ca = c - a;  
     float baLength = (ba.x * ba.x) + (ba.y * ba.y); 
     float caLength = (ca.x * ca.x) + (ca.y * ca.y); 
     float denominator = 2f * (ba.x * ca.y - ba.y * ca.x); 
     if (denominator <= 0f) { // Equals 0 for colinear points. Less than zero if points are ccw and arc is diverging. 
      return false; // Don't use this circle event! 
     }; 
     d.x = a.x + (ca.y * baLength - ba.y * caLength)/denominator ; 
     d.y = a.y + (ba.x * caLength - ca.x * baLength)/denominator ;