Board index » delphi » Is a Point in a Polygon?

Is a Point in a Polygon?

I have the vertices of a polgon (up to 100 vertices), and I have a point.

What's an easy way to tell if the point is in the polygon?

J. Masters
tr...@circle.net

 

Re:Is a Point in a Polygon?


See windows api "regions" that should work.
in general create a region from your polygon and check the point to be
in the region !?

Quote
On Sun, 09 Feb 97 18:41:13 GMT, tr...@circle.net (Trent) wrote:
>I have the vertices of a polgon (up to 100 vertices), and I have a point.

>What's an easy way to tell if the point is in the polygon?

>J. Masters
>tr...@circle.net

Christian Kaas, c.k...@osn.de
Quote
>Software-, Projektrealisierung u. Beratung
>640kB ought to be enough memory ! - Bill Gates 1981

Re:Is a Point in a Polygon?


Quote
Trent wrote:

> I have the vertices of a polgon (up to 100 vertices), and I have a point.

> What's an easy way to tell if the point is in the polygon?

> J. Masters
> tr...@circle.net

If you want to do it mathematically, there is a very nice algorithm in
Joseph O'Rourke's book "Computational Geometry in C". I'm sure if you
search the web you will find his algorithm in various forms. Basically
what you do is extend a line fron the point and see if it crosses a
boundary an even or odd number of times.

Tony

Re:Is a Point in a Polygon?


Quote
In article <5dl5r8$...@news1-alterdial.uu.net> tr...@circle.net (Trent) writes:
>From: tr...@circle.net (Trent)
>Subject: Is a Point in a Polygon?
>Date: Sun, 09 Feb 97 18:41:13 GMT
>I have the vertices of a polgon (up to 100 vertices), and I have a point.
>What's an easy way to tell if the point is in the polygon?

Project a line from the point to infinity. Observe how many sides of the
polygon are intersected by the line. If it's odd, the point is inside the
polygon.

Roger Musson
r.mus...@bgs.ac.uk

Re:Is a Point in a Polygon?


Quote
In article <5dl5r8$...@news1-alterdial.uu.net>, tr...@circle.net (Trent) wrote:

]-I have the vertices of a polgon (up to 100 vertices), and I have a point.
]-
]-What's an easy way to tell if the point is in the polygon?

here's a previous post on the subject by the Lord of Darkness
which should point you in the right direction...

Mark Vaughan

----

     Date[ 06/13/1996
   Author[ Lord of Darkness
  Address[ j.biddisco...@rl.ac.uk
  Subject[ Polygons: creating, identifying, and manipulating
 Keywords[ polygon
 Question[
          ]
 Response[

this works for concave and convex polygons.

create a polygon by calling allocate_poly_space
or declare a pointer by your own allocation (stack/memory etc etc )

intercept WM_MouseMove and test x,y coords, the snippet I've put in is what
I use, but it's for a CAD-type program and the coords are 3D and doubles
this is not a problem as you can see...

type
  Point3D = record
    x,y,z : double;
  end;

type
  P_poly3D = ^Poly3D;
  Poly3D   = record
    numvertices : integer;
    polypoints  : array[0..0] of Point3D;
  end;

{
this type is like an AutoCAD polyline - the last point is the same as the first
if you want circularr polys with n vertices change numvertices-2 to
numvertices-1
etc etc

Quote
}

function is_point_in_polygon2D(poly:P_poly3D; x,y:double) : boolean;
var i,j       : integer;
    p1_i,p1_j : Point3D;
begin
  j := poly^.numvertices-2;
  result := false;
  with poly^ do for i:=0 to numvertices-2 do begin
    p1_i := polypoints[i];
    p1_j := polypoints[j];
    if ((((p1_i.y<=y) and (y<p1_j.y)) or
         ((p1_j.y<=y) and (y<p1_i.y))) and
          (x<(p1_j.x - p1_i.x)*(y-p1_i.y)/
          (p1_j.y - p1_i.y) + p1_i.x)) then result:= not result;
    j:=i;
  end;
end;

function allocate_poly_space(n:integer) : P_poly3D;
begin
  Getmem(result,SizeOf(poly3D)+(n-1)*SizeOf(Point3D));
  result^.numvertices := n;
  inc(polys_in_existence);
end;

procedure free_poly_space(var poly:P_Poly3D);
begin
  Freemem(poly,SizeOf(poly3D)+(poly^.numvertices-1)*SizeOf(Point3D));
  dec(polys_in_existence);
end;

{ this searches through lists of polygons to find the one the mouse is in
I left this code as I use it, because it's easier than doing a simplified demo
you can cut out most of it )
( Most mouse movements are small, so I always check to see if the last
highlighted poly is still the one with the mouse in first, if not then I search
all the others, this saves a lot of searching when the

procedure TMap_display_form.ZoomboxMouseMove(Sender:TObject; Shift:TShiftState;
X,Y:Integer);
var lp0,lp1   : integer;
    P_poly    : P_Poly3D;
    p1        : Point2D;
    p2        : Point3D;
    data_list : My_data_list;
    redraw    : boolean;
begin
  if not database_loaded then exit;
// convert screen coords to database coords
  p1 := Zoombox.Screen_to_real(Point(x,y));
// can we redraw/leave the last highlighted one ?

// ignore this
  redraw := false;
  for lp0:=0 to Files_listbox.Items.Count-1 do begin
    if (not Files_listbox.Selected[lp0]) then continue;
    data_list := My_data_list(Files_listbox.Items.Objects[lp0]);
    if (data_list=Highlighted_list) and (Highlighted_list<>nil) then begin
      redraw:=true; lp1:=lp0; break;
    end;
  end;
  if (highlighted_poly<>nil) and redraw then begin

// this is the important bit

    if
is_point_in_polygon2D(Highlighted_poly,RCPoly_List(Highlighted_list),p1.x,p1.y)
then exit;
    //  same poly as last time - exit quickly, otherwise rub it out.
    // normal color
    Zoombox.ClientArea.Canvas.Pen.Color := nice_colours[lp1 mod 20];

// draw the highlighted polygon
    Highlighted_list.draw_primitive(Highlighted_poly,Zoombox.ClientArea.Canvas);
  end;

  etc etc etc

  this may be a little confusing but all you need to do is
  if is_point_in_Poly2D(polypointer,x,y) then do_something nice

end;

Hope this helps

John B
          ]

Other Threads