[gelöst] Punkt im Dreieck?

habichthugo · 26. Oktober 2006

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)?

-> Lösung

dmh · 26. Oktober 2006

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*

pram · 26. Oktober 2006

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

knebb · 26. Oktober 2006

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?

Code

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

fabo · 26. Oktober 2006

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

fabo · 26. Oktober 2006

Hier findest du z.B. den ccw-Algorithmus.

Grüsse,

Frank

knebb · 26. Oktober 2006

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

habichthugo · 26. Oktober 2006

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...

ARK · 26. Oktober 2006

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

habichthugo · 26. Oktober 2006

Code

int 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;
...

Alles anzeigen

...tut devinitiv nicht!

habichthugo · 26. Oktober 2006

dito mit

Code

...
   return abs(ccw(x,y,x1,y1,x2,y2)+ccw(x,y,x2,y2,x3,y3)+ccw(x,y,x3,y3,x1,y1)) == 3;
...

...übrigens auch nicht!

habichthugo · 26. Oktober 2006

Oha! Sonderbedingungen für ccw == 0 vergessen!? Weiter nach dem Mittagessen...

Fridi · 26. Oktober 2006

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

habichthugo · 26. Oktober 2006

Code

...
    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;
...

Alles anzeigen

Nö, tut auch mit Ausnahmebehandlung nich!?
Wo liegt der Fehler?

pram · 26. Oktober 2006

also ich würde jetzt behaupten, folgendes funktioniert:

Code

function 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;
}

Alles anzeigen

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

reini1305 · 26. Oktober 2006

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

fabo · 26. Oktober 2006

Zitat

Original von habichthugo

Code

...
    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;
...

Alles anzeigen

Nö, tut auch mit Ausnahmebehandlung nich!?
Wo liegt der Fehler?

Ich würde sagen, wenn du die Zeilen

Code

ccw(x,y,x2,y2,x3,y3)

durch

Code

ccw(x2,y2,x3,y3,x,y)

ersetzst, sollte es funktionieren.

fabo · 26. Oktober 2006

pram:

Zitat

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!

Dies sollte im ccw bereits geprüft sein, d.h. ccw(p1,p2,p)==0 nur dann, wenn p AUF p1p2 liegt.

Grüsse,

Frank

fabo · 26. Oktober 2006

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

habichthugo · 26. Oktober 2006

Zoo geht dat (z.B.):

Code

// 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;
}

Alles anzeigen

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!
:]:]:]:]:]:]:]

[gelöst] Punkt im Dreieck?

Jetzt mitmachen!

Teilen

Benutzer online in diesem Thema