AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Projekte Ist ein Punkt in einem Polygon

Ist ein Punkt in einem Polygon

Ein Thema von Amateurprofi · begonnen am 21. Feb 2007 · letzter Beitrag vom 17. Nov 2009
Antwort Antwort
Seite 1 von 3  1 23   
Amateurprofi
Registriert seit: 17. Nov 2005
Nicht immer, aber immer wieder taucht die Frage auf, wie man wohl feststellen kann, ob ein Punkt innerhalb eines Dreiecks oder innerhalb einer anderen Figur liegt.

Ich habe dieses Thema mal ganz allgemein betrachtet und eine kleine Funktion geschrieben, die prüft, ob sich ein Punkt innerhalb eines konvexen nicht überschlagenden Polygons befindet.
Ein Programm zum Testen ist im Anhang.
Vielleicht interessiert es den einen oder anderen.

Delphi-Quellcode:
{------------------------------------------------------------------------------}
{ PtInPolygon                                                                  }
{ Prüft, ob ein Punkt innerhalb eines Polygons liegt.                          }
{ Das Polygon muß konvex sein und darf keine Überschneidungen haben.           }
{------------------------------------------------------------------------------}
FUNCTION PtInPolygon(const points:array of TPoint; N:integer; const p:TPoint):boolean;
var i:integer; angles:single;
//------------------------------------------------------------------------------
FUNCTION Angle(const p1,p2:TPoint):Extended;
var a2,b2,c2,cosa:single;
//--------------------------------------------------------------
begin
   a2:=Sqr(p2.x-p1.x)+Sqr(p2.y-p1.y);
   b2:=Sqr(p2.x-p.x)+Sqr(p2.y-p.y);
   c2:=Sqr(p1.x-p.x)+Sqr(p1.y-p.y);
   cosa:=(b2+c2-a2)/(2*Sqrt(b2)*Sqrt(c2));
   if cosa<=-1 then result:=pi
      else if cosa>=1 then result:=0
         else Result:=ArcCos(cosa);
end;
//------------------------------------------------------------------------------
begin
   result:=(n>2) and (n-1<=High(points));
   if not result then exit;
   for i:=0 to n-1 do if (p.x=points[i].x) and (p.y=points[i].y) then exit;
   angles:=Angle(points[n-1],points[0]);
   for i:=0 to n-2 do angles:=angles+Angle(points[i],points[i+1]);
   result:=Abs(angles-Pi*2)<0.00001;
end;
Angehängte Dateien
Dateityp: zip knlib_781.zip (229,8 KB, 77x aufgerufen)
Gruß, Klaus
Die Titanic wurde von Profis gebaut,
die Arche Noah von einem Amateur.
... Und dieser Beitrag vom Amateurprofi....
 
21. Feb 2007, 16:26
Dieses Thema wurde von "SirThornberry" von "Programmieren allgemein" nach "Open-Source" verschoben.
EDatabaseError

 
Delphi 2007 Professional
 
#3
  Alt 21. Feb 2007, 16:40
In dem angehängten Polygon erkennt er garkeinen Punkt der innen liegt.

Tobi
Miniaturansicht angehängter Grafiken
unbenannt_179.png  
Tobias
  Mit Zitat antworten Zitat
Benutzerbild von Neutral General
Neutral General

 
Delphi 10.2 Tokyo Professional
 
#4
  Alt 21. Feb 2007, 16:42
Zitat von Amateurprofi:
Ich habe dieses Thema mal ganz allgemein betrachtet und eine kleine Funktion geschrieben, die prüft, ob sich ein Punkt innerhalb eines konvexen nicht überschlagenden Polygons befindet.
Kann es sein das du da was überlesen hast EDatabaseError

Gruß
Neutral General
Michael
  Mit Zitat antworten Zitat
Amateurprofi

 
Delphi XE2 Professional
 
#5
  Alt 21. Feb 2007, 21:12
Zitat von EDatabaseError:
In dem angehängten Polygon erkennt er garkeinen Punkt der innen liegt.

Tobi
Also funktioniert das ganz ausgezeichnet.

Bei "Deiner" Figur handelt es sich um ein nichtkonvexes, überschlagendes Polygon, also um genau das Gegenteil eines konvexexn, nichtüberschlagenden Polygons. Im Begleittext steht aber unmißverständlich, daß die Prüffunktion nur für konvexe, nichtüberschlagende Polygone gedacht ist.
  Mit Zitat antworten Zitat
Benutzerbild von JasonDX
JasonDX
 
#6
  Alt 21. Feb 2007, 21:45
Geil sehr coole Idee, wie dus geloest hast
Nur eine ganz kleine Kleinigkeit zur Polygon-Bedingung: Ein konvexes Polygon kann sich IMHO nicht ueberschlagen, also koenntest du das theoretisch weglassen

greetz
Mike
Mike
  Mit Zitat antworten Zitat
Gandalfus

 
Delphi 2006 Professional
 
#7
  Alt 22. Feb 2007, 03:27
passent zum Thema:
http://blubplayer.de/tipppointinpolygon.html

ein Programm zum testen hab ich auch noch:
http://www.blubplayer.de/PointinPolygon.zip


Wie genau ist ein konvexes Polygon definiert?
  Mit Zitat antworten Zitat
Amateurprofi

 
Delphi XE2 Professional
 
#8
  Alt 22. Feb 2007, 11:14
Zitat von Gandalfus:
Superschnell die Funktion.
Jedoch (wenn ich nicht grobe Fehler gemacht habe), leider nicht zuverlässig.

Die in anhängendem Bild rot markierten Punkte wurden nicht richtig erkannt.

Teilweise wird für Punkte außerhalb des Polygons True zurückgegeben, teilweise für Punkte innerhalb des Polygons false.
Miniaturansicht angehängter Grafiken
test_988.jpg  
  Mit Zitat antworten Zitat
Amateurprofi

 
Delphi XE2 Professional
 
#9
  Alt 22. Feb 2007, 11:36
Zitat von JasonDX:
Geil :D sehr coole Idee, wie dus geloest hast :thumb:
Nur eine ganz kleine Kleinigkeit zur Polygon-Bedingung: Ein konvexes Polygon kann sich IMHO nicht ueberschlagen, also koenntest du das theoretisch weglassen ;)

greetz
Mike
Ja, dem könnte ich mich anschließen.
Aber sieh Dir mal anhängendes Bild an.
Die Angaben, welche Punkte zum Polygon gehören stehen daneben.

Weiß nicht wie Fachleute das sehen.....
Die äußere Begrenzung ist ein Quadrat, m.E. konvex.
Durch die Senkrechten innerhalb des Quadrates wird es zu einem überschlagenden Polygon.
Wir haben also ein konvexes überschlagendes Polygon.
Sicherlich sehr konstruiert....
Miniaturansicht angehängter Grafiken
test2_156.jpg  
  Mit Zitat antworten Zitat
EDatabaseError

 
Delphi 2007 Professional
 
#10
  Alt 22. Feb 2007, 11:46
Zitat von Neutral General:
Zitat von Amateurprofi:
Ich habe dieses Thema mal ganz allgemein betrachtet und eine kleine Funktion geschrieben, die prüft, ob sich ein Punkt innerhalb eines konvexen nicht überschlagenden Polygons befindet.
Kann es sein das du da was überlesen hast EDatabaseError

Gruß
Neutral General
kann ja mal vorkommen...
Tobias
  Mit Zitat antworten Zitat
Antwort Antwort
Seite 1 von 3  1 23   

Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 21:32 Uhr.
Powered by vBulletin® Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2019 by Daniel R. Wolf