Mal ne potentiell VDR-freie Fragestellung:
Gegeben ist das Dreieck A(x1,y1), B(x2,y2), C(x3,y3) und der Punkt P(x,y) in karthesischen Koordinaten. Die Frage ist nun wie man (mit trivialem C/++-Code) herausfinden kann, ob P im Dreieck (incl. seiner Kanten) liegt, oder ausserhalb.
Das Ganze sollte mit linearen Gleichungen (ohne trigonometrische Funktionen) gehen, aber ich bin zu dumm für die Herleitung. Ich habe u.a. das hier dazu gefunden. Zumindest der zweite Alkoholismus funzt aber net (auch wenn man die Bedingung 'q <= 1' nach 'q >= 0' korrigiert)...
Hat irgend jemand ne funktionierende Lösung dafür (möglichst mit Herleitung)?
[gelöst] Punkt im Dreieck?
- habichthugo
- Geschlossen
-
-
Wir hatten so ein Problem mal mit Punkt in Polygon. Such doch vielleicht mal danach und dann hast Du eben ein Polygon, welches nur aus drei Punkten besteht. Lösungen kann ich Dir leider nicht geben, aber vielleicht hilft dieser Hinweis... *goodluck*
-
Du brauchst einen "Liegt rechts von Gerade" Algorithmus:
Google->LiegtRechtsVon
Wenn der Punkt rechts von allen 3 Geraden liegt, ist er im inneren.
Gruß
Roland -
Zitat
Original von pram
Wenn der Punkt rechts von allen 3 Geraden liegt, ist er im inneren.
Bin ich da jetzt auf dem falschen Dampfer?
Hier liegt der Punkt "P" rechts von allen drei begrenzenden Geraden des Dreiecks- aber nicht innerhalb....habichthugo:
Stammen die Koordinaten aus der Menge der natürlichen Zahlen |N ?
Oder darf es auch rational (|R) sein? Postiv oder auch Negativ? |R ist deutlich einfacher...also |R.[Gedankenmodell ON]
Annahmen: X1=7;3,5 X2=0,0 X3=10;2
Ich würde zuerst einmal feststellen, welche Koordinaten auf den drei Geraden liegen. Dazu kannst Du die Geraden als Funktion ausdrücken. Für die Gerade G12 wäre das also f(x)=0,5x; für G13 f(x)=0,2x und für G23 f(x)=-0,5x+7. Die Funktionen lassen sich ja einfach berechnen.
Daraus kannst Du für einen gegebenen Punkt feststellen, ob er über oder unter einer der Geraden liegt.
Ein Punkt liegt nun im genau dann im Dreieck, wenn er die folgende Bedingung erfüllt ist:
Er liegt ÜBER GENAU EINER Geraden und UNTER den anderen beiden.Müßte so hinkommen
pram: Ist auch nichts groß anderes, als das "RechtsvonderGeraden", nur daß Deine Bedingung falsch formuliert war.Wenn's nicht stimmt: selbst optimieren
-
Hi habichthubo!
Suche mal nach dem ccw-Algorithmus von Robert Sedgewick, der gibt an, ob ein Punkt rechts oder links von der Geraden liegt (ccw=couterclockwise).
ccw liefert -1,0,1 (0=auf der Linie)
Dann ist der Punkt (echt) innerhalb, wenn
abs(Summe(ccw(A,B,P)+ccw(B,C,P)+ccw(C,A,P)))=3 ist.
(Das heißt nicht anderes als daß immer -1 oder immer 1 raus kommt, also immer auf der gleichen Seite).Sonderfälle wie Punkt auf Linie sind natürlich gesondert zu behandeln.
knebb: In deinem Beispiel hast du die Orientierung der Geraden außer Acht gelassen. Du musst die Geraden durch die Punkte AB,BC und CA betrachten.
Grüsse,
Frank
-
-
Zitat
Original von fabo
knebb: In deinem Beispiel hast du die Orientierung der Geraden außer Acht gelassen. Du musst die Geraden durch die Punkte AB,BC und CA betrachten.
Stimmt, man muß vorher noch feststellen, welcher der beiden Punkte der drei Geraden "weiter rechts" ist. Dann kann man erst die Funktion bestimmen.Aber sonst paßt das
-
knebb
...ganz 'normale', reelle Zahlen (double)...LiegtRechtsVon...ccw habe ich durchetestet. Tun nicht, oder ich bin zu blöd. Eventuell liegt's einfach daran, dass die Punkte bzw. Kanten geeignet sortiert sein müssen? Könnte mal einer der Weisen hier den Algorithmus komplett (in Cisch nebst Ausnahmebehandlung etc.)wiedergeben?
Ich habe hier ein schönes Delaunay-Netz zum austesten... -
Zitat
Original von knebb
Stimmt, man muß vorher noch feststellen, welcher der beiden Punkte der drei Geraden "weiter rechts" ist. Dann kann man erst die Funktion bestimmen.Aber sonst paßt das
Wenn man - wie von fabo vorgeschlagen - nur auf "alle drei rechts" oder "alle drei links" prüft, braucht man die Punkte vorher nicht zu sortieren, dann tut's nämlich jede Reihenfolge.
Gruß,
ARK -
Code
Alles anzeigenint ccw(double x0, double y0, double x1, double y1, double x2, double y2 ) { int dx1, dx2, dy1, dy2; dx1 = x1 - x0; dy1 = y1 - y0; dx2 = x2 - x0; dy2 = y2 - y0; if (dx1*dy2 > dy1*dx2) return +1; if (dx1*dy2 < dy1*dx2) return -1; if ((dx1*dx2 < 0) || (dy1*dy2 < 0)) return -1; if ((dx1*dx1+dy1*dy1) < (dx2*dx2+dy2*dy2)) return +1; return 0; } ... return abs(ccw(x1,y1,x2,y2,x,y)+ccw(x2,y2,x3,y3,x,y)+ccw(x3,y3,x1,y1,x,y)) == 3; ...
...tut devinitiv nicht!
-
-
Oha! Sonderbedingungen für ccw == 0 vergessen!? Weiter nach dem Mittagessen...
-
Wie wäre es, wenn du für alle drei Seiten des Dreiecks mit ccw testest, ob der gesuchte Punkt und der Punkt des Dreiecks der nicht für die Gerade gebraucht wurde jeweils auf der gleichen Seite liegen? Dann hat man das Problem mit Links und Rechts nicht.
Gruß,
Fridi -
Code
Alles anzeigen... int n = 0; int c; c = ccw(x,y,x1,y1,x2,y2); if (c == 0) return true; if (c > 0) n++; else n--; c = ccw(x,y,x2,y2,x3,y3); if (c == 0) return true; if (c > 0) n++; else n--; c = ccw(x,y,x3,y3,x1,y1); if (c == 0) return true; if (c > 0) n++; else n--; return abs(n) == 3; ...
Nö, tut auch mit Ausnahmebehandlung nich!?
Wo liegt der Fehler? -
also ich würde jetzt behaupten, folgendes funktioniert:
Code
Alles anzeigenfunction LRV(p, q, r) { w := (q.x–p.x)*(r.y–p.y) – (r.x–p.x)*(q.y–p.y); if w > 0 return 1; if w < 0 return -1 return 0; } function ImDreieck(a,b,c,p) { res=LRV(a,b,p) + LRV(b,c,p) + LRV(c,a,p); return abs(res) == 3; }
LRV müsste äquivalent mit ccw sein (hab den einfach aus meinem Info-Skript so übernommen)
wenn alle 3 Punkte dann rechts (oder links, je nach Umlaufsinn) liegen, ist er im Dreieck.in deinem Code sehe ich gerade dass du noch prüfst ob er AUF der Gerade liegt. Da eine Gerade unendlich lang ist, kann er auch ausserhalb des Dreiecks auf der Gerade liegen!
Gruß
Roland -
Vielleicht darf ich auch noch meinen Senf dazu geben: Ich erinner mich gerade wieder an eine Vorlesung im letzten Semester "Geometrische Algorithmen". Dabei haben wir auch den sogenannten "point-location" Algo durchgemacht.
Bitte sich den Anhang anzusehen:
Nehmen wir an, dass der Punkt q die Koordinaten qx und qy hat. Nun schneidet man die Gerade y=qy mit allen Kanten des Dreiecks und zählt die Schnittpunkte rechts von q.
Ist die Anzahl gerade liegt der Punkt außerhalb, bei ungerade innerhalb. Funktioniert mit beliebigen geschlossenen Polygonen.
Die einzige Ausnahme die mir einfällt ist, wenn man genau durch den obersten oder untersten Eckpunkt schneidet.
HTH
reini1305 -
Zitat
Original von habichthugo
Code
Alles anzeigen... int n = 0; int c; c = ccw(x,y,x1,y1,x2,y2); if (c == 0) return true; if (c > 0) n++; else n--; c = ccw(x,y,x2,y2,x3,y3); if (c == 0) return true; if (c > 0) n++; else n--; c = ccw(x,y,x3,y3,x1,y1); if (c == 0) return true; if (c > 0) n++; else n--; return abs(n) == 3; ...
Nö, tut auch mit Ausnahmebehandlung nich!?
Wo liegt der Fehler?Ich würde sagen, wenn du die Zeilen
durch
ersetzst, sollte es funktionieren. -
-
Zitat
Original von pram
LRV müsste äquivalent mit ccw sein (hab den einfach aus meinem Info-Skript so übernommen)
wenn alle 3 Punkte dann rechts (oder links, je nach Umlaufsinn) liegen, ist er im Dreieck.LRV ist identisch mit dem 1. Teil von ccw. Es wird nicht geprüft, ob der Punkt auf der LINIE liegt, nur auf der GERADEN !
Grüsse,
Frank
-
Zoo geht dat (z.B.):
Code
Alles anzeigen// Punkt liegt 'links' (oberhalb), 'rechts' (unterhalb), auf der Strecke oder der Geraden // -1 -> links der Geraden // 0 -> auf der Geraden (ausserhalb der Strecke) // 1 -> rechts der Geraden // 2 -> auf der Strecke int PointRelationToLine( double x, // Punkt double y, // .. double x1, // Strecke Punkt 1 double y1, // .. double x2, // Strecke Punkt 2 double y2 // .. ) { double dx1, dx2, dy1, dy2; dx1 = x1 - x; dy1 = y1 - y; dx2 = x2 - x; dy2 = y2 - y; if (((dx1 == 0) && (dy1 == 0)) || ((dx2 == 0) && (dy2 == 0))) return 2; double dx1dy2 = dx1*dy2; double dy1dx2 = dy1*dx2; if (dx1dy2 > dy1dx2) return 1; if (dx1dy2 < dy1dx2) return -1; if ((dx1*dx2 < 0) || (dy1*dy2 < 0)) return -1; if ((dx1*dx1+dy1*dy1) < (dx2*dx2+dy2*dy2)) return 1; if ((((dx1 >= 0) && (dx2 <= 0)) || ((dx1 <= 0) && (dx2 >= 0))) && ((dx1 != 0) || (dx2 != 0))) return 2; if ((((dy1 >= 0) && (dy2 <= 0)) || ((dy1 <= 0) && (dy2 >= 0))) && ((dy1 != 0) || (dy2 != 0))) return 2; return 0; } bool PointInTriangel( double x, // Punkt double y, // .. double x1, // Dreieck Punkt 1 double y1, // .. double y2, // Dreieck Punkt 2 double x2, // .. double y3, // Dreieck Punkt 3 double x3 // .. ) { // Der Punkt muss (3*) 'rechts' oder (3*) 'links' aller drei Seiten des Dreiecks liegen // oder direkt auf einer der Strecken bool bRight; switch (PointRelationToLine(x,y,x1,y1,x2,y2)) { case 0: return false; case 2: return true; case 1: bRight = true; break; default: bRight = false; break; } switch (PointRelationToLine(x,y,x2,y2,x3,y3)) { case 0: return false; case 2: return true; case 1: if (!bRight) return false; break; default: if (bRight) return false; break; } switch (PointRelationToLine(x,y,x3,y3,x1,y1)) { case 0: return false; case 2: return true; case 1: if (!bRight) return false; break; default: if (bRight) return false; break; } return true; }
Man muss die Fälle, wo der Punkt auf eine der Geraden bzw. Strecken der Dreieckskanten liegt, sauber behandeln bzw. auseinander halten, sonst wird's nix.
:]:]:]:]:]:]:]
Danke @All!
:]:]:]:]:]:]:]
Jetzt mitmachen!
Sie haben noch kein Benutzerkonto auf unserer Seite? Registrieren Sie sich kostenlos und nehmen Sie an unserer Community teil!