Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

Prüfen ob Polygon im R³ konvex ist

Werbeanzeige

Phil_GDM

Alter Hase

  • »Phil_GDM« ist der Autor dieses Themas

Beiträge: 443

Wohnort: Graz

Beruf: Student-Softwareentwicklung u. Wissensmanagement

  • Private Nachricht senden

1

24.02.2009, 14:14

Prüfen ob Polygon im R³ konvex ist

Wie der Titel schon sagt, suche ich eine Möglichkeit zu überprüfen,
ob ein Polyxgon im R³ konvex ist.

Google liefert mir immer nur Ergebnisse für Polygone im R².

Hat jemand von euch einen Algorithmus parat?

mfg Philipp

TrommlBomml

Community-Fossil

Beiträge: 2 117

Wohnort: Berlin

Beruf: Software-Entwickler

  • Private Nachricht senden

2

24.02.2009, 14:26

so auf anhieb eigentlich genauso wie im 2-dimensionalen raum: prüfen aller innenwinkel auf maximal rechter winkel.

David Scherfgen

Administrator

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

3

24.02.2009, 15:11

Re: Prüfen ob Polygon im R³ konvex ist

Zitat von »"Phil_GDM"«

Wie der Titel schon sagt, suche ich eine Möglichkeit zu überprüfen,
ob ein Polyxgon im R³ konvex ist.

Google liefert mir immer nur Ergebnisse für Polygone im R².

Hat jemand von euch einen Algorithmus parat?

Wie soll denn ein Polygon im R³ aussehen? Das ergibt für mich keinen Sinn. Die Punkte müssen doch alle auf einer Ebene liegen, was das Polygon dann wieder 2-dimensional macht.
David Scherfgens Website | Konzentrationstest Polizei

David_pb

Community-Fossil

Beiträge: 3 886

Beruf: 3D Graphics Programmer

  • Private Nachricht senden

4

24.02.2009, 15:12

Du kannst auch für jeden Vertex testen ob die anderen Vertices entsprechend vor dem Vertex liegen.

Phil_GDM

Alter Hase

  • »Phil_GDM« ist der Autor dieses Themas

Beiträge: 443

Wohnort: Graz

Beruf: Student-Softwareentwicklung u. Wissensmanagement

  • Private Nachricht senden

5

24.02.2009, 15:40

@TrommelBomml: du meinst wohl: 0° <= Winkel <= 180°. Der Winkel zwischen zwei Vektoren ist aber immer 0° <= Winkel <= 180°. Daher kann ich das nicht machen. Ausser man würde zusätlich noch Orientierung des Kreuzprodukts miteinbeziehen usw.

@David Scherfgen: Ja die Punkte liegen schon auf einer Ebene, diese liegt aber im R³. Damit ich die bekannten 2D-Verfahren andwenden kann, müsste ich diese Ebene doch zuerst so projezieren, dass sie auf einer der Ebenen des Achsensystems liegt. Oder denke ich da zu kompliziert?

@David_pb: Jop genau die Info, die ch brauchte. Damit kann ich wieder prüfen ob der Winkel > 180° ist. Thx.

mfg Philipp

David Scherfgen

Administrator

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

6

24.02.2009, 15:46

Zitat von »"Phil_GDM"«

@David Scherfgen: Ja die Punkte liegen schon auf einer Ebene, diese liegt aber im R³. Damit ich die bekannten 2D-Verfahren andwenden kann, müsste ich diese Ebene doch zuerst so projezieren, dass sie auf einer der Ebenen des Achsensystems liegt. Oder denke ich da zu kompliziert?

So ist es. Wo ist da das Problem? Rechne die Ebene aus und bestimme dann zwei willkürliche nicht-parallele Vektoren in dieser Ebene, die dein 2D-Koordinatensystem aufspannen. Dann kannst du die Punkte des Polygons in diesem 2D-Koordinatensystem ausdrücken - fertig.
David Scherfgens Website | Konzentrationstest Polizei

Phil_GDM

Alter Hase

  • »Phil_GDM« ist der Autor dieses Themas

Beiträge: 443

Wohnort: Graz

Beruf: Student-Softwareentwicklung u. Wissensmanagement

  • Private Nachricht senden

7

24.02.2009, 17:26

Zitat von »"David Scherfgen"«


So ist es. Wo ist da das Problem?


Dass ich nachdem meine letzte Mathe VO schon einige Semester zurück liegt viel zu wenig Plan von linearer Algebra habe, um dass auf die Reihe zu kriegen.

Ich meine mich zu erinnnert, dass wir ähnliche Sachen bereits gemacht haben. Das war aber immer ziemlich aufwändig... Eigenvektoren/Eigenwerte bestimmen, orthoganale Basisvektoren ausrechenen usw....

Da versuch ich es vorher lieber mit dem Ansatz von David_pb

mfg Philipp

knivil

Treue Seele

Beiträge: 383

  • Private Nachricht senden

8

25.02.2009, 13:07

Wenn alle Punkte in einer Ebene liegen kannst du einfach die Winkel an den Punkten bestimmen (Skalarprodukt im 3D) und keiner sollte groesser als 180 Grad sein. Ist so wie der LeftOf-Test beim berechnen der konvexen Huelle.

Quellcode

 
1
2
3
4
5
6
7
8

// true <=> this point lies on the left side of line(p1,p2)
// false otherwise
bool Point::leftOf(const Point& p1, const Point& p2) const
{
    Point r(*this - p1);
    Point q(p2 - p1);
    return (q.m_x*r.m_y - q.m_y*r.m_x) > 0;
}

In der return-Zeile steht das skalarprodukt im 2D, kann natuerlich leicht durch das im 3D ersetzt werden. Jeder Punkt des Polygons muss links von seinen 2 Vorgaengern liegen. Ob nun > oder >= benutzt wird, ist kontextabhaengig.

PS: Ob's ne Methode von Point sein soll oder nicht, ist Geschmackssache.
If it were not for laughter, there would be no Tao.

Werbeanzeige