inside area

[Stephen Woodbridge]

joerg pfeiffer wrote:
> hello,
>
> I d like to build a function in php, that checks, if a lat/long point is
> inside an area, described by several lat/long points.
>
> Is there a function, also in other languages, I can use or translate?

If you are looking to do a pure php implementation instead of Abe's good
suggestion, there are two algorithms that I know for this task.

1) sum the angles created by p[i], t, p[i+1] while i+1 <=n, where t is
the point you are testing and p[1..n] is your polygon, where p[1] ==
p[n]. You angle calculation needs to be account for positive and
negative angles. If you result is 360, then t is in the polygon and if
the result is zero, it is outside the polygon. Make you tests handle
numeric rounding and errors. Degenerate case is when the point lies on a
segment of at a vertex.

2) Draw a line from t[x,y] to t[infinity,y] and intersect all the line
segments of the polygon with the line. Count the number of intersection,
if it is odd you are inside the polygon and if it is zero or even you
are outside the polygon. Be careful about the degenerate case when a
vertex of the polygon falls on the line, if both the other ends of the
segment are on the same side of the line count it as 0 or 2, if the
other ends are on opposite sides then count it as one, if both ends of
the segment line on the line then throw out the segment and test the
next line.

Hope this helps,
   -Steve Woodbridge
    http://imaptools.com