# Board index » delphi » Geometry help needed

## Geometry help needed

##### Quote
Sheldon C. Shallon wrote in message <37E26DAA.6...@ieee.org>...
>Arash wrote:

>> I'm after a program in pascal more so an algorithim that will determine
>> weather or not a point is within an n-vertix polygon (n number of
>> sides).

>> Something like:

>> Const N=5;
>> Type TPoint: Record x,y:Integer; End;
>> Type TPoly: Array[1..5] Of TPoint;

>> Function (Poly:TPoly; x,y:Integer):Boolean;
>>   Begin
>>   End;

>> The function should give a true value if point is in polygon otherwise
>> it should give a flase value, plus if the point is on any of the sides
>> it should also give a true value.

>> If anyone can help me with this, and to please explain the geometry
>> involved I'd appreciate it very much.

>> Arash

>You could draw the polygon with a colored fill, then check the color of
>the point.

That's too easy. Well, it is *if* he can draw the polygon. :)

## Re:Geometry help needed

##### Quote
> >> I'm after a program in pascal more so an algorithim that will
determine
> >> weather or not a point is within an n-vertix polygon (n number of
> >> sides).

> >> Something like:

> >> Const N=5;
> >> Type TPoint: Record x,y:Integer; End;
> >> Type TPoly: Array[1..5] Of TPoint;

> >> Function (Poly:TPoly; x,y:Integer):Boolean;
> >>   Begin
> >>   End;

> >> The function should give a true value if point is in polygon
otherwise
> >> it should give a flase value, plus if the point is on any of the
sides
> >> it should also give a true value.

> >> If anyone can help me with this, and to please explain the geometry
> >> involved I'd appreciate it very much.

> >> Arash

> >You could draw the polygon with a colored fill, then check the color
of
> >the point.

> That's too easy. Well, it is *if* he can draw the polygon. :)

Well, drawing a polygon is a science itself :-)
One solution is given in comp.graphics.algorithms FAQ (e.g.
ftp://x2ftp.oulu.fi/pub/msdos/programming/faq/algorith.114 question
#17). Warning: it's C ;-) But there is no explanation...

Trying to improvise... If the polygon is convex the following approach
should work:
var p : TPoint; v : TVert;
Iterate over edges and calculate (v[i+1].x-v[i].x)*(p.y-v[i].y) -
(v[i+1].y-v[i].y)*(p.x-v[i].x) - it should be z-component of cross
product between "edge vector" and vector from first vertex of the edge
to the problematic point :-). You have to iterate over every edge, of
course (this example forgets one). IF the point is inside, signs of
these components must not change. If one of these numbers is zero, the
point is on this edge. I _hope_ I didn't make any mistake.

Non-convex polygons are worse - so bad that I don't want to think about
them right now.

--
Ingmar

Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.

## Re:Geometry help needed

##### Quote
On Sat, 18 Sep 1999, Ingmar Tulva wrote:
> Well, drawing a polygon is a science itself :-)
> One solution is given in comp.graphics.algorithms FAQ (e.g.
> ftp://x2ftp.oulu.fi/pub/msdos/programming/faq/algorith.114 question
> #17). Warning: it's C ;-) But there is no explanation...

Another solution is to have a look at the fillpoly procedure in the file
rtl\inc\graph\fills.inc of the FPC RTL sources (available in the
development section at <http://tfdec1.fys.kuleuven.ac.be/~michael/fpc>.
It's written completely in pascal and basically only requires a line
procedure.

It works both for convex and concave polygons and fills them while drawing
them (so no floodfilling)

Jonas

## Re:Geometry help needed

##### Quote
Ingmar Tulva <mi...@my-deja.com> writes:
> Non-convex polygons are worse - so bad that I don't want to think about
> them right now.

Well, if there's a point that you know is outside the polygon (like
the upper left hand corner or (-100,-100) or whatever) then a line
drawn from the point in question and that outside point will cross an
edge of the polygon an odd number of times if the point is inside, and
an even number of times if the point is outside.  (This will work for
any curve.)

The trick is to determine whether a given point is on the edge of a
polygon, and thus to determine how many times a line segment cross a
polygon.

/
:@-) Scott
\

## Re:Geometry help needed

Lancelot appearing sideways <sah...@rainbow.uchicago.edu> wrote:

##### Quote
> Well, if there's a point that you know is outside the polygon (like
> the upper left hand corner or (-100,-100) or whatever) then a line
> drawn from the point in question and that outside point will cross an
> edge of the polygon an odd number of times if the point is inside, and
> an even number of times if the point is outside.  (This will work for
> any curve.)

> The trick is to determine whether a given point is on the edge of a
> polygon, and thus to determine how many times a line segment cross a
> polygon.

Elegant! Let's better take (p.x,inf) or (inf,p.y) as the other point,
i.e. a simply-oriented ray instead of line. Voila, it's far more simple
than one could guess (but requires a slow and dangerous division).

Well, let's stop posting this not-so-ontopic discussion to almost every
Pascal newsgroup..

--
Ingmar

Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.

## Re:Geometry help needed

interesting view, could you please elabortae a bit more ?
##### Quote
Lancelot appearing sideways wrote:
> Ingmar Tulva <mi...@my-deja.com> writes:

> > Non-convex polygons are worse - so bad that I don't want to think about
> > them right now.

> Well, if there's a point that you know is outside the polygon (like
> the upper left hand corner or (-100,-100) or whatever) then a line
> drawn from the point in question and that outside point will cross an
> edge of the polygon an odd number of times if the point is inside, and
> an even number of times if the point is outside.  (This will work for
> any curve.)

> The trick is to determine whether a given point is on the edge of a
> polygon, and thus to determine how many times a line segment cross a
> polygon.

> /
> :@-) Scott
> \

## Re:Geometry help needed

[Arash's reply moved to the bottom of my previous post, where it should be.]

##### Quote
Arash <tprod...@primus.com.au> writes:
> Lancelot appearing sideways wrote:

> > Ingmar Tulva <mi...@my-deja.com> writes:

> > > Non-convex polygons are worse - so bad that I don't want to think about
> > > them right now.

> > Well, if there's a point that you know is outside the polygon (like
> > the upper left hand corner or (-100,-100) or whatever) then a line
> > drawn from the point in question and that outside point will cross an
> > edge of the polygon an odd number of times if the point is inside, and
> > an even number of times if the point is outside.  (This will work for
> > any curve.)

> > The trick is to determine whether a given point is on the edge of a
> > polygon, and thus to determine how many times a line segment cross a
> > polygon.

> interesting view, could you please elaborate a bit more ?

Choose a point that you want to know about--i.e. is it inside or
outside.  Now start at a point that you know is outside.  Now the only
way to go from outside to inside or inside to outside is by crossing
the border of the polygon.  Also, crossing an edge will always switch
you: there are no edges in a polygon which you can cross and remain
on the same side as you were before you crossed it.
So start moving from the outside point to the point in
question, along any path (a straight line is simplest).  If you don't
cross any edges to get to the point in question (call it P), then you
never went inside the polygon, so P is outside.  If you cross one edge
as you go, then you moved inside the polygon, and are still inside the
polygon when you hit P; thus P is inside.  If you cross two edges,
at the first edge you moved inside, but at the second you moved out
again, so P is on the outside.  And so forth.

Mind you I've never coded this, so I don't know all of the
problems there might be in translation into Pascal.  You'd have to
check if P were on the edge, of course; that would be a special case.
You also might run into problems if your path passes tangent to a
vertex; there the two edges that make up the vertex may look like one
edge, but the path passing it could start outside the polygon and stay
there.  Since you probably have the polygon stored as a set of points,
you can get around this by making the path you choose avoid all
vertices.  Also, instead of a straight line, you might want to use an
L-shaped path to the point; any shaped path will do, and a computer
understands horizontal and vertical lines better than skew ones.

Another method's come to me: you can divide up any polygon
into triangles, so write a routine that tells you if a point is inside
a triangle, divide your polygon up into appropriate triangles, and go
from there.  Unfortunately I don't see a trivial way of determining
a set of triangles that completely cover a polygon and only a polygon,
so that's tricky (a convex polygon can be covered by the set of
triangles made up by using any three of its vertices, although that's
overkill.  This won't work for nonconvex polygons, like a star or a
four-point boomerang.)

Implementation is left as an exercise for the reader.

/
:@-) Scott
\

## Re:Geometry help needed

In article <ru6dccj2lg...@corp.supernews.com>, "Todd"

##### Quote
<Post_to_group_o...@nospam.com> wrote:
>>Sheldon C. Shallon wrote in message <37E26DAA.6...@ieee.org>...
>>>Arash wrote:

>>>> I'm after a program in pascal more so an algorithim that will determine
>>>> weather or not a point is within an n-vertix polygon (n number of
>>>> sides).

>>>> Something like:

>>>> Const N=5;
>>>> Type TPoint: Record x,y:Integer; End;
>>>> Type TPoly: Array[1..5] Of TPoint;

>>>> Function (Poly:TPoly; x,y:Integer):Boolean;
>>>>   Begin
>>>>   End;

>>>> The function should give a true value if point is in polygon otherwise
>>>> it should give a flase value, plus if the point is on any of the sides
>>>> it should also give a true value.

>>>> If anyone can help me with this, and to please explain the geometry
>>>> involved I'd appreciate it very much.

>>>> Arash

>>>You could draw the polygon with a colored fill, then check the color of
>>>the point.

use quickdarw routines :
1) make a polygon
2) transform polygon to region
3) use ptInRgn test !!!

----------------------------------------------------------
Et Dieu cra les hommes. Les autres utiliseront Windows95.
----------------------------------------------------------