Re: polygon approximation/simplification -- "inner" and "outer" bounds

On Dec 11, 8:28 am, Jason S <jmsa...@xxxxxxxxx> wrote:
Hi -- I have a lot of point-in-polygon testing to do: thousands of
points against polygons representing land parcel boundaries. I have an
R-tree with the polygons so it greatly narrows down the set to be
tested, but still, some of the parcel boundaries have hundreds or even
thousands of boundary points. (Blame those stupid meandering rivers
and streams!!!)

The polygons are often non-convex, but are always non-self-
intersecting. (Some parcels may consist of several disconnected
polygons or a polygon with holes, but ignore these cases as I can
consider each simple polygon separately.)

I was wondering if there was a relatively straightforward way, given a
simple non-self-intersecting (but possibly non-convex) polygon P, to
precompute 3 or more simpler regions, defined by the following:

....

That approach should work, but your point-in-polygon test can be
sped up more with simpler tricks.

...or is there a simpler way to precompute regions for repetitive
point-in-polygon testing?

Yes, I think so. My ad valorem tax program processes 17-million
points against 2300 polygons (comprised of over 300,000 vertices)
in less than a minute on my 2-GHz machine.

I employ two tricks:
Segment trees -- Assuming that your point-in-polygon test is
counting polygon segments that intersect a vertical ray eminating
from that point, for each polygon, you sort the vertices by x-value
and construct a tree in which each node represents a range of
adjacent x values. Off of each tree node you then build a linked
list of pointers to the polygon segments that straddle that
interval. Thus, your point-in-polygon test need only traverse the
tree to find the interval containing that point's x-value, and then
loop through the short list of segments that lie vertically above
or below that point. My testing shows (as one would expect)
logrithmic performance improvement: a doubling of processing speed
for polygons with 160 vertices and a 10x improvement at 1000
vertices. I also determined that for polygons with fewer than 20
vertices, the performance improvement didn't warrant the time spent
constructing the segment tree, but of course, that's strictly a
function of the data I'm processing. The set-up time becomes
comparativley less significant as you process more points within
that polygon.

Gridding off the space -- Similar to the R-tree you've already
implemented, but simpler and faster. You simply define a grid that
partitions the range of x-y values, and then for each grid square,
you build a linked list of pointers to the polygons that contact
that square. If you make the grid small enough such that typical
polygons will contain several grid squares, then you can even
eliminate the need to run your point-in-polygon test (since every
point within that "enclosed" grid will be within that polygon).
This dramatically improves performance (by my testing of ad valorem
tax data, nearly two orders of magnitude) over the brute-force
method of testing every point against every polygon. As a further
enhancement, if you make your grid size a power of two and if your
test points and polygon vertices are specified by integer values,
then you might even use the C-language shift operator (thus
avoiding division) to find the x-y index values of the grid
containing that point. The price you pay for this point-in-polygon
performance gain is memory and set up time. If the polygon data is
relatively static (as are the city limits, etc. I process), then
you can archive the grid-to-polygon lists and directly load that
into memory on subsequence runs of new points against those same
polygons.

The data you're processing will greatly influence performance. For
a relatively small number of complex polygons processed against
millions of points, the two tricks I've proposed yield very
dramatic performance improvement. If your processing involves a
large number of small polyons (polygons with a small number of
vertices) being run on a small number of points (you mentioned
"thousands"), then you probably shouldn't bother constructing
segment trees (except perhaps for the largest of polygons).
.