Re: [Boost-users] [Boost.Polygon] support for polygons with holes

Subject: Re: [Boost-users] [Boost.Polygon] support for polygons with holes
From: Björn Piltz (bjornpiltz_at_[hidden])
Date: 2011-09-13 05:29:10

Ok,
here is my D-P implementation:
https://bitbucket.org/bjornpiltz/boost_polygon_dp.
When I tried to refactor the line-to-point distance calculation from
simplify(), I realized it wasn't working correctly. I have replaced it, but
I would suggest you have a look at it.

All the best
Björn

2011/9/8 Simonson, Lucanus J <lucanus.j.simonson_at_[hidden]>

> Björn Piltz wrote:
> >>      All functionality is supported for the polygon_with_holes concept.
> >> I consider it to be the normal case.
> >
> > Thanks, that's a relief!
> > I use my own containers and I missed that I had to declare
> > polygon_traits as well as polygon_with_holes_traits for my
> > PolygonsWithHoles class. Now things are working like a charm.
> > I'm very happing being able to map Qt's QPolygon to Boost.Polygon
> > since this gives me full rendering capabilities.
>
> I'm glad to hear it.  For some reason this email ended up misidentified as
> spam and went to my Junk E-mail folder, so please excuse the lateness of my
> response.
>
> > I do have a couple of issues and I thought I'd let you know. I'm not
> > sure if they are outside the scope of the library, so I'll let you be
> > the judge of that.
> >
> > 1.
> > Is there an easy(and computationally cheaper) way to check if two
> > simple polygons intersect?
> > other than: !boost::polygon::empty(a & b). If not, is such
> > functionality planned?
>
> You should check if their bounding boxes intersect first and then do the
> expensive check only if there is intersection between the bounding boxes.
>
> > 2.
> > The simplify() algorithm seems to be a bit greedy. I have a hard time
> > thinking up a small example, but I can see it clearly on some larger
> > GIS-datasets. The algorithm starts chipping away at some corner,
> > removing unneeded vertices, but in some cases it doesn't stop until
> > the whole polygon is gone. It seems to me it should work a bit more
> > like Douglas-Peucker:
> >
> >       Everytime a point P is removed, creating a line between A and B,
> all
> > previously removed points between A and B should be checked against
> > the line, and if any of the points end up to far from the line
> > removal of P is rejected
> >
> > The way it works now, the accumulated error can be great.
>
> Yes, I see your point.  In my testing on CAM data that contained a large
> number of nearly colinear line segments as an artifact of meshing in
> addition to the sharp angles of man made geometry the operation seemed to be
> performing well removing the artifact vertices but retaining the ones that
> were desired features of the figure, however, I can imagine that for GIS
> data things could turn out much different since all vertices would be
> qualitatively similar.  The way I implemented the simplify operation the
> threshold is interpreted as a lower bound instead of an upper bound, which
> makes the result unpredictable.
>
> > 3.
> > Are there potentially more ways the user can help the library? Right
> > now the user can override polygon_traits<>::winding(), which is
> > otherwise O(N). Couldn't the same be done for area, bounding box and
> > concavity. The bounding box is of course useful for speeding up all
> > boolean operators and knowing concavity speeds up hit tests (
> > contains(point_type) ) This could be calculated in one sweep. No
> > boiler plate code needed if there would be polygon_default_traits
> > returning winding_unknown, concavity_unknown, etc.
>
> It is easy to imagine a polygon object that caches its area and bounding
> box.  You can override any free function in the library (like area()) by
> defining your own overload of the function that accepts your type, or
> partial specialization for your specific type.  Frequently the compiler
> fails to inline the accessor functions for simple data structres like point
> or rectangle resulting in less-than-zero-cost abstraction.  We address this
> (when benchmarking shows it is a problem) by overloading or partial
> specialization of the free functions that use the accessors through the
> traits to instead access the data type directly.  I suppose it is possible
> to define an extended set of traits for many of the free functions that
> default to the current implementation (similar to winding), but it is hard
> to know where to draw the line, and it wouldn't be easier for the user than
> just overloading, but it would be more obvious, but it would be much more
> work for me.  I chose to provide the winding trait because I call winding
> very frequently, yet it is very common for winding to be a class invariant
> and known actually at compile time and so have O(0) runtime complexity.
>  Perhaps we can add an example showing how to override free functions for
> performance.
>
> > Otherwise, like I said before, it works like a charm.
>
> I'm very glad to hear it.  I made correctness with intuitive and simple to
> use interfaces my priority.  With feedback from the boost community I also
> cleaned up all the compiler warnings and fixed compatibility issues with the
> various compilers and versions thereof.  Getting the functionality to you
> was a little like getting a block of cheese through a cheese grater.  I had
> to limit the scope a little and work a lot.  Contributions from the
> community are very welcome, both patches and new features.  The simplify
> algorithm was actually a contributed by a user of the library who had a CAM
> application.  If you would like to contribute a Douglas-Peucker
> implementation (perhaps you were forced to write your own) I'd be very happy
> to integrate it, document it and get it into the next release.
>
> Thanks,
> Luke
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>