AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Projekte Ist ein Punkt in einem Polygon
Thema durchsuchen
Ansicht
Themen-Optionen

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
Ort: Hamburg
1.043 Beiträge
 
Delphi XE2 Professional
 
#1

Ist ein Punkt in einem Polygon

  Alt 21. Feb 2007, 12:43
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, 83x aufgerufen)
Gruß, Klaus
Die Titanic wurde von Profis gebaut,
die Arche Noah von einem Amateur.
... Und dieser Beitrag vom Amateurprofi....
  Mit Zitat antworten Zitat
21. Feb 2007, 15:26
Dieses Thema wurde von "SirThornberry" von "Programmieren allgemein" nach "Open-Source" verschoben.
EDatabaseError

Registriert seit: 11. Mai 2005
Ort: Göppingen
1.238 Beiträge
 
Delphi 2007 Professional
 
#3

Re: Ist ein Punkt in einem Polygon

  Alt 21. Feb 2007, 15:40
In dem angehängten Polygon erkennt er garkeinen Punkt der innen liegt.

Tobi
Miniaturansicht angehängter Grafiken
unbenannt_179.png  
Tobias
It's not a bug, it's a feature.
  Mit Zitat antworten Zitat
Benutzerbild von Neutral General
Neutral General

Registriert seit: 16. Jan 2004
Ort: Bendorf
5.219 Beiträge
 
Delphi 10.2 Tokyo Professional
 
#4

Re: Ist ein Punkt in einem Polygon

  Alt 21. Feb 2007, 15: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
"Programmers talk about software development on weekends, vacations, and over meals not because they lack imagination,
but because their imagination reveals worlds that others cannot see."
  Mit Zitat antworten Zitat
Amateurprofi

Registriert seit: 17. Nov 2005
Ort: Hamburg
1.043 Beiträge
 
Delphi XE2 Professional
 
#5

Re: Ist ein Punkt in einem Polygon

  Alt 21. Feb 2007, 20: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.
Gruß, Klaus
Die Titanic wurde von Profis gebaut,
die Arche Noah von einem Amateur.
... Und dieser Beitrag vom Amateurprofi....
  Mit Zitat antworten Zitat
Benutzerbild von JasonDX
JasonDX
(CodeLib-Manager)

Registriert seit: 5. Aug 2004
Ort: München
1.062 Beiträge
 
#6

Re: Ist ein Punkt in einem Polygon

  Alt 21. Feb 2007, 20: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
Passion is no replacement for reason
  Mit Zitat antworten Zitat
Gandalfus

Registriert seit: 19. Apr 2003
407 Beiträge
 
Delphi 2006 Professional
 
#7

Re: Ist ein Punkt in einem Polygon

  Alt 22. Feb 2007, 02: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?
Besucht doch mal meine Homepage
  Mit Zitat antworten Zitat
Amateurprofi

Registriert seit: 17. Nov 2005
Ort: Hamburg
1.043 Beiträge
 
Delphi XE2 Professional
 
#8

Re: Ist ein Punkt in einem Polygon

  Alt 22. Feb 2007, 10: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  
Gruß, Klaus
Die Titanic wurde von Profis gebaut,
die Arche Noah von einem Amateur.
... Und dieser Beitrag vom Amateurprofi....
  Mit Zitat antworten Zitat
Amateurprofi

Registriert seit: 17. Nov 2005
Ort: Hamburg
1.043 Beiträge
 
Delphi XE2 Professional
 
#9

Re: Ist ein Punkt in einem Polygon

  Alt 22. Feb 2007, 10: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  
Gruß, Klaus
Die Titanic wurde von Profis gebaut,
die Arche Noah von einem Amateur.
... Und dieser Beitrag vom Amateurprofi....
  Mit Zitat antworten Zitat
EDatabaseError

Registriert seit: 11. Mai 2005
Ort: Göppingen
1.238 Beiträge
 
Delphi 2007 Professional
 
#10

Re: Ist ein Punkt in einem Polygon

  Alt 22. Feb 2007, 10: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
It's not a bug, it's a feature.
  Mit Zitat antworten Zitat
Antwort Antwort
Seite 1 von 3  1 23      


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 12:52 Uhr.
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz