## Bounds Checking for Point Inside a Polygon

### Bounds Checking for Point Inside a Polygon

Umm... How about flood filling the polygon and then checking the color of
that point.

Kevin

Quote:> I am having a problem and was hoping someone might have a solution.  I
need
> to be able to define a polygon that may have any number of vertices.
> Assuming that the vertices form a closed polygon, how can I check if a
point
> (x, y) falls inside this polygon.  I was thinking about transformations,
but
> cant get my head around this problem.
> Any help or suggestions would be greatly appreciated.

> Thanks

> Mike

### Bounds Checking for Point Inside a Polygon

I am having a problem and was hoping someone might have a solution.  I need
to be able to define a polygon that may have any number of vertices.
Assuming that the vertices form a closed polygon, how can I check if a point
(x, y) falls inside this polygon.  I was thinking about transformations, but
cant get my head around this problem.
Any help or suggestions would be greatly appreciated.

Thanks

Mike

### Bounds Checking for Point Inside a Polygon

<pseudo-code>

Type Point
X as Single
Y as Single
End Type

For i% = 1 to NumPts%
If Pt(i%).X > MaxX then MaxX = Pt(i%).X
If Pt(i%).Y > MaxY then MaxY = Pt(i%).Y
Next i%

MaxPt.X = MaxX + 1: MaxPt.Y = MaxY + 1

Isections% = 0
For i% = 1 to NumPts%
If i% = NumPts% Then
j% = 1
Else
j% = i% + 1
Endif
Isections% = Isections% + InterSect(MaxPt, PtX, Pt(i%), Pt(j%))
Next i%

InSide% = ((Isections% AND 1) = 1)

</pseudo-code>

The fun part is writing Intersect, it returns 1 if a line defined by
the first two Pts intersects the line defined by the second pair of
points.  Don't forget to account for horizontal lines, and vertical
lines as well as normal, sloped lines.

--

Jim DeVries

'65 Monza - '94 Saturn SL2

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
"If all mankind minus one, were of one opinion, and only one person were
of a contrary opinion, mankind would be no more justified in silencing
that one person, than he, if he had the power, would be justified in
silencing mankind."

John Stuart Mill, from 'On Liberty'

### Bounds Checking for Point Inside a Polygon

A nonMathematical solution is to draw that poligon in a invisible picture.
Paint inside the poligon with one cololor (eg Black) and outside the poligon
with another color (eg White). Then with the Point function you can know if
your point is inside or outside the poligon.

if Picture1.Point(x,y) = vbBlack then
...is inside
else
...is outside
end if

You must set the Autoredraw property of the Picture to TRUE.
Hope this helps...
========================================
Pedro J. Rusjan

WEB: http://www.mug.org.ar/socios/pedro.rusjan
========================================

Quote:>I am having a problem and was hoping someone might have a solution.  I need
>to be able to define a polygon that may have any number of vertices.
>Assuming that the vertices form a closed polygon, how can I check if a
point
>(x, y) falls inside this polygon.  I was thinking about transformations,
but
>cant get my head around this problem.
>Any help or suggestions would be greatly appreciated.

>Thanks

>Mike

### Bounds Checking for Point Inside a Polygon

>I am having a problem and was hoping someone might have a solution.  I need
>to be able to define a polygon that may have any number of vertices.
>Assuming that the vertices form a closed polygon, how can I check if a
point
>(x, y) falls inside this polygon.  I was thinking about transformations,
but
>cant get my head around this problem.
>Any help or suggestions would be greatly appreciated.

This falls under the "any suggestions" category ...

Let point P be a known point, which is inside the polygon; let Q be any
other point.
Draw a line segment from P to Q.  You must now count the number of
intersections with the boundary lines of the polygon ... if it is even
(0,2,4,...), then Q is inside the polygon; if it is odd, then Q is outside.

This is obviously true for a convex polygon, but it also works for a concave
polygon.

Best Regards, Peter

### Bounds Checking for Point Inside a Polygon

O.K., Don't worry Mike, your problem is not difficult, so I can tell you
decision without any joking!

First : you need Type (but not necessary )  -

Type Point
X As Double
Y As Double
End Type

Then : you need Function -
Function IsCross(p1 as Point, p2 as Point ,q1 as Point, q2 as Point) as
Boolean

Dim Kp as Double,Kq as Double
Dim CrossX as Double
Dim T as Double

On Error GoTo L1
Kp=(p2.X-p1.X)/(p2.Y-p1.Y)
Kq=(q2.X-q1.X)/(q2.Y-q1.Y)
CrossX=(p1.X*Kp-q1.X*Kq+q1.Y-p1.Y)/(Kp-Kq)

if p2.X<p1.X then
T=p2.X
p2.X=p1.X
p1.X=T
End If

IsCross = ((CrossX > p1.X) AND (CrossX < p2.X))

ExitL: Exit Function
L1: on error goto 0
IsCross = False
GoTo ExitL
End Function

Second : I think your polygon is presented by points
Pt(1)->Pt(2)->->Pt(NPts)=Pt(1)
and your point is MyPt (there I mean you define structure {.x,.y })
So, the main Code is

Dim I as Integer,J as Integer
Dim Answer as Boolean  'this is the answer

For I=1 To NPts
For J= 1 To Npts-1
if  IsCross ( MyPt,Pt(I),Pt(J),Pt(J+1))   then Exit For
Next J
if J <  Npts then Exit For
Next I
Answer = (I <= Npts)

This is all! Try it !
Maybe this is not the best decision but this mast be work. If you wont a

Best Regards, Kakha Orkoshneli.

### Bounds Checking for Point Inside a Polygon

> Umm... How about flood filling the polygon and then checking the color of
> that point.

> Kevin

But You have to know X,Y coords of flood fill starting point and that's
Mike's question.

Regards.
Artur.
--
_ | _______________________________________________________________
/ -+-_  ___  ___  _  _ _  ___  ___                                  \
|   |/ || _ \/ __)| || \ |/   \| __) Artur Jarkiewicz                 |

|  /___||_\_\(___/|_||_\_|\___/|___) http://www.meil.pw.edu.pl/~ajark |
\___________________________________________________________________/

### Bounds Checking for Point Inside a Polygon

>I am having a problem and was hoping someone might have a solution.  I need
>to be able to define a polygon that may have any number of vertices.
>Assuming that the vertices form a closed polygon, how can I check if a point
>(x, y) falls inside this polygon.

I once wrote such a function (in Perl), and it worked pretty goo. It's
along the lines of the pseudocode by Jim DeVries in another reply.

But you could also use the API. Check out these API calls:

CreatePolygonRgn        'create a lpolygonal region
PtInRegion              'check if a point is in a region

and don't forget to apply DeleteObject on your region when you're
through.

As for the code-only solution, here's the principle:

Draw a line from your point to infinity. Check how many sides it
crosses. If this number is odd, the point is inside the polygon;
if it's even, it's outside.

Problems you may encounter is when your line runs though an endpoint.

As for an easy solution, take a horizontal line, x>xp. Check y1 and y2
are on different sides of yp ((xp,yp) is your point): one above, the
other below. If so, calculate the x value of a point on that line. If
for this point, x>xp ((x,y) is on line (x1,y1)-(x2,y2), and y=yp), then
these pieces cross.

HTH,
Bart.

### Bounds Checking for Point Inside a Polygon

>This falls under the "any suggestions" category ...

>Let point P be a known point, which is inside the polygon; let Q be any
>other point.
>Draw a line segment from P to Q.  You must now count the number of
>intersections with the boundary lines of the polygon ... if it is even
>(0,2,4,...), then Q is inside the polygon; if it is odd, then Q is outside.

Rotten thing is: you have to know a point that is sure to be inside a
polygon.

Reversing this is easy. Take any point that is far away from the
polygon. This point is sure to be OUTSIDE the polygon. Applying your
method here, simply swap the "even" and "odd" for inside and outside.

You may even use "infinity" as the reference outside point. Counting the
intersections with the half-line {y=yp, x>xp} will do. This is the
algorythm I described in another reply.

I'm not sure if there's a name for this algorythm. I know I "invented"
it once, when solving this question as an assignment for a course in
computer graphics. Your post proves I'm not the only one to think of it.

===
As for the calculation of the intersection... This is the "parameter
representation"  of the line (x1,y1)-(x2,y2), maning that for any point
(x,y) on the line, there exists a number k:

x = k * (x2-x1) + x1
y = k * (y2-y1) + y1

Note that k is 0 and 1 for the endpoints, respectively.

The lines intersect, if there is a solution with 0<k<1, for any point on
the other line (y=yp), with x>xp. Solving this, you get:

k = (yp-y1)/(y2-y1)
if k<0 or k>1 then
'no intersection
else if k * (x2-x1) + x1 > xp
'intersection!
else
'no intersection
end if

Bart.

### Bounds Checking for Point Inside a Polygon

There is a graphics techni called clipping that may solve your problem.  I
ve seen a algorithm in a book called Computer Graphics Princeples and
Practice by Foley, van Dam, Feiner and Hughes.  The publisher is

I will try to find  the algorithm in my book.

Andre de Beer

>I am having a problem and was hoping someone might have a solution.  I need
>to be able to define a polygon that may have any number of vertices.
>Assuming that the vertices form a closed polygon, how can I check if a
point
>(x, y) falls inside this polygon.  I was thinking about transformations,
but
>cant get my head around this problem.
>Any help or suggestions would be greatly appreciated.

>Thanks

>Mike

### Bounds Checking for Point Inside a Polygon

>> Umm... How about flood filling the polygon and then checking the color of
>> that point.

>> Kevin

Actually,  that's exactly what I was doing, not filling it, but using a
bitmap and the color of Point (x, y).  The problem is that different
graphics adapters render the image differently (8-bit, 16-bit, and 24-bit
all render different values).

Thanks to everyone for all of the suggestions !

Mike

### Bounds Checking for Point Inside a Polygon

You could use the Windows API call PtInRegion.  you should just have to give
it a point and a defined polygon, and it will tell you whether or not it is
in it.  I haven't used it in a while, but I know it worked.

>>I am having a problem and was hoping someone might have a solution.  I
need
>>to be able to define a polygon that may have any number of vertices.
>>Assuming that the vertices form a closed polygon, how can I check if a
>point
>>(x, y) falls inside this polygon.  I was thinking about transformations,
>but
>>cant get my head around this problem.
>>Any help or suggestions would be greatly appreciated.

Hi all,

I need an fast algorithm to check if a point is inside a polygon. The
polygon has no more than 255 edges, arbitrary shape. we have a struct to
store vertex coordinates, but it is not guarantee to have a
conterclockwise order.

Thank you for your help.

Linda Chen