Data analysis question.

[John Cameron]

Hi,

I have a set of XY co-ordinates that define a polygon.

I also have a single pair of XY co-ordinates that define a point.

Can anyone suggest a simple method to determine if the point falls
inside the polygon?

All numbers are doubles.
--
Regards,

John Cameron.
Type softly, read gently.

[msaxon]

Conceptually, what you need to do is this:

1. Find all the polygon line segments that cross the Y-coordinate of your point. For line segment with starting point (x1,y1) and finishing point (x2,y2) then the line crosses Y if y1<=y2.

2. Calculate the X-coordinates of the line segments for the given Y-coordinate.

3. Determine how many line segments are to the left of the point (i.e. how many line segments have calculated X coordinate less than your point's X-coordinate).

4. If this number is odd, then the point is inside the polygon. If even, it is outside.

Care has to be taken for the special case of a line segment or segments that lie along the Y-coordinate of the point.

--
Martin.

[John Cameron]

In message <5065000000050000008D9F0100-1079395200000@exchange.ni.com>,
msaxon writes
>Conceptually, what you need to do is this:
>
>1. Find all the polygon line segments that cross the Y-coordinate of
>your point. For line segment with starting point (x1,y1) and finishing
>point (x2,y2) then the line crosses Y if y1<=y2.
>
>2. Calculate the X-coordinates of the line segments for the given
>Y-coordinate.
>
>3. Determine how many line segments are to the left of the point (i.e.
>how many line segments have calculated X coordinate less than your
>point's X-coordinate).
>
>4. If this number is odd, then the point is inside the polygon. If
>even, it is outside.
>
>Care has to be taken for the special case of a line segment or
>segments that lie
along the Y-coordinate of the point.
>
>--
>Martin.

Hi Martin,

Thanks for the reply. If I understand you correctly then I think the
method falls down when the point is next to the left hand line segment
and the segment X co-ordinates are either side of the point.

+
+
. +
+

--
Regards,

John Cameron.
Type softly, read gently.

[msaxon]

No, the example you quote is ok. Don't forget that for each line segment you calculate the x-coordinate on the line corresponding to the y-coordinate of the point of interest.

The case it can't cope with is if there are line segments on either side of the point of interest that are 'horizontal' (i.e. they start and end with the same y-coordinate of the point of interest). In this case, the algorithm "doesn't know' if the point is inside or outside the polygon.

If there are such line segments only one side of the point of interest, that is ok because you can start counting segments from either side to get the result.

For example, in the attached sketch all of the 'o' points can be correctly identified (try it!) but the (red) 'x' point can
not.

There are two solutions to this:

1. You can go to a much more complex algorithm in which the polygon is broken down into a number of trapezoids and triangles; the point can then be tested against all of these elements to see if it is inside one of them.
   
2. You can move the point a tiny bit up and/or down to clear the ambiguity (that is what I normally do, since for most practical situations it works fine).
   

--
Martin

[John Cameron]

In message <506500000005000000AA9F0100-1079395200000@exchange.ni.com>,
msaxon writes
>No, the example you quote is ok. Don't forget that for each line
>segment you calculate the x-coordinate on the line corresponding to
>the y-coordinate of the point of interest.
>
>The case it can't cope with is if there are line segments on either
>side of the point of interest that are 'horizontal' (i.e. they start
>and end with the same y-coordinate of the point of interest). In this
>case, the algorithm "doesn't know' if the point is inside or outside
>the polygon.
>
>If there are such line segments only one side of the point of
>interest, that is ok because you can start counting segments from
>either side to get the result.
>
>For ex
ample, in the attached sketch all of the 'o' points can be
>correctly identified (try it!) but the (red) 'x' point cannot.
>
>There are two solutions to this:
>

>
1. You can go to a much more complex algorithm in which the polygon
   >is broken down into a number of trapezoids and triangles; the point
   >can then be tested against all of these elements to see if it is
   >inside one of them.
   >
2. You can move the point a tiny bit up and/or down to clear the
   >ambiguity (that is what I normally do, since for most practical
   >situations it works fine).
   >

>
>--
>Martin
>[ A MIME image / gif part was included here. ]
>

Yes is see what you mean now.

In fact your solution is very similar to one I found on the web dating
from 1970! In this version the point is shifted subtly to get around the
type of problem you demonstrate.

http://www.ecse.rpi.edu/Homepages/wrf/research/geom/pnpoly.html#License%2
0to%20Use

I shall attempt both solutions next week.

Thanks a lot for your input.


--
Reg
ards,

John Cameron.
Type softly, read gently.