HANDOUT - SIMPLE POINT IN POLYGON PROGRAM

ni = +1

for i=1 to n

if x(i+1) <> x(i) then (A)

if (x(i+1)-u) * (u-x(i)) >= 0 then (B)

if x(i+1) <> u or x(i) <= u then (C)

if x(i) <> u or x(i+1) >= u then (D)

b = (y(i+1)-y(i)) / (x(i+1)-x(i))

a = y(i)-b * x(i)

yi = a+b*u

if yi > v then

ni = ni*(-1)

end if

end if

end if

end if

end if

next i

Point is located at (u,v).

- b is the slope of the line from (x(i),y(i)) to (x(i+1),y(i+1))

- by substituting x=u in the equation y=a+b*x we get the y coordinate of the intersection between this line and the vertical line through x=u

- then if y(i) > v the intersection must be above the point, and so is counted

- the value of ni alternates between +1 and -1

- it is flipped every time an intersection is found

- at the end, ni = -1 if the point is in, +1 if the point is out

Special cases

Lines (A) through (D) deal with special cases, as follows:

(A.) if the line from (x(i),y(i)) to (x(i+1),y(i+1)) is vertical there can be no intersection

diagram

(B.) there can only be an intersection if the ith point is on one side of the vertical line through u and the i+1th point is on the other side

diagram

(C.D.) if either (x(i),y(i)) or (x(i+1),y(i+1)) lies exactly on the line, i.e. the point at (u,v) lies directly below a vertex, we may miscount:

diagram

Solution to this is:

if (x(i),y(i)) lies exactly on the line, then:

- count an intersection only if (x(i+1),y(i+1)) lies to the right, or

if (x(i+1),y(i+1)) lies exactly on the line, then:

count an intersection only if (x(i),y(i)) lies to the left

Polygon with isolated islands

diagram

- works fine

Polygon has hole with an island

diagram

- works fine

Concave polygons

diagram

- works fine

What if the point is on the boundary?

- some point in polygon routines deal with this explicitly, but this does not

- sometimes it finds the point inside, sometimes outside

Fuzzy boundaries

- Blakemore (see Blakemore, 1984) described a "fuzzy" generalization of the point in polygon problem:

- location of the boundary is uncertain

- a band of width epsilon is drawn around the boundary, and represents the band within which the true boundary is assumed to lie

- points can now be classified as "definitely out", "probably out", "probably in" and "definitely in"

Many points in many polygons (Advanced)

Polygons will likely be stored by arc

- check all arcs against vertical lines drawn upward from each point

If an arc between polygons A and B intersects, record an intersection with the boundary of both A and B, irrespective of which side of the arc A and B lie on. This will require a counter for each point/polygon combination. - not very efficient

A better algorithm is as follows:

When an arc is found to intersect a vertical line, record the y value of the intersection and the polygon lying below the intersection (right polygon if the arc runs from W to E, left polygon otherwise)

For each point, keep account of:

(a) the lowest such intersection found, and

(b) the polygon below that intersection

After all arcs have been examined, the polygon below the lowest intersection is the containing polygon

Now have just two values to store for each point - will still need to check every arc against every point, unless some sorting is done first.