Entwickler-Ecke :: Thema anzeigen - Der Punkt im Dreieck

Kaspall - Mi 16.03.11 14:09
Titel: Der Punkt im Dreieck

Hallo Delphi-Freunde, ich verzweifle seit gestern abend an einer recht einfach klingenden Problem das sich bei meinem derzeitigen Delphi-projekt in den Weg stellt und ich weiß nicht weiter.

Also folgendes: Ich versuche derzeit einen algorithmus zu schreiben der erkennt ob sich ein Punkt in einem Dreieck befindet.
Stellt euch einfach ein Koordinatensystem mit einem Dreieck vor und dann wird irgendwo ein Punkt hingesetzt. Egal ob im Dreieck, oder ausserhalb.
Wir wissen die Koordinaten der 3 Eckpunkte des Dreiecks

x1, x2, x3
y1, y2, y3

und die des Punktes natürlich.

xp, yp

Es gibt zwar einen mathematischen Weg, aber da benötige ich Gleichungen...und wie bitte soll ich in Delphi Gleichungen lösen? HEUL!
ich brauch einfach eine Funktion die am ende sagt..true (also Punkt befindet sich im Dreieck) oder eben false, dann halt nicht^^
Aber ich scheiß hier seit gestern erfolglos herum und komm nicht weiter, also fals wer Lösungsvorschläge hat wie ich das in Delphi angehen könnte, bitte hier posten.
Danke schon mal im Vorraus.

-Kaspall

ALF - Mi 16.03.11 14:40

geh mal die Sache anders rum an.
Frage den Punkt ab ob seine x,y position innerhalb von x1,y1,z1 ist.
Da die Werte ja bekannt sind.
Etwa so:

Delphi-Quelltext

1:	if (position(x,y) = position(z1,x1)) and (position(x,y) = position(z1,y1)) then

Mal so als idee.

Alf

Kaspall - Mi 16.03.11 14:54

Also um mich zu ergänzen: Der mathematische Weg wäre: Eine senkrechte und eine waagrechte Gerade durch den Punkte legen, und dann die Geraden mit den Linien des Dreiecks schneiden, sollten sich 4 Schnittpunkte ergeben und die jeweils oben/unten bzw links und rechts vom Punkt liegen befindet er sich im Dreieck. Auf einem Zettel würd ich das mit Geradengleichungen lösen die ungefähr so aussehen:

y=23x+1

und dann noch eine Geradengleichung von der Linie.

y=0.5x + 232

(alles nur als Beispiele)

Dann würde man das y gleichsetzen mit

23x + 1 = 0.5x + 232
und daraus x berechnen(und mit x dann y) was dann die Koordinaten des Schnittpunkts ergeben würden.
=========================

Das wäre mal meine Idee so gewesen, nur wie soll ich das in Delphi umsetzen^^

Ich glaub nämlich es gibt für das Problem eine total simple Lösung, nur denke ich einfach zu kompliziert^^

Kaspall - Mi 16.03.11 15:08

Ich versteh deinen Weg ehrlich gesagt nicht wirklich...
Was ich da so verstehe meinst du ich solle überprüfen ob sich der Punkt INNERHALB der Punkte befindet, also x und y-mäßig zwischen den Punkten.
Aber ich glaub das würde nur prüfen ob sich der Punkt innerhalb eines Rechtecks befindet das du dann über das Dreieck drüberlegst.

ALF - Mi 16.03.11 15:35

oobs, habe ich mich soo blöd ausgedrückt :gruebel:
Dann nehme ich es zurück.

€: Obwohl bezogen auf den Link von Kha
zum Schluss kommt der if vergleich, nähmlich ob P nun unter ab ist oder über ab und dann noch der Rest ac,bc. Was ist also da so verkehrt von meinem Beispiel, ausser das ich auf gleich Prüfe.
Es ist zwar keine mathematisch Formel aber ein vergleich wo sich der Punkt befindet.

mh...:gruebel:
Alf

ALF - Fr 18.03.11 14:14

Ich Pushe mal um Missverständnisse auszuräumen (sorry also)

Kha hat folgendes geschrieben :

Kaspall hat folgendes geschrieben :

Ich versteh deinen Weg ehrlich gesagt nicht wirklich...

Da schließe ich mich an ;) .

bei NonVCL brauch ich natürlich eine Formel unbestritten.

Ich bezog meine Aussage:

ALF hat folgendes geschrieben :

geh mal die Sache anders rum an.
Frage den Punkt ab ob seine x,y position innerhalb von ...
So als Idee

Da die einzelnen Punkte, bezogen auf den Bildschirm, Coordinaten haben.
Also rein Visuel
Denn,
P hat eine Position P(x,y)
A hat eine Position A(x,y)
B hat eine Position B(x,y)
C hat eine Position C(x,y) auf dem Bildschirm.

Nun zur Lösung: rein Visuel!

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:

if ((P.x >= A.x) and (P.x <= B.x)) or ((P.y >= A.y) and (P.y <= B.y)) then
    // P befindet sich innerhalb der Strecke von AB, nun Prüfe P mit strecke AC
else//P befindet sich nicht innerhalb der Strecke von AB kann aber trotzden im Dreick sein
If (P.x >= A.x) and (P.x <= C.x) then
   //im dreieck
else
  //nicht im Dreieck

ist nicht komplett oder auch nicht schön, aber machbar!
Das habe ich gemeint.
Natürlich sind Formeln immer das beste!
(Ich bin kein Freund von Formeln) darum diesen Vorschlag
Denn so viel ich weiss, wird so auch abgefragt, ob die Maus sich über eine VCL befindet.
Hoffentlich nicht wieder so blööd ausgedrückt :mrgreen:

Gruss ALf

Kha - Fr 18.03.11 14:48

Sorry, aber wenn ich das richtig sehe, werden deine Formeln hinten und vorne nicht hinhauen :nixweiss: . Ohne die Anwendung von Vektorrechung oder Geradengleichungen dürfte das Problem nicht lösbar sein.

ALF hat folgendes geschrieben :

Denn so viel ich weiss, wird so auch abgefragt, ob die Maus sich über eine VCL befindet.

Für achsenparallele Rechtecke reichen solche Ungleichungen natürlich aus, aber davon sind wir hier weit entfernt ;) .

ALF - Fr 18.03.11 15:06

Darum hab ich ja auch geschrieben, rein NONVCL benötige ich ne Formel, da ich keine visulle Koordinaten habe.
Wenn ich mir einen dreieckigen Button mache, werd ich bestimmt nicht so eine Formel auf setzten um zu wissen ob die Maus innerhalb des dreieckigen Button ist. Kann ich mir nicht vorstellen :gruebel:

Gruss ALf

Gausi - Fr 18.03.11 15:13

Was hat das denn mit VCL oder NonVCL zu tun? :gruebel: Die Frage ist, wie man feststellen kann, ob ein Punkt in einem Dreieck liegt oder nicht. Da muss man halt ein bissel rumrechnen (Skalarprodukt, Kreuzprodukt, etc.pp.). Da gibts ja weiter oben einen schönen Link.

Wenn Windows (oder die VCL) nicht das Dreieck checkt, sondern das kleinste umliegende achsenparallele Rechteck - ok. Ist da ja auch ggf. sinnvoll, da fast alle Controls nunmal solche Rechtecke sind.

Martok - Fr 18.03.11 17:32

:gruebel:

Warum macht ihr euch das so kompliziert? PointInPolygon [http://www.efg2.com/Lab/Library/Delphi/Graphics/Math.htm#PointInPolygon] und wenn das zu langsam sein sollte, kann man immer noch optimieren. Kommt vor allem vollständig ohne Vektorarithemtik aus, dürfte also erstmal schneller sein als user profile icon

Kha's Ansatz.

Aber da in diesem Thread irgendwie alle ein Problem damit haben sich vernünftig auszudrücken (:lol:) ist mir nicht so ganz klar was der OP eigentlich will ;)

Xion - Fr 18.03.11 17:38

Kaspall hat folgendes geschrieben :

Es gibt zwar einen mathematischen Weg, aber da benötige ich Gleichungen...und wie bitte soll ich in Delphi Gleichungen lösen? HEUL!

Kaspall hat folgendes geschrieben :

Auf einem Zettel würd ich das mit Geradengleichungen lösen die ungefähr so aussehen:

y=23x+1

und dann noch eine Geradengleichung von der Linie.

y=0.5x + 232

(alles nur als Beispiele)

Dann würde man das y gleichsetzen mit

23x + 1 = 0.5x + 232
und daraus x berechnen(und mit x dann y) was dann die Koordinaten des Schnittpunkts ergeben würden.

Das kannst du in Delphi auch. Nur halt etwas allgemeiner:

y=a*x+b
y=c*x+d

=> a*x+b=c*x+d
=> (a-c)*x=d-b
=> x=(d-b)/(a-c)

Also:

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:

Function myFormula(a,b,c,d: integer): real;
begin
  if a-c<>0 then
    Result:=(d-b)/(a-c)
  else
    System.Explode;
end;

Aufruf:

Delphi-Quelltext

1:	myForumla(23,1,0.5,232);

Horst_H - Sa 19.03.11 15:28

Hallo,

für TurboPascal hatte ich mal eine Frage nach einem Punkt ( Mausklick ) in einer Raute beantwortet.
Wie bei Kha's Link unten beschrieben, besteht es im Prinzip aus einer Basisumwandlung, wobei die Basisvektoren des neuen Koordinatensystems zwei Seiten des Dreiecks sind.
Ich habe mal auf einem Image durch Abfrage aller Punkte zufällige Dreiecke zeichnen lassen, wobei für das Dreieck vorab konstante Faktore zur schnellen Bestimmung berechnet werden.

Gruß Horst

Waldheini - Mo 21.03.11 22:58

Hallo,

Du kannst berechnen, ob der Punkt im Dreieck liegt, wenn Du mit dem Punkt und den Dreieckpunkten drei neue Dreiecke bildest und den Kreuzvektor der Dreiecke berechnest. Sind alle Kreuzvektoren positiv, oder alle negativ, ist der Punkt im Dreieck:

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:

function PunktImDreieck(X1,Y1,X2,Y2,X3,Y3,Px,Py: Single): Boolean;
var a,b,c: Single;
begin
// erstes Dreieck ist X1/Y1, X2/Y2 und Px/Py:
a:= ((X1-X2)*(Y1-Py))-((Y1-Y2)*(X1-Px));
// zweites Dreieck ist X2/Y2, X3/Y3 und Px/Py:
b:= ((X2-X3)*(Y2-Py))-((Y2-Y3)*(X2-Px));
// drittes Dreieck ist X3/Y3, X1/Y1 und Px/Py:
C:= ((X3-X1)*(Y3-Py))-((Y3-Y1)*(X3-Px));
// der Punkt liegt im Dreieck, wenn a und b und c positiv, oder a und b und c negativ sind:
Result:= ((a > 0) and (b > 0) and (c > 0))
      or ((a < 0) and (b < 0) and (c < 0));
end;

Mr_Emre_D - Sa 02.04.11 14:34

@Waldheini - Kannst du auch eine Begründung abgeben?

Ich wollte noch vorschlagen, zu schauen, ob die Winkel APB, BPC, APC aufaddiert 360° ergeben. Falls nicht, dann ist der Punkt nämlich nicht im Kreis.
Diese Methode ist aber langsamer als die im vorigen Post beschriebene, weil man hier zuerst die Winkel per ArcCos ermitteln muss!

Waldheini - Sa 02.04.11 20:33

Mr_Emre_D hat folgendes geschrieben :

@Waldheini - Kannst du auch eine Begründung abgeben?

Stell Dir vor, Du gehst das Dreieck entlang von Punkt1 zu Punkt2 und Punkt 3 und wieder zu Punkt 1. Dabei beobachtest Du den Punkt. Ist der Punkt immer auf deiner linken, oder rechten Seite, so kann er nur im Dreieck liegen. Dadurch, das mit jeweils einer Seite des Dreiecks und dem Punkt ein neues Dreieck gebildet wird, kann über das Kreuzprodukt (nicht Vektor, mein Fehler!) festgestellt werden, wo der Punkt liegt.

Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!