What is the utility of Boost Polygon?

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

Garpike

I actually don't know a proper answer to the numeric accuracy conundrum. Maybe I'll add it to my answer later. – Subcritical

yes it is used, in production VLSI work. Everything in semiconductor fab needs to be exact, we're dealing with single atoms and single electrons at the limit... though in practice single-atom or single-molecule is still at the cutting edge of R&D. Regardless, integers are common... whether it is 1 micron, 1 nanometer, 1 picometer, that is dependent on the downstream tooling needs, and the "grids" those tools are based on (i.e. a lithography scanner might have interferometer based positioning accuracy to 1 angstrom (1/10th of a nanometer). – Eppes

@nmz787, good to know. Thank you. I now notice that the project is (was?) sponsored by Intel. It makes a lot of sense. – Garpike

Answer 1

Boost polygon is extremely useful for VLSI (very large scale integration) layouts in semiconductor manufacturing. There is an even an example on the boost polygon page. It has extremely good performance for Manhattan geometries and the integer types are precise enough to represent chip designs within a fraction of a nanometer. Integers are important because you need uniform precision along the entire span of a chip design, whereas floating point numbers have lower precision as numbers get larger.

It was developed and is still used at Intel.

https://www.youtube.com/watch?v=6MGLiIwc1_0&t=205s&ab_channel=nerd_mmccoo

Panoply

That's a very nice insight with ditto link. Welcome to Stack Overflow! – Subcritical

Answer 2

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>

Subcritical

Yesterday I created the tag boost-polygon so we can start identifying these questions in SO. Please use the tag if you find other questions (I found only 4 or 5). I am confused what is the use of Voronoi diagrams (or for that matter many other features) for integer coordinates. I am having the impression that the idea is to scale all the geometrical objects to MAX_INT, work with Boost.Polygon and go back to the original scale. – Garpike

Like I said. I cannot confirm/deny that. People are using it, perhaps that's a good place to start looking. I'm sure I saw applications that didn't seem toying. I wouldn't get stuck on that assumption (I haven't seen that kind of scaling before with Boost Polygon) – Subcritical

Thanks, I added an example of the polygon operations and how the behave strangely (by design apparently). – Garpike

Answer 3

Since the accepted answer is 6 years old I think it's worth pointing out that while the library is not completely abandoned, it is certainly heading that way and is firmly in maintenance mode.

At time of writing the most recent merged pull request is more than 1 year old.

Burble