Autor |
Beitrag |
Kaspall
      
Beiträge: 65
Erhaltene Danke: 10
|
Verfasst: Mi 16.03.11 14:09
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
|
|
Gausi
      
Beiträge: 8548
Erhaltene Danke: 477
Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
|
Verfasst: Mi 16.03.11 14:24
Wie sieht denn der mathematische Weg aus? Die Gleichungen muss man ggf. umformen und dann mit Fallunterscheidungen arbeiten. Gleichungen lösen muss man für das Problem doch nicht direkt, oder irre ich mich da?
_________________ We are, we were and will not be.
|
|
ALF
      
Beiträge: 1085
Erhaltene Danke: 53
WinXP, Win7, Win10
Delphi 7 Enterprise, XE
|
Verfasst: 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
_________________ Wenn jeder alles kann oder wüsste und keiner hätt' ne Frage mehr, omg, währe dieses Forum leer!
|
|
Kaspall 
      
Beiträge: 65
Erhaltene Danke: 10
|
Verfasst: 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^^
|
|
ALF
      
Beiträge: 1085
Erhaltene Danke: 53
WinXP, Win7, Win10
Delphi 7 Enterprise, XE
|
Verfasst: Mi 16.03.11 15:04
Wenn Du natürlich die genaue Position des Punktes relativ zum Dreieck haben willst(ob nun innen oder ausserhalb), kommst Du um eine Gleichuung nicht drum rum.
Wenn Du nur wissen willst ob der Punkt innerhalb des Dreieck ist dann schaue auf das Beispiel von mir.
ALf
_________________ Wenn jeder alles kann oder wüsste und keiner hätt' ne Frage mehr, omg, währe dieses Forum leer!
|
|
Kaspall 
      
Beiträge: 65
Erhaltene Danke: 10
|
Verfasst: 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.
|
|
Kha
      
Beiträge: 3803
Erhaltene Danke: 176
Arch Linux
Python, C, C++ (vim)
|
Verfasst: Mi 16.03.11 15:20
Point in Triangle Test
Kaspall hat folgendes geschrieben : | Ich versteh deinen Weg ehrlich gesagt nicht wirklich... |
Da schließe ich mich an  .
_________________ >λ=
|
|
Stundenplan
      
Beiträge: 128
Erhaltene Danke: 32
Win 7
Delphi 7 Pers., C# (VS 2010 Express)
|
Verfasst: Mi 16.03.11 15:28
Du könntest auch mit CreatePolygonRgn() eine Region erstellen und dann mit PtInRegion() testen.
Viele Grüße,
Stundenplan.
|
|
ALF
      
Beiträge: 1085
Erhaltene Danke: 53
WinXP, Win7, Win10
Delphi 7 Enterprise, XE
|
Verfasst: Mi 16.03.11 15:35
oobs, habe ich mich soo blöd ausgedrückt
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...
Alf
_________________ Wenn jeder alles kann oder wüsste und keiner hätt' ne Frage mehr, omg, währe dieses Forum leer!
|
|
ALF
      
Beiträge: 1085
Erhaltene Danke: 53
WinXP, Win7, Win10
Delphi 7 Enterprise, XE
|
Verfasst: 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 elseIf (P.x >= A.x) and (P.x <= C.x) then else | 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
Gruss ALf
_________________ Wenn jeder alles kann oder wüsste und keiner hätt' ne Frage mehr, omg, währe dieses Forum leer!
|
|
Kha
      
Beiträge: 3803
Erhaltene Danke: 176
Arch Linux
Python, C, C++ (vim)
|
Verfasst: Fr 18.03.11 14:48
Sorry, aber wenn ich das richtig sehe, werden deine Formeln hinten und vorne nicht hinhauen  . 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
      
Beiträge: 1085
Erhaltene Danke: 53
WinXP, Win7, Win10
Delphi 7 Enterprise, XE
|
Verfasst: 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
Gruss ALf
_________________ Wenn jeder alles kann oder wüsste und keiner hätt' ne Frage mehr, omg, währe dieses Forum leer!
|
|
Gausi
      
Beiträge: 8548
Erhaltene Danke: 477
Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
|
Verfasst: Fr 18.03.11 15:13
Was hat das denn mit VCL oder NonVCL zu tun?  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.
_________________ We are, we were and will not be.
|
|
ALF
      
Beiträge: 1085
Erhaltene Danke: 53
WinXP, Win7, Win10
Delphi 7 Enterprise, XE
|
Verfasst: Fr 18.03.11 15:26
So meinte ich es ja auch. Da ich nun aber nicht weiss ob er dies benötigt für ein Spiel z.B.
Spieler FOV(FieldOfView), was ja ein Dreieck ABC ist, und Gegner P .
Darum dieser Vorschlag
PS ist halt blöd wenn man sich nicht richtig ausdrücken kann
Gruss ALf
_________________ Wenn jeder alles kann oder wüsste und keiner hätt' ne Frage mehr, omg, währe dieses Forum leer!
|
|
Martok
      
Beiträge: 3661
Erhaltene Danke: 604
Win 8.1, Win 10 x64
Pascal: Lazarus Snapshot, Delphi 7,2007; PHP, JS: WebStorm
|
Verfasst: Fr 18.03.11 17:32
Warum macht ihr euch das so kompliziert? 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 Kha's Ansatz.
Aber da in diesem Thread irgendwie alle ein Problem damit haben sich vernünftig auszudrücken (  ) ist mir nicht so ganz klar was der OP eigentlich will 
_________________ "The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."
|
|
Xion
      

Beiträge: 1952
Erhaltene Danke: 128
Windows XP
Delphi (2005, SmartInspect), SQL, Lua, Java (Eclipse), C++ (Visual Studio 2010, Qt Creator), Python (Blender), Prolog (SWIProlog), Haskell (ghci)
|
Verfasst: 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); |
_________________ a broken heart is like a broken window - it'll never heal
In einem gut regierten Land ist Armut eine Schande, in einem schlecht regierten Reichtum. (Konfuzius)
Für diesen Beitrag haben gedankt: Horst_H
|
|
Horst_H
      
Beiträge: 1654
Erhaltene Danke: 244
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: 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
Einloggen, um Attachments anzusehen!
|
|
Waldheini
      
Beiträge: 32
Win 98SE, XP
D5 St., K3 Prof
|
Verfasst: 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 a:= ((X1-X2)*(Y1-Py))-((Y1-Y2)*(X1-Px)); b:= ((X2-X3)*(Y2-Py))-((Y2-Y3)*(X2-Px)); C:= ((X3-X1)*(Y3-Py))-((Y3-Y1)*(X3-Px)); Result:= ((a > 0) and (b > 0) and (c > 0)) or ((a < 0) and (b < 0) and (c < 0)); end; |
|
|
Mr_Emre_D
      
Beiträge: 114
Erhaltene Danke: 14
|
Verfasst: 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!
Einloggen, um Attachments anzusehen!
|
|
Waldheini
      
Beiträge: 32
Win 98SE, XP
D5 St., K3 Prof
|
Verfasst: 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.
|
|
|