test czy zadany punkt leży wewnątrz czworościanu

0

Mamy dany czworościan o wierzchołkach: A,B,C,D, oraz punkt P, wszystko w postaci (x,y,z);
jak szybko stwierdzić, czy ten punkt leży wewnątrz czworościanu, czy też na zewnątrz?

0
Patryk27 napisał(a):

https://www.google.com/search?q=point+inside+tetrahedron

Ale chodzi o szybkie wyliczenie - optymalne, a nie takie które wymaga setek operacji na macierzach 4x4; na płaszczyznach też odpada - za dużo to kosztuje.

1

Hej,
jeżeli V to objętość całego czworościanu, a V1, V2, V3, V4 są objętościami czworościanów o podstawach będących kolejnymi ścianami czworościanu V, i mającymi wspólny wierzchołek P, to wystarczy sprawdzić warunek (konieczny i wystarczający, jak sądzę):

V = V1 + V2 +V3 + V4
0

@exp4: sprawdzałeś jakiekolwiek inne rezultaty z Google poza tym pierwszym? ;-)

Anyway: czy Twój czworościan spełnia jakieś względnie ciekawe warunki?
Np. jest ułożony wzdłuż osi czy cokolwiek innego.

0
hurgadion napisał(a):

Hej,
jeżeli V to objętość całego czworościanu, a V1, V2, V3, V4 są objętościami czworościanów o podstawach będących kolejnymi ścianami czworościanu V, i mającymi wspólny wierzchołek P, to wystarczy sprawdzić warunek (konieczny i wystarczający, jak sądzę):

V = V1 + V2 +V3 + V4

Może dobry trop, ale obawiam się że takie coś jest zawsze spełnione.

To chyba tak należy rozwinąć:
V = suma Vi, i = 1..4

i dopiero pod warunkiem: wszystkie Vi mają jednakowe znaki, wtedy P leży w T.

Może ktoś to sprawdzi praktycznie, bo mi się nie chce. :)

Samo wyliczenie objętości jest tu dość łatwe - chyba z wyznacznika 3x3, bo za pomocą trzech wektorów.
u, v, w:
6V = det| u; v; w|

Np. takie coś:
det
|1 0 0
|0 1 0
|0 0 1
= 1
czyli objętość takiego prostokątnego czworościanu, ze ścięcia wierzchołka sześcianu, o bokach 1,1,1 ... = 1/6

To jest nawet całkiem zabawne:
mamy 4 możliwe takie ścinki (z 8-miu wierzchołków cube 1x1x1),
co w sumie daje objętość: 4/6 = 2/3, a w środku pozostanie: V5 = 1/3, co jest czworościanem foremnym o boku sqrt2/2;

0

I jeżeli się nie mylę, to ta własność będzie prawdziwa także dla dowolnych, wypukłych figur dwuwymiarowych i trójwymiarowych (pytanie co z kołem, no to może załóżmy, że dla figur kanciastych). Niestety w większej ilości wymiarów nie widzę :)

PS. a z kołem, to trza inaczej, trzeba obliczyć odległość od środka koła :)

0
hurgadion napisał(a):

I jeżeli się nie mylę, to ta własność będzie prawdziwa także dla dowolnych, wypukłych figur dwuwymiarowych i trójwymiarowych (pytanie co z kołem, no to może załóżmy, że dla figur kanciastych). Niestety w większej ilości wymiarów nie widzę :)

Może raczej dla wypukłych tylko.

PS. a z kołem, to trza inaczej, trzeba obliczyć odległość od środka koła :)

dla powierzchni ciągłych tak samo pójdzie, tyle że z całki zamiast z sumy;
zatem wtedy warunek będzie po prostu: dS, czy dV, ma stały znak, a wtedy jesteś w środku.

0

A może z odległości lepiej wyjdzie?

Mamy 4 ściany, więc wyliczamy odległości z P do każdej... no i co?

Chyba to samo: gdy wszystkie odległości mają ten sam znak, wtedy P leży wewnątrz... hihi!

0

masz problem z liczbami ujemnymi, czy co?

a co powiesz np. na taką zespoloną objętość - niedobra? :)

0

Ok.
Odległość punktu P=(x,y,z) do płaszczyzny ABCD oblicza się wprost z wzora:

d = |Ax + By + Cz + D|/|A,B,C|;
gdzie |X| = norma, czyli jakiś numerek nieujemny - jak moduł |-1| = 1.

zatem co otrzymasz, gdy pomniesz ten moduł w liczniku:

d = Ax + By + Cz + D
(normalizacja: |A,B,C| nas tu nie interesuje, bo chodzi nam o znak, więc to pomijamy - szkoda czasu na dzielenie)

1

Mam inny sposób na sprawdzenie czy dany pkt. leży na przykład w trójkącie, może Cię zainteresuje. Załóżmy, że mamy trójkąt o współrzędnych A=(2,2), B=(6,2), C=(4,6) oraz punkt P=(3,3). Jeżeli punkt leży w środku trójkąta, to da się go przedstawić jako kombinację wypukłą, czyli:

t1*(2,2) + t2*(6,2) + t3*(4,6) = (3,3)
t1 + t2 + t3 = 1

Edit: potrzebny jeszcze jest warunek (spostrzeżenie Mistrzowskiego Kaczora): t1, t2, t3 >= 0 :)

Po przekształceniu otrzymujemy układ równań:

2t1 + 6t2 + 4t3 = 3
2t1 + 2t2 + 6t3 = 3
t1 + t2 + t3 = 1

Układ ten ma rozwiązanie, o ile wyznacznik:

| 2 4 6 |
| 2 6 2 |
| 1 1 1 |

jest niezerowy :)

Edit: no i niestety trzeba wyliczyć t1, t2, t3 , aby sprawdzić dodatkowy, powyższy warunek (Edit)

0

W przypadku **dowolnej ** płaskiej (i bez znaczenia czy wypukłej) figury działa zasada, iż punkt znajduje się wewnątrz "jeziorka" jeśli dowolna półprosta poprowadzona z punktu przecina jego ściany nieparzystą ilość razy. Podejrzewam, że tak samo będzie działać w 3D tylko musisz posprawdzać przecięcia wszystkich płaszczyzn. I trzeba uważać na przypadki szczególne, kiedy półprosta przechodzi przez wierzchołek / krawędź.

0
Freja Draco napisał(a):

W przypadku **dowolnej ** płaskiej (i bez znaczenia czy wypukłej) figury działa zasada, iż punkt znajduje się wewnątrz "jeziorka" jeśli dowolna półprosta poprowadzona z punktu przecina jego ściany nieparzystą ilość razy. Podejrzewam, że tak samo będzie działać w 3D tylko musisz posprawdzać przecięcia wszystkich płaszczyzn. I trzeba uważać na przypadki szczególne, kiedy półprosta przechodzi przez wierzchołek / krawędź.

Marne sposoby.

Pewnie prędzej bym to wyliczył ze zwyczajnego wyliczania kątów:
gdy siedzisz w środku figury, wówczas suma kątów dookoła musi być = 2pi, licząc po wszystkich brzegach - całe koło.

A w zasadzie warunek typu: suma kątów dookoła <> 0 wystarczy, bo gdy stoimy na zewnątrz wyjdzie zero!

P-------------> // trójkąt, czy dowolny wielokąt jest zamknięty:
więc f1 + f2 + ... = 0, bo ten promień lata dookoła - po bokach figury, czyli finalnie zerowy kąt zatoczy... nie?

0
  1. obejdź wielokąt zgodnie z porządkiem kolejnych jego wierzchołków ;
  2. w każdym kroku wyznacz prostą przechodzącą przez bieżący i następny wierzchołek ;
  3. sprawdź czy badany punkt jest po tej samej stronie prostej co jeden z wierzchołków wielokąta; jeśli w którymkolwiek kroku badany punkt nie spełnia tego warunku, przerwij sprawdzanie – punkt jest na zewnątrz ;
  4. jeśli po obejściu całego wielokąta okaże się, że punkt był zawsze (!) po tej samej stronie co reszta wielokąta to punkt jest wewnątrz ;

Inne:

  • Badanie przynależności punktu do wielokąta przez kontrolę parzystości
  • Badanie przynależności punktu do wielokąta na podstawie sumy kątów zorientowanych

Copy paste z książki(pierwszy działa tylko dla wielokąta wypukłego).

1
hurgadion napisał(a):

Mam inny sposób na sprawdzenie czy dany pkt. leży na przykład w trójkącie, może Cię zainteresuje. Załóżmy, że mamy trójkąt o współrzędnych A=(2,2), B=(6,2), C=(4,6) oraz punkt P=(3,3). Jeżeli punkt leży w środku trójkąta, to da się go przedstawić jako kombinację wypukłą, czyli:

t1*(2,2) + t2*(6,2) + t3*(4,6) = (3,3)
t1 + t2 + t3 = 1

Po przekształceniu otrzymujemy układ równań:

2t1 + 6t2 + 4t3 = 3
2t1 + 2t2 + 6t3 = 3
t1 + t2 + t3 = 1

Układ ten ma rozwiązanie, o ile wyznacznik:

| 2 4 6 |
| 2 6 2 |
| 1 1 1 |

jest niezerowy :)
Ok, ale jeszcze musi być spełniony warunek, że t_{i}>=0.

0

Ok, ale jeszcze musi być spełniony warunek, że t_{i}>=0.

ten warunek jest nieco inny: 0 < ti < 1

0

Barycentryczne są równoważne z metodą obliczana pól, o której wspominałem.

P = aA + bB + cC; i a+b+c = 1
P - dowolny punkt wewnątrz trójkąta ABC.

W wersji 3D - czyli z czworościanem, będzie tak samo:

P = aA + bB + cC + dD; i a+b+c+d = 1
P - dowolny punkt wewnątrz czworościanu ABCD.

Zatem dla czworościanu otrzymamy macierz 4x4:
|xa xb xc xd
|ya yb yc yd
|za zb zc zd
|1 1 1 1

Np. dla czworościanu prostokątnego w stylu: A(1,0,0), B(0,1,0), C(0,0,1), D(0,0,0), otrzymamy tu:
1 0 0 0 | xp
0 1 0 0 | yp
0 0 1 0 | zp
1 1 1 1 | 1
co daje chyba wyznacznik: -1
itd.

obliczenia są raczej zbyt skomplikowane.

Metoda z objętości 4 ostrosłupów byłaby szybsza, bo tam są do wyliczenia tylko 4 wyznaczniki 3x3,
a tu są 4 wyznaczniki 4x4, więc zdecydowanie gorsze w obliczaniu - 4 razy.

1

Co wy się tak uparliście na te objętości i płaszczyzny i liczenie biliona wyznaczników?

Skoro to czworościan, czy ogólnie jakiś N-wymiarowy simpleks (odcinek, trójkąt, czworościan etc) to mamy N+1 wierzchołków. Możemy sobie przekształcić układ współrzędnych tak, by jego początek znajdował się w punkcie np. P(N+1) - współrzędne każdego punktu wewnątrz tego simpleksu będą wówczas kombinacją liniową współrzędnych pozostałych N wierzchołków:

P_n =  a_1\cdot{}A_1 + a_2\cdot{} A_2 + ... +  a_n\cdot{}A_n

x_{P1} = a_1\cdot{}x_{1,1} + a_2\cdot{}x_{2,1} + ... + a_n\cdot{}x_{n,1}

...

x_{Pn} = a_1\cdot{}x_{1,n} + a_2\cdot{}x_{2,n} + ... + a_n\cdot{}x_{n,n}

Czyli wystarczy rozwiązać 1 układ równań by znaleźć współczynniki, nie trzeba się bawić w liczenie wyznaczników. Jeżeli będą spełnione warunki:

0 \leq a_k, k \in {1, .., N}

\sum_{i = 1}^{N}a_i  \leq 1

To siłą rzeczy jesteśmy wewnątrz simpleksu, jeżeli któryś warunek nie jest spełniony - to jesteśmy poza :)

Czyli dla czworościanu musimy przekształcić 4 punkty (3 wierzchołki i punkt) odejmując współrzędne piątego, rozwiązać układ 3 równań dowolną metodą i voila.

1

a czy czasem czworościan nie jest stworzony przez cztery punkty niewspółpłaszczyznowe ?? :)

No jest, ale jeśli przeniesiesz układ współrzędnych tak, by jeden wierzchołek był w jego początku, to pozostałe trzy utworzą trójkąt w przestrzeni, współrzędne dowolnego punktu wewnątrz trójkąta możesz przedstawić jako kombinację liniową współrzędnych pozostałych trzech - jeśli suma wag wyniesie 1, to punkt będzie leżał gdzieś w płaszczyźnie przeciwległego boku czworościanu. Jeśli poszczególne wagi są nie większe od 1 i nie mniejsze od 0, to ponadto możemy powiedzieć, że punkt znajduje się wewnątrz tego trójkąta (to się wtedy nazywają współrzędne naturalne lub L-współrzędne i ta właściwość ma swoją drogą zastosowanie np. w MES). Dla sum wag mniejszych od 1 możemy wykorzystać tę samą zależność na podstawie podobieństwa - zawsze będziemy mieli jakiś przekrój na którym leży dany punkt, a który jest podobny do omawianego boku czworościanu :)

Nie umiem się bawić w formalizmy i dowody matematyczne, wszystko biorę na chłopski rozum, ale można z tym wyjść właściwie od przypadku odcinka w 1D i dodawać kolejne punkty tak, by wymagane było dodawanie nowego wymiaru do przestrzeni, za każdym razem możemy stosować wspomnianą regułę z nieujemnymi wagami i sumą wag nie większą od 1, dokładając tylko kolejne wymiary i zakładając analogię z "podobnym odcinkiem", "podobnym trójkątem", "podobnym czworościanem", i tak dalej.

screenshot-20180902205013.png
Poglądowy rysunek na którym próbuję zobrazować to, o co mi chodzi - do niezdolności używania języka matematycznego dochodzi niemota artystyczna, więc jeśli dalej nie wyrażam się zrozumiale to już mówi się trudno :P

0

Spokojnie, intuicję masz dobrą, ale chyba jednak dojdzie czwarta zmienna :) Jeżeli mamy punkty A, B, C, D (wierzchołki czworościanu), mamy też punkt P. Zakładamy, że punkt A ma współrzędne (0, 0, 0), to OK. Teraz możemy wyznaczyć równanie płaszczyzny wyznaczonej przez punkty B, C, D, to też OK :) Niech to równanie ma postać:

E*x + F*y + G*z + H = 0

Dalej: będziemy chcieli, aby prosta t*P, gdzie t jest parametrem przecinała się z płaszczyzną w jednym punkcie, i to tak, aby ten punkt można było przedstawić jako kombinację wypukłą punktów B, C, D. Ja to tak widzę, proste to nie jest, i raczej w tej metodzie liczby zmiennych nie zbijemy do mniejszej niż cztery :)

0

Skoro już przesuwamy układ współrzędnych, to może ustawmy 0.0 na punkt? i teraz albo boki figury przetną wszystkie 4 półproste (x , y, -x, -y),albo punkt jest na zewnątrz.

0

Jeżeli kogoś interesują te tematy, to na .edx jest bardzo fajny kurs (chyba da się go odpalić, robiłem kawałek rok temu) pt. "Computational Geometry", bardzo ciekawie wykłada pewien Chińczyk, na szczęście jest tłumaczenie, ale po angielsku :) kurła, mam już tyle kursów na tapecie, że nie wiem za co się zabrać :)

0

I mam jeszcze jedno kryterium (nie wiem jak bardzo algorytmiczne, ale może ktoś coś fajnego wykoncypuje). Warunek dla trójkąta ABC oraz punktu P. Niech alpha będzie miarą kąta przy wierzchołku P trójkąta ABP, beta kątem przy wierzchołku P trójkąta ACP, a gamma przy wierzchołku P trójkąta BCP. Wtedy punkt leży we wnętrzu trójkąta ABC (lub na brzegu), jeżeli jest spełniony warunek:

sin(alpha+beta+gamma) = 0

Idę spać :)

0

Metoda objętości działa lepiej - przykład:

bierzemy tradycyjny czworościan foremny, taki w sześcianie, czyli o wierzchołkach:

A(1,1,1), B(-1,-1,1), C(1,-1,-1), D(-1,1,-1);

wybieramy sobie nasz punkt: P = (1,-1,1), który jest na zewnątrz.

wyliczamy 4 wektory:
PA(0,-2,0); PB(2,0,0); PC(0,0,2); PD(2,-2,2)

i teraz wyliczamy 4 objętości - z iloczynu mieszanego wektorów, czyli takie coś: (a x b)c = 1/6 V:

1-2-3 -> wektory trzeba wybierać cyklicznie!
0 -2 0
2 0 0 = 8
0 0 2

2-3-4:
2 0 0
0 0 2 = 8
2 -2 2

3-4-1:
0 0 2
2 -2 2 = -8
0 -2 0

no i już wiemy że P leży na zewnątrz, bo znaki są różne.

4-1-2:
2 -2 2
0 -2 0 = 8
2 0 0

1 użytkowników online, w tym zalogowanych: 0, gości: 1