Punkt innerhalb von Dreieck/Viereck? |
30.12.2004, 11:34 | Paulchen Panther | Auf diesen Beitrag antworten » | ||
Punkt innerhalb von Dreieck/Viereck? ich möchte (im R²) rechnerisch ermitteln, ob sich ein punkt, dessen koordinaten bekannt sind, innerhalb eines durch die koordinaten der eckpunkte gegebenen dreiecks/vierecks befinden. interessieren würde mich hier ein verfahren, welches sich allgemein anwenden lässt und auch in ein computerprogramm umsetzbar ist. mir ist dazu folgendes eingefallen:
nun ist es zwar möglich, dieses verfahren zu programmieren, aber ich frage mich, ob es nicht ein schnelleres verfahren gibt, dass zu demselben ergebnis führt. das schöne an diesem verfahren ist jedenfalls, dass es sich für beliebige vielecke mit innenwinkeln < 180° erweitern lässt. anwendung finden soll dieses verfahren, um festzustellen, ob ein viereck ein dreieck umschließt, ob dieses dreieck das viereck umschließt, oder ob das dreieck außerhalb des vierecks liegt, ohne dieses zu umschließen; den fall, dass es schnittpunkte zwischen dreiecks- und vierecksseiten gibt, habe ich in meinem programm bereits ausgeschlossen (da ich in diesem fall die schnittpunkte berechnen muss, führe ich dies durch; wenn es keine schnittpunkte gibt, muss einer der anderen fälle vorliegen) |
||||
30.12.2004, 12:04 | Bloodman | Auf diesen Beitrag antworten » | ||
wenn es keine schnittpunkte gibt dann nimmst du eine stecke des dreiecks her und machst di zu einer geraden wenn die gerade keine dieser stecken schneidet liegt es außerhalb wenn die grade ungrade anzahl von schnitpunkten hat nimmst du eine eine andere punkt kombination her wenn die schnitte beide "links" oder "rechts" der stecke liegen dann liegt es außerhalb wenn es jeweil links und recht ligt dann innerhalb wenn es 4 schnitpunkte gibt dann wähle eine andere strecke (punktkombination) |
||||
30.12.2004, 12:06 | Bloodman | Auf diesen Beitrag antworten » | ||
edit: damit kann man nicht gut zeichenen |
||||
30.12.2004, 12:15 | pimaniac | Auf diesen Beitrag antworten » | ||
Ich hab mal einen Risikoclon programmiert da hab ich sowas gebraucht... Idee vom bloodman is gut Damals hab ich einfach eine Strecke (keine Gerade!!!) vom gegeben Punkt in irgendeine Richtung genommen und die Anzahl der Schnitpunkte mit den Ländergrenzen gezählt Ungerade= Innerhalb Gerade=Ausserhalb Wichtig: Nimm als Richtung der Strecke irgendetwas Irationales... Da die Richtungen der Grenzen der Länder normalerweise rational sind kann es keine Probelem geben dass die Strecke durch einen Eckpunkt geht oder paralell durch eine Ländergrenez geht, |
||||
30.12.2004, 12:39 | Bloodman | Auf diesen Beitrag antworten » | ||
gerade heitß aber auch durch einen eckpunkt darum sollte er ja in beide richtungen gehen (nur mit 2 schnittpunkten bekomst du ein brauchbares ergebnis (und dessen lage auf der geraden) bei allen anderen fällen kann man ausnahmen konstruieren aber für alle möglichekeiten eine grade zu biden gibt es mindestens eine die die 2 schnittpunkte erfüllt |
||||
30.12.2004, 13:35 | AD | Auf diesen Beitrag antworten » | ||
Vielleicht hilft dir folgende Aussage für die Überprüfung des Falles der Disjunktheit von Drei- und Viereck: Sei A ein konvexes m-Eck und B ein konvexes n-Eck, beide beschrieben als Durchschnitt von m bzw. n Halbebenen. Dann sind A und B genau dann disjunkt, wenn 1) alle n Eckpunkte von B außerhalb einer (festen) der m Halbebenen liegen, welche im Durchschnitt die Figur A bilden, oder 2) alle m Eckpunkte von A außerhalb einer (festen) der n Halbebenen liegen, welche im Durchschnitt die Figur B bilden. Wenn es dir gelingt, das irgendwie mit diesen Berechnungen
zu verzahnen, dann kann das durchaus effektiv sein (habe ich selbst mal vor Jahren so ähnlich programmiert). |
||||
Anzeige | ||||
|
||||
30.12.2004, 13:36 | Leopold | Auf diesen Beitrag antworten » | ||
Wir gehen von einem positiv orientierten n-Eck aus, dessen Eckpunkte die Ortsvektoren besitzen mögen, sowie einem weiteren Punkt (der keiner der Eckpunkte sein soll) mit dem Ortsvektor . Positive Orientierung bedeutet, daß, wenn man den Rand des n-Ecks nach steigenden Indizes der Eckpunkte durchläuft, das Innere zur Linken liegt. Zunächst berechnet man die Winkel zwischen den Vektoren , zum Beispiel mit der Skalarprodukt-Formel Ist , so liegt auf der Strecke . Wir nehmen daher an, daß für alle ist. Jetzt bestimmt man die Orientierung der Dreiecke : und setzt liegt genau dann im Innern des n-Ecks, wenn ist. (Liegt der Punkt im Äußeren des n-Ecks, so ist diese Winkelsumme gleich 0.) (Ich hoffe, daß das alles stimmt. Diese Orientierungsfragen sind nämlich immer recht kniffelig.) |
||||
30.12.2004, 13:45 | riwe | Auf diesen Beitrag antworten » | ||
RE: Punkt innerhalb von Dreieck/Viereck? jede menge literatur findest du bei ottmann/widmayer algorithmen und datenstrukturen sedgewick (geometrische) algorithmen grafiti:schau nach bei grafiti und scan-line ist ein ganz toller geometrie/grafik - link der uni oldenburg werner |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
Die Neuesten » |
|