# 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
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
// 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
]