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

Czy musisz przechowywać wielokąt w postaci tablicy punktów? Jeśli nie, to możesz na przykład od razu trzymać całość w postaci listy wielokątów płaskich. Zamiana tego na punkty jest prostsza niż przejście w drugą stronę. W ogóle - w jakim celu korzystasz z tablicy punktów? A może wcale jej nie potrzebujesz?

>>Czy musisz przechowywać wielokąt w postaci tablicy punktów? Jeśli nie, to możesz na przykład od razu trzymać całość w postaci listy wielokątów płaskich. Zamiana tego na punkty jest prostsza niż >>przejście w drugą stronę. W ogóle - w jakim celu korzystasz z tablicy punktów? A może wcale jej nie potrzebujesz?

>>Czy musisz przechowywać wielokąt w postaci tablicy punktów?
Ja ten wielokąt dostaję do analizy w takiej właśnie postaci.
Wydaje mi się że to iż punkty biegną w kolejności jest sporym ułatwieniem i dodatkową informacją.

>>Jeśli nie, to możesz na przykład od razu trzymać całość w postaci listy wielokątów płaskich.
A tego to wcale nie rozumiem:) możesz rozwinąć?

>>W ogóle - w jakim celu korzystasz z tablicy punktów? A może wcale jej nie potrzebujesz?
Wynikiem finalnym ma być lista wszystkich płaskich powierzchni podana w taki sposób aby możliwe było skonstruowanie i narysowanie tych płaskich powierzchni.

Aktualnie jestem na etapie w którym zrobiłem podział wielokąta na te płaskie powierzchnie ale oprócz tych właściwych, które faktycznie należą do wielokąta mam sporą ilość powierzchni "nadmiarowych" o których pisałem wcześniej.
Na tą chwilę problem sprowadza się do tego jak je odsiać? i nie mam pojęcia.

Zadanie wydaje się proste :)

Jak to jednak prosto wytłumaczyć ?
może zacznijmy od przykładu planarnego

weźmy sobie np. sześciokąt  (sześciokąt 3D prezentujesz na wskazanym rysunku)
1. opisujemy wierzchołki ABCDEFA
2. wybieramy trzy kolejne np. ABC
3. powstały trójkąt odcinamy.
  tu stawiamy pytanie który punkt wypada ? musi to być środkowy ( czyli B ) zostaje nam krawędź AC
4. wybieramy trzy kolejne np. ACD (AC - pozostała krawędź + kolejny sąsiedni punkt np. D i powtarzamy punkty 3, 4

co powoduje, że uzyskamy 4 trójkąty :  ABC, ACD, ADE, AEF

teraz musimy odpowiedzieć sobie na pytanie.
czy mogliśmy wybierać kolejne punkty inaczej ?
oczywiście możemy :
* ABC, FAC, EFC, DEF
* ABC, FAC, FCD, FDE
są to ewidentnie inne trójkąty !

Nie są to wszystkie możliwości, bo wyszło nam to po wyborze w punkcie 1
trzech pierwszych punktów, co ograniczyło inne możliwe rozwiązania.
dlatego do opisania takiego wielokąta w 3D poza samymi punktami musi być informacje na temat punktów łamania

>>Wydaje mi się że to iż punkty biegną w kolejności jest sporym ułatwieniem i dodatkową informacją.
Bez rozstrzygnięcia tego masz problem z określeniem właściwego rozwiązania.

wydaje mi się, że na podstawie tego co zaprezentowałem widzisz już algorytm uzyskania konkretnego rozwiązania lub listy wszystkich możliwych rozwiązań.

Zgodzisz się chyba jednak, że zadanie jest proste :)

Powodzenia !

>>Zadanie wydaje się proste :)
Dokładnie:)

Co do podziału na trójkąty to już zrobiłem jak mówisz, tylko co dalej?
Mam listę tych wszystkich trójkątów i brak jasnego kryterium eliminacji zbędnych powierzchni.

>>Dlatego do opisania takiego wielokąta w 3D poza samymi punktami musi być informacje na temat punktów łamania.
Pytanie jak zdobyć tą informację?

Na razie stoję w miejscu i dalej kombinuje:)

Pozdrawiam.

>>

Cytaty na forum tworzymy za pomocą [cytat]cytowany tekst[/cytat].

Ja ten wielokąt dostaję do analizy w takiej właśnie postaci.

Trudno, czyli nie da się uciec od głównego problemu.

A tego to wcale nie rozumiem:) możesz rozwinąć?

Po prostu myślałem, że na przykład sam sobie możesz wybrać postać, w jakiej cały wielokąt jest zdefiniowany. Ale skoro nie, to trzeba szukać innego sposobu.

Na tą chwilę problem sprowadza się do tego jak je odsiać? i nie mam pojęcia.

A w jakiej postaci masz te wielokąty płaskie? Jeśli w takiej samej, jak główny wielokąt (tablica punktów, którą można traktować również jako listę krawędzi), to możesz spróbować szukać krawędzi, które nie należą do wielokąta. Jeśli wielokąt płaski jest maksymalny (to znaczy nie istnieje żaden punkt leżący na tej samej płaszczyźnie, który można byłoby do niego dołączyć), to taki wielokąt ma wszystkie krawędzie albo należące do głównego wielokąta albo wspólne z innymi wielokątami płaskimi. Szukaj i usuwaj te wielokąty, które mają jakieś krawędzie należące tylko do nich i nienależące do żadnej z krawędzi głównego wielokąta.

Zadanie wydaje się proste

Dobrze powiedziane - wydaje się. Podobnie jak wiele innych problemów matematycznych, które na pierwszy rzut oka wydają się przeznaczone dla dzieci z podstawówki. Rozkład liczb na czynniki pierwsze również wydaje się prosty, dopóki liczby są małe. Ale gdy chodzi o wartości mieszczące się na jednym kilobicie, to taki rozkład jest na tyle trudny, że szyfr RSA jakoś się trzyma.

czy mogliśmy wybierać kolejne punkty inaczej ? oczywiście możemy : * ABC, FAC, EFC, DEF * ABC, FAC, FCD, FDE są to ewidentnie inne trójkąty !

Możesz wybrać inne trójkąty, ale wielokąty płaskie o maksymalnej liczbie kątów będą takie same. Scal ze sobą te trójkąty, które leżą na tej samej płaszczyźnie i zobacz, czy w jakimkolwiek przypadku uzyskasz inny wynik końcowy.

do opisania takiego wielokąta w 3D poza samymi punktami musi być informacje na temat punktów łamania

Nie musi. Krawędzie można traktować jako wektory (czyli mające określony kierunek i zwrot). To powoduje, że jeśli któryś z nich ma niewłaściwy zwrot, to oznacza, że coś jest nie tak. Przykładowo: jeśli masz trójkąt ABC, to A łączy się z B, B prowadzi do C, a C wskazuje na A. Możesz iść w drugą stronę i otrzymać CBA, ale to jedyna możliwość (pomijając sytuacje, gdzie startujesz z innego punktu, ale same wektory są identyczne). Nie da się zrobić tak, aby A łączyło się z B oraz C prowadziło do B. Jeśli tak jest, to znaczy, że dana lista wektorów nie stanowi prawidłowego wielokąta i całość musi być połączona inaczej.

A czy przypadkiem algorytm grafowy Floyda-Warshalla nie był by tutaj właściwy?
Tak się na razie głośno zastanawiam bo dziwnie pasuje mi do tego problemu.
Krawędzie zewnętrzne które posiadam i krawędzie wszystkich wygenerowanych trójkątów mają znany kierunek.
Wagi krawędzi do algorytmu to ich długości w tym przypadku.
Patrzę na te swoje przypadki i wydaje mi się że to podejście powinno odsiać zbędne trójkąty.
Co o tym sądzicie?

Pozdrawiam.

1.
Z samych punktów wielokąta nie da się odczytać punktu łamania.
najprostszy przykład czworokąt
A(-1, 0, 0)
B( 0  1, 1)
C( 1, 0, 0)
D( 0 -1, 1)  
mogą być dwie linie łamania AC lub BC
rysuje sobie oba przypadki i powstają dwa różne wielokąty 3D

2
@garlonicon

Krawędzie można traktować jako wektory ...

Ciekawa idea, zakłada istnienie dodatkowej informacji, której chyba nie ma.

Nie wiem jednak jak zinterpretować przedstawiony wyżej przykład
łamania to AC czy BC ?
 

3.

algorytm grafowy Floyda-Warshalla

Moim zdaniem nie ma związku z problemem.




 

Nie wiem jednak jak zinterpretować przedstawiony wyżej przykład łamania to AC czy BC ?

Decyduje o tym kolejność wstawionych punktów, czyli będzie to krawędź AC.