What is the utility of Boost Polygon?

问题:

This is a question about Boost Polygon (not about Boost Geometry)

Recently I was trying to play with some geometrical polygon constructions. Since Boost Geometry (a different library which also deals with polygons) is not working circumstantially in Boost 1.58 I though I would give a try to Boost Polygon.

After trying to understand the library and not getting the expected results I discovered that the library only works for integer coordinates. At first I though that this was a limitation for input, but in fact all internal operations and outputs are integers, this makes all output quite quirky, for example, the intersections for polygons are slightly deformed (because the coordinates of vertices have to be integers).

A quote from the main page (emphasis mine):

The coordinate data type is a template parameter of all data types and algorithms provided by the library, and is expected to be integral. Floating point coordinate data types are not supported by the algorithms implemented in the library due to the fact that the (sic) achieving floating point robustness implies a different set of algorithms and generally platform specific assumptions about floating point representations.

At first I though that it was a problem between exact and inexact representation so I tried to make it work with rational (Boost Rational) types (I figured out a wrapper rational class to make it compile) but actually the integer coordinates is a strict requirement (There are parts in the code that actually add and substract one to construct intermediate results).

Going back to integers, I had to make the coordinates very big (in integer terms) to make this discreteness problem disappear. In other words I have to normalized everything back and forth. Well, at the end it is not very useful or convenient as I originally thought.

Am I missing something important about the use of this library?

Is this library intended for "pixelated" problems? What is the utility if the coordinates are restricted to be integers?

Is the idea to scale the coordinates to very big numbers and then renormalize the results later for geometric applications?

I understand that Computational Geometry with floating-points is very painful, but why this library doesn't even try to be compatible with exact rationals?

Are there real examples of use? (The manual is pretty bad at giving examples) Is anyone actually using this library?

Bonus question: Is this an abandoned library?

---

This is an example of how the library behaves from the integer coordinates:

Here it is an example of what happens with integral polygons, If I use small numbers to represent the coordinates the results are not even geometrically consistent. (The two polygons are polygon(-2,0)(2,-2)(6,4)(0,2) and polygon(-5,0)(-1,-2)(3,4)(-3,2))

(note how skew everything comes out.)

But when I scale the polygons to have large integer coordinates the results get more exact (The two polygons are polygon(-200,0)(200,-200)(600,400)(0,200) and polygon(-500,0)(-100,-200)(300,400)(-300,200), scaled versions of the two above.):

---

EDIT: I learned a bit more of computational geometry, apparently the robustness of computational geometry is a very difficult problem. One of the strategies is to use integer arithmetic. It looks like Boost.Polygon takes this approach. Problems in continuous space should be scaled appropriately.

回答1:

It's not abandoned.

Yes it's used by (many) people.

One thing that it does that seems to have a solid user base is e.g. Voronoi diagrams and related algorithms. You can find a good number of questions about that on SO too, so you could head over to see what they use it for.

Bonus answer

You can even combine the libraries by using

#include <boost/geometry/geometries/adapted/boost_polygon.hpp>