Algorytm tworzenia sąsiednich trójkątów

Mam system, w którym możesz kliknąć raz, aby umieścić węzeł w scenie. Po umieszczeniu 3 węzłów tworzy trójkąt. Po umieszczeniu jakichkolwiek przyszłych węzłów tworzy nowy trójkąt, łącząc ten węzeł z 2 najbliższymi istniejącymi węzłami.

Działa to dobrze przez większość czasu, ale jest wadliwe, gdy jest używane w pobliżu trójkątów o bardzo ostrych kątach, ponieważ jeden z 2 najbliższych węzłów często nie jest tym, który powinien zostać użyty.

Na przykład zobacz obrazek poniżej. Trójkąt magenta jest umieszczony pierwszy. Jeśli następnie kliknę na pozycję oznaczoną X, otrzymam nowy trójkąt, w którym znajduje się niebieska nakładka. Chcę nowego trójkąta z zieloną nakładką. (tj. symetryczny do magenta, w tym przykładzie. Wyjaśnienie: trójkąty zielony i magenta nie nakładają się - zielony rozciąga się pod niebieskim do lewego skrajnego węzła)

Jak mogę określić, które 2 istniejące wierzchołki należy zastosować podczas tworzenia nowych trójkątów, aby trójkąty nie były nakładane w ten sposób?

EDYCJA : Wyszukiwanie najbliższej krawędzi daje lepsze wyniki, ale nie doskonałe. Rozważ tę sytuację:

Test „najbliższej krawędzi” jest niejednoznaczny i może zwrócić AB lub AC (ponieważ najbliższy punkt do X dla obu jest w A). Pożądanym wynikiem byłoby AC, aby utworzyć trójkąt ACX bez nakładających się krawędzi. Jak mogę zapewnić ten wynik? (Wolałbym nie przeprowadzać testów nakładania się pojedynczych krawędzi, jeśli to możliwe, ponieważ obawiam się, że najbliższy test krawędzi niekoniecznie wykryje 2 są dokładnie w jednakowej odległości, biorąc pod uwagę problemy z precyzją zmiennoprzecinkową.)

Zamiast znajdować minimalną odległość od węzłów, znajdź minimalną odległość od krawędzi (tj. Segment linii zdefiniowany przez węzły).

Następnie, jeśli najbliższym punktem jest wierzchołek (który będziesz musiał użyć testu epsilon ** zmiennoprzecinkowego), porównaj kąt między linią od nowego punktu do wierzchołka a każdą z krawędzi połączonych z tym wierzchołkiem. Wybierz ten z minimalnym kątem bezwzględnym:

MinAngle(newPoint, vertex, edge1, edge2)
{
   newEdgeUnit = norm(newPoint - vertex); // don't actually need to normalize this
   edge1Unit = norm(edge1 - vertex);      // you probably have these from your dist to line tests
   edge2Unit = norm(edge2 - vertex);

   edge1Dot = dot(edge1Unit, newEdgeUnit);
   edge2Dot = dot(edge2Unit, newEdgeUnit);

   // you can simply compare dot products to find the minimum absolute angle
   if (edge1Dot > edge2Dot) return edge1;     // set up this way so you can generalize to an array
   return edge2;
}

** Aby uniknąć dodawania zdegenerowanych trójkątów, które mogłyby zakłócać test epsilon, możesz umieścić obszar wokół każdego wierzchołka, w którym dodawanie punktów jest niedozwolone (coś w rodzaju zakazu punktów w pewnej wielokrotności epsilonu użytego powyżej).

Po umieszczeniu pierwszego trójkąta, umieszczając nowy wierzchołek, zawsze generujesz dwie nowe krawędzie. Trzecia krawędź nowego trójkąta będzie zawsze krawędzią wspólną z poprzednim trójkątem. Gdybyś mógł znaleźć sposób na określenie wspólnej krawędzi, wiedziałbyś, z którymi wierzchołkami się połączyć, ale to jest trudna część. Uważam, że można to zrobić poprzez narysowanie linii od nowego wierzchołka do środka każdej z trzech ostatnich wygenerowanych krawędzi (lub prawdopodobnie 3 najbliższych krawędzi).

Jeśli linia od wierzchołka do środka krawędzi nie przecina żadnej z pozostałych dwóch krawędzi, masz wspólną krawędź. Wspólna krawędź powie ci, z którymi dwoma wierzchołkami połączyć nowy wierzchołek.

Jimmy poruszył sprawę dotyczącą niejasności co do tego, gdzie pójdzie nowy trójkąt:

To dałoby ci możliwość wyboru między dwoma ważnymi trójkątami. Być może rozstrzygnięcie jest tym, który punkt środkowy jest najbliższy.

Biorąc pod uwagę twoją aktualizację, choć bardziej złożoną, moje rozwiązanie spowoduje remis tylko wtedy, gdy będziesz mieć dwa prawidłowe trójkąty. Korzystając z tej metody, twój drugi przykładowy obraz da pożądany rezultat.

Mając magenta trójkąt ABC, włączasz nowy wierzchołek X. Myślę, że oczywiste jest, że będą dwie linie zaczynające się od D, które nie przecinają się między żadnymi krawędziami trójkąta ABC.

Te dwie linie mogą być AX i BX, BX i CX lub AX i CX. Możesz następnie potraktować swój problem jako klasyczny problem „czy przecinają się dwie linie”? Następnie możesz sprawdzić, która z tych par linii nie przecina się z żadną z krawędzi trójkąta ABC, wykonując na przykład dowolną z metod z tego pytania . W związku z tym będziesz mieć dwie nowe krawędzie nowego trójkąta.

Ustalenie, czy znajdujesz się w jednym z jednoznacznych regionów (1, 2, 3 poniżej), jest dość łatwe: potraktuj każdą krawędź trójkąta jako płaszczyznę 2D i sprawdź, po której stronie płaszczyzny znajduje się nowy punkt. Jeśli jesteś w dwóch z nich, ale poza jednym, to ten odpowiada krawędzi trójkąta, który tworzy dwa wierzchołki w twoim nowym trójkącie.

Jeśli jesteś wewnątrz jednego i na zewnątrz dwóch, jesteś w dwuznacznym przypadku, w którym najbliższa część trójkąta do nowego punktu jest rogiem. W takim przypadku możesz utworzyć płaszczyznę 2D z punktu środkowego przeciwległej krawędzi (tej, w której się znajdujesz) i najbliższego wierzchołka (tej współdzielonej przez dwie płaszczyzny, na których jesteś poza). Możesz wybrać krawędź w zależności od strony tej płaszczyzny, na której znajduje się nowy punkt.

Zauważ, że test płaszczyzny w 2D działa tak samo jak w 3D: kropka wektora z dowolnego miejsca na płaszczyźnie do swojego punktu normalną płaszczyzną (w 2D jest to prostopadła linia).

(Nawiasem mówiąc, obszary rozdzielone karmazyną na tym obrazie nazywane są regionami Voronoi; są to obszary przestrzeni zawierające punkty, które są najbliżej określonej cechy - krawędzi lub wierzchołka - trójkąta. Edycja: Moja terminologia tutaj nie jest w rzeczywistości całkiem poprawnie, to nie są dokładnie regiony Woronoi).