Bounds Checking for Point Inside a Polygon

Bounds Checking for Point Inside a Polygon

Post by Denve » Wed, 28 Jan 1998 04:00:00



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

Post by Michael Hatfiel » Wed, 28 Jan 1998 04:00:00


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

Post by Jim DeVrie » Wed, 28 Jan 1998 04:00:00


<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

Post by Pedro Rusja » Wed, 28 Jan 1998 04:00:00


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

Post by Peter Dieh » Wed, 28 Jan 1998 04:00:00



>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

Post by Kakha Orkoshnel » Thu, 29 Jan 1998 04:00:00


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
better decision, contact us

Best Regards, Kakha Orkoshneli.

 
 
 

Bounds Checking for Point Inside a Polygon

Post by Artur Jarkiewic » Thu, 29 Jan 1998 04:00:00



> 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

Post by Bart Late » Thu, 29 Jan 1998 04:00:00



>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

Post by Bart Late » Fri, 30 Jan 1998 04:00:00



>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

Post by 139.53.1.19 » Fri, 30 Jan 1998 04:00:00


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
Addison-Wesley Publishing Company.

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

Post by Michael Hatfiel » Fri, 30 Jan 1998 04:00:00



>> 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

Post by Adam Krapf » Fri, 30 Jan 1998 04:00:00


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.

-Adam.



>>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.