Wielokąt w 3D - podział na obszary płaskie.

Witam,

mam w przestrzeni 3D wielokąt, który nie jest planarny.
Szukam rozwiązania, algorytmu takiego ażeby wyodrębnić w nim wszystkie obszary płaskie.
Może być to zrobione przy użyciu zewnętrznej biblioteki,
jakieś sugestie?

Pozdrawiam.

W jakiej postaci go przechowujesz? Jeśli na przykład masz zbiór punktów, to możesz próbować dzielić to na trójkąty (w przestrzeni trójwymiarowej każdy trójkąt jest płaski).

Przykładowy algorytm:
1. Wybierasz sobie jeden punkt (A) należący do wielokąta.
2. Bierzesz dwa sąsiednie punkty (B i C) względem punktu A.
3. Otrzymujesz trójkąt, który musi należeć do wielokąta i musi być płaski (z definicji).
4. Startując z punktu B przechodzisz do kolejnego punktu i sprawdzasz, czy należy do tej samej płaszczyzny, co otrzymany trójkąt.
5. Jeśli tak, to zamiast trójkąta masz czworokąt (pięciokąt, sześciokąt, i tak dalej - dopóki znajdujesz punkty należące do tej samej płaszczyzny).
6. To samo robisz startując z punktu C (dopóki nie trafisz na punkt nienależący do tej samej płaszczyzny).
7. Masz pierwszy wielokąt płaski o maksymalnej liczbie kątów, ponieważ punkty z obu stron leżą w innej płaszczyźnie.
8. Dwa ostatnie punkty są jedną z krawędzi nowego trójkąta.
9. Dokładasz jeden z sąsiadujących punktów otrzymując trójkąt i wracając do punktu trzeciego.
10. Gdy wszystkie punkty zostaną odwiedzone, zakończ algorytm.

To niestety nie jest dobre rozwiązanie.
Ten obrazek to wyjaśnia:

https://my.pcloud.com/publink​/show​?code=XZBVpR7Zspd1rgigmwmqQh64S7xpOHxxPlyX

Jeśli zaczniemy od lewej strony powstanie trójkąt, który nie należy do płaszczyzny wielokąta.

Skąd masz ten wielokąt?

Jeśli zaczniemy od lewej strony powstanie trójkąt, który nie należy do płaszczyzny wielokąta.

W takim razie najpierw należy znaleźć dowolny trójkąt należący do wielokąta.
1. Wybierz dowolny punkt A należący do wielokąta.
2. Wychodząc z punktu A znajdź taki punkt B, który tworzy odcinek AB należący do wielokąta.
3. Wychodząc z punktu A lub B znajdź taki punkt C, aby trójkąt złożony z tych trzech punktów należał do wielokąta.
4. Skorzystaj z poprzedniego algorytmu, zastępując kroki 1-3 oraz 8-9 prawidłowym szukaniem trójkąta.

Mój wielokąt to tablica punktów, wierzchołki biegną po kolei, współrzędne ostatniego punktu są równe punktowi startowemu.

>> 3. Wychodząc z punktu A lub B znajdź taki punkt C, aby trójkąt złożony z tych trzech punktów należał do wielokąta.

Pytanie zasadnicze - jak to stwierdzić? :)

Ten problem jest ciekawszy niż się spodziewałem. Znalezienie trójkąta należącego do wielokąta (mając dwa odcinki należące do niego) można sprowadzić do znalezienia dodatkowego odcinka, który do niego należy (co w przestrzeni trójwymiarowej może być równie trudne, więc trzeba kombinować inaczej). A skoro całe zadanie można sprowadzić do znalezienia odpowiednich odcinków dzielących wielokąt na mniejsze części, to chyba nie tędy droga.

Własne pomysły, może coś się przyda:
1. Zacząć od trzech pierwszych punktów tworząc trójkąt, a następnie stopniowo dodawać/usuwać poszczególne fragmenty w miarę dołączania kolejnych punktów aż do uzyskania całego wielokąta.
2. Wyznaczyć prostopadłościan, w którym na pewno znajdują się wszystkie punkty i stopniowo ciąć go płaszczyznami odrzucając fragmenty, które na pewno nie należą do wielokąta.

Co do szukania rozwiązań, to wyrażenie polygon partition daje całkiem sensowne wyniki, może coś znajdziesz. Ale...

The problem of partitioning a rectilinear polygon to a smallest number of squares (in contrast to arbitrary rectangles) is NP-hard.

Czyli zapewne ogólny przypadek, gdzie bierzesz dowolny, trójwymiarowy wielokąt i dzielisz go na figury płaskie, może się okazać dość złożony. Może lepiej spróbuj opisać, do czego tego potrzebujesz - możliwe, że da się to sprowadzić do jakiegoś bardziej szczegółowego problemu, który będzie łatwiej rozwiązać.

>> Może lepiej spróbuj opisać, do czego tego potrzebujesz - możliwe, że da się to sprowadzić do jakiegoś bardziej szczegółowego problemu, który będzie łatwiej rozwiązać.

Mam funkcję, która wypełnia wielokąt wzorem, problem w tym że działa tylko na płaskich obszarach.
Nie da się tego zrobić wspomagając się jakimiś dedykowanymi bibliotekami C, C++?
Bo problem jak widać nie jest prosty:)