Re: [boost] Formal Review: Boost.Polygon starts today August 24, 2009

Subject: Re: [boost] Formal Review: Boost.Polygon starts today August 24, 2009
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2009-08-25 16:31:03

Phil Endecott wrote:
> Dear Luke & others,
> 
> Congratulations on getting this library as far as a review.  I feared
> that the scope of the subject might make it impossible for anyone to
> ever get this far.  Perhaps we have Luke's employer to thank for this.

Yes, I have thanked my employer.  It has been years of work and I feel very fortuante to have been allowed the opportunity to get this far.
 
> I hope to have time to try out the library with at least a couple of
> real-world examples.  I'll describe the problems that I have in mind
> now and update later with my experiences.
> 
> Marker Merging:  I have lots of small square markers indicating search
> results on a map.  If the map is zoomed out so that the whole planet
> is 
> visible and you search for something common like "lake", it will
> attempt to draw many thousands of overlapping markers which is slow.
> Since the markers are just squares of solid colour, I would like to
> merge them into a single polygon-set and plot that.  Speed is the main
> concern.  It it also interesting to consider what would happen if the
> markers were circles.  Here's an example of the sort of output I
> need:  http://chezphil.org/tmp/six_thousand_lakes.jpeg 

This will be blazingly fast with my specialized manhattan implementation.  The general implementation will switch to the manhattan algorithm dynamically if the data is manhattan, but if you use the manhattan types/concepts it selects the correct algorithm at compile time.

> Border Simplification:  I have data describing state outlines as
> polygon-sets.  I want to pre-process that into a format that permits
> rapid rendering; specifically, I want to generate multi-resolution
> versions with smoothing and interpolation as necessary.  I also want
> to 
> reduce it from polygons with common edges to polylines, so that each
> border is plotted once rather than twice.  This is something that
> happens off-line as part of a build process, so speed is much less
> important than ease of coding.  Example output:
> http://chezphil.org/tmp/state_borders.jpeg  (yes, it's an iPhone
> app... 
> hey, we all have to pay the rent somehow...)

I don't have a smooth algorithm because the definition is sort of fuzzy.  There are many smoothing algorithms to choose from.  It is also straightforward to implement oneself, unlike sweepline.

To eliminate borders that would be plotted twice you can easily find duplicate edges by sorting and discovering duplicates as neighbors.  From there assign unique ids to each polygon and disable its edges if there is a polygon with greater id that has the same edge.  This disables common borders, is n log n, and shouldn't be hard to implement based upon stl and my library.  I define less than on point_data<T>, which is about all you need.

I'd love to have my code running on an iphone.  I pulled out iostream deps to make it more friendly to compile targeting small form factors. 

If you implement these examples I'd be happy to add them to the docs and put a thank you in there for you.

> p.s. has anyone worked out where this thread has gone on gmane.org?

What is gmane.org?

Thanks,
Luke