Michael Michaud wrote:
Hi,
More on this topic...
I've been doing some testing of my prototype implementation of
"Buffer Input Simplification". This uses a special-purpose
linestring simplification algorithm which weeds out *concave*
sections of the linework, but leaves *convex* sections untouched (up
to a given tolerance). This is based on the observation that as
buffers get larger, the concave sections contribute less and the
convex areas more to the shape of the final buffer. In the limit,
very large buffers are simply "blobs", which are dominated by a only
a few of the larger "protrubances" in the input curve.
Interesting !
Can we extrapolate and consider that in the limit the buffer of the
line equals the buffer of its convex hull ?
Yes, I think that's correct. Determining what that limit is is the
tricky part! In any case, the limit case for the "Buffer Input
Simplifier" is the convex hull of the input.
Using this simplification technique with a conservative tolerance
produces high-quality buffers which are very close to the "pure"
buffer compute by the current JTS code (which is itself an
approximation). The best part is that by linking the tolerance
factor to the buffer distance, as the distance goes up the
performance of generating the overall buffer increases
dramatically! Some results (using Michael's test geometry) are
given here:
How do you make sure that your conservative tolerance is, in fact,
conservative. Anyway, results are impressive, and having job done
faster for larger buffers is an excellent and unexpected result.
About your outputs compared to "pure buffer", I realize that buffer
outputs are never "pure" (because of curved parts) and it could make
sense to simplify the input line in a way which is both consistent
with the buffer size and the "segments per quadrant" parameter (but it
may be difficult to "measure" how the input line simplification will
impact the precision buffer output).
Re the choice of "conservative tolerance": As you point out, the
accuracy of the generated buffer is primarily determined by the choice
of resolution of the approximations to the circular arcs around convex
vertices. This is controlled by the "quadrant segments" parameter in
JTS. The default setting is 8 lines per quadrant, which gives a
difference from the true arc of < 1%. By using a tolerance distance for
the simplification which is well below this, there should be essentially
no impact from the simplification. I actually used a tolerance of 10
times less than this (0.001). (I used a fixed tolerance, but it would
be easy to make it depend on the users choice of quadrantSegments value).
If I can help with tests, I'll try to do my best on my spare time.
Great!
I actually have run into a bit of a snag with the simplification
algorithm, so I'm going to have to think my way thru that before
carrying on. I'll post when I make some progress.
Michaël
--
Martin Davis
Senior Technical Architect
Refractions Research, Inc.
(250) 383-3022
_______________________________________________
jts-devel mailing list
[email protected]
http://lists.refractions.net/mailman/listinfo/jts-devel
