alfC - 1 year ago 113

C++ Question

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 typeis a template parameter of all data types and

algorithms provided by the library, andis expected to be integral.

Floating point coordinate data types are not supportedby 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.

I understand that Computational Geometry with floating-points is very painful,

Bonus question:

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)`

`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)`

`polygon(-500,0)(-100,-200)(300,400)(-300,200)`

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.

Answer Source

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>
```