Punkt innerhalb von Dreieck/Viereck?

Neue Frage »

Paulchen Panther Auf diesen Beitrag antworten »
Punkt innerhalb von Dreieck/Viereck?
ich habe keine ahnung, ob es dazu schon einen thread gibt:

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:
  • ich gebe die gleichungen der trägergeraden der dreiecks-/vierecksseiten in der form y=kx+d an.
  • ich stelle drei halbebenen auf, die jeweils von den trägergeraden der dreiecks-/vierecksseiten begrenzt sind, sodass der jeweils nicht auf dieser geraden liegende punkt in dieser halbebene liegt. ich erhalte also drei ungleichungen der form y<kx+d bzw. y>kx+d.
  • nun überprüfe ich für den punkt, von dem ich wissen möchte, ob er innerhalb des dreiecks/vierecks liegt, ob er alle diese drei ungleichungen erfüllt; wenn ja, dann liegt er innerhalb des dreiecks/vierecks, wenn nein, dann eben nicht


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)
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)
Bloodman Auf diesen Beitrag antworten »

edit: damit kann man nicht gut zeichenen
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,
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
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

Zitat:
Original von Paulchen Panther
[*]ich stelle drei halbebenen auf, die jeweils von den trägergeraden der dreiecks-/vierecksseiten begrenzt sind, sodass der jeweils nicht auf dieser geraden liegende punkt in dieser halbebene liegt. ich erhalte also drei ungleichungen der form y<kx+d bzw. y>kx+d.
[*]nun überprüfe ich für den punkt, von dem ich wissen möchte, ob er innerhalb des dreiecks/vierecks liegt, ob er alle diese drei ungleichungen erfüllt; wenn ja, dann liegt er innerhalb des dreiecks/vierecks, wenn nein, dann eben nicht


zu verzahnen, dann kann das durchaus effektiv sein (habe ich selbst mal vor Jahren so ähnlich programmiert).
 
 
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.)
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
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »