Witam,
mam w przestrzeni 3D wielokąt, który nie jest płaski, składa się z kilku płaskich powierzchni.
No i teraz pytanie o jakąś bibliotekę w C, C++ przy pomocy której mógłbym wyodrębnić wszystkie płaskie powierzchnie zadanego wielokąta.
Wydaje mi się że najpierw należałoby całość sprowadzić do trójkątów a następnie połączyć trójkąty, które są współpłaszczyznowe.
Problem nie jest na 5min dlatego pytam o jakieś gotowe open-sourcowe rozwiązania.
Pozdrawiam.
Wydaje mi się, że sam algorytm jest prosty i do zrobienia w czasie O(n). Zakładamy, że masz punkty po kolei (wg brzegu "wielokąta") w jakiejś tablicy w[0..n-1]. Teraz wyobrażam to sobie tak:
C++ 
w[0], w[1], w[2] do tablicy plaszczyzna[0] (trzy punkty zawsze są na płaśzczyźnie).i = 3 oraz p = 0i < n:
w[i-3], w[i-2], w[i-1], w[i] są współpłaszczyznowe to wrzucasz w[i] do zbioru plaszczyzna[p]++p i zaczynasz nową płaszczyznę plaszczyzna[p] z punktami w[i-2], w[i-1], w[i] (tak, dwa punkty będą wspólne dla sąsiednich płaszczyzn)++iAle, problemem może być działanie na liczbach niecałkowitych -- tu będą błędy naturalne dla nich i współpłaszczyznowość może być przybliżona...
W grafice 3d zazwyczaj wszystko rysuje się za pomocą trójkątów ponieważ tylko te wielokąty dają 100% pewności że będą płaskie.
Załóżmy że masz te punkty rozpisane tak, że tworzą trójkąty składające się na twój wielokąt, np:
p[0], p[1], p[2] - pierwszy trójkąt
p[3], p[4], p[5] - drugi trójkąt
itd (nie wiem czy masz te punkty tak rozpisane czy nie, nawet nie wiadomo jak i za pomocą czego rysujesz, jeśli tak to bardzo dobrze).
Możesz stworzyć metodę sprawdzającą czy sześć takich liczb składających się na dwa trójkąty leżą na jednej płaszczyźnie, tu masz jakiś przykład jak wygląda sprawdzanie czy cztery punkty leżą na jednej płaszczyźnie: https://www.matematyka.pl/79295.htm - wypada sprawdzić tą metodą czy:
p[0], p[1], p[2], p[3] i
p[0], p[1], p[2], p[4] oraz
p[0], p[1], p[2], p[5]
leżą na tej samej płaszczyźnie, jeśli tak to możesz oznaczyć te dwa trójkąty jako współpłaszczyznowe.
Pozostaje tylko sprawdzić wszystkie możliwe kombinacje trójkątów i przypisać je do odpowiednich płaszczyzn, lub nie jeżeli jakimś dziwnym trafem żadne nie są współpłaszczyznowe (chociaż też tak może być).
Możliwe że ta metoda nie jest optymalna, ale wiem że bryły 3d najczęściej opisuje się za pomocą trójkątów i najłatwiej sprawdzać trójkąty (zwłaszcza jak się trochę porysuje te bryły 3d za pomocą trójkątów ).
koszalek-opalek napisał(a):
Wydaje mi się, że sam algorytm jest prosty i do zrobienia w czasie O(n). Zakładamy, że masz punkty po kolei (wg brzegu "wielokąta") w jakiejś tablicy
w[0..n-1]. Teraz wyobrażam to sobie tak:
No więc wpadłem dokładnie na takie rozwiązanie i nawet je zrealizowałem.
Niestety ten sposób powoduje generację sporej ilości trójkątów nie należących do wielokąta.
No i teraz jest kolejny problem jak rozpoznać te, które nie należą?
Problem nie jest do rozwiązania w 5min i dlatego pytam o jakieś gotowe, dobrze przemyślane rozwiązania.
Pozdrawiam.
Wesoły Kot napisał(a):
koszalek-opalek napisał(a):
Wydaje mi się, że sam algorytm jest prosty i do zrobienia w czasie O(n). Zakładamy, że masz punkty po kolei (wg brzegu "wielokąta") w jakiejś tablicy
w[0..n-1]. Teraz wyobrażam to sobie tak:No więc wpadłem dokładnie na takie rozwiązanie i nawet je zrealizowałem.
Niestety ten sposób powoduje generację sporej ilości trójkątów nie należących do wielokąta.
To znaczy, że nie zrealizowałeś tego, o czym ja pisałem...
No i teraz jest kolejny problem jak rozpoznać te, które nie należą?
W moim algorytmie lecisz tylko po trójkątach z wielokąta -- chyba, że się mylę... Podaj przykłąd, może rzeczywiście o czymś nie pomyślałem?
koszalek-opalek napisał(a):
W moim algorytmie lecisz tylko po trójkątach z wielokąta -- chyba, że się mylę... Podaj przykłąd, może rzeczywiście o czymś nie pomyślałem?
Pokaże kilka prostych przykładów.
Po prawej stronie wielokąt wypełniony ażeby było widać gdzie jest "złamany".
Zobacz czy to co zaproponowałeś będzie działać na tych prostych przypadkach, jeśli tak to pomyślę co źle zrobiłem.
Pozdrawiam.
koszalek-opalek napisał(a):
Masz rację -- mój algorytm nie zawsze działa. Mam pewien pomysł na polepszenie algorytmu, ale chyba nie na szybko. :) Spróbuję to zrobićw najbliższych godzinach. :)
Jeśli byś mógł coś zaproponować bo ja już "przegrzałem obwody" :).