Intersecting integer polygons produces incorrect or self-intersecting result

[starinshak1@…]

I've noticed several instances of Boost.Geometry returning incorrect or self-intersecting polygons when working in integers (32 and 64 bit).

EXAMPLE: Polygon A has vertices (42817136,-3774506), (43029074,-3929862), (31446819,18947953), (30772384,19615678), (30101303,19612322), (30114725,16928001), (33520458,6878575), (35332375,2413654), (35725796,2024148), (42817136,-3774506)

Polygon B has vertices (-33386239,-33721784), (33721785,-33386239), (33386240,33721785), (-33721784,33386240)

Intersecting Polygon A and Polygon B returns:

A correct but self-intersecting polygon using Boost 1.55

An incorrect polygon using Boost 1.57 and int64_t coordinates

An incorrect and self-intersecting polygon using Boost 1.57 and int32_t coordinates.

For both Boost 1.57 tests, I enabled BOOST_GEOMETRY_NO_ROBUSTNESS to avoid floating point rescaling.

[mkaravel]

Hi.

AFAIC, the macro BOOST_GEOMETRY_NO_ROBUSTNESS has nothing to do with your findings, as rescaling is only activated for floating-point coordinates.

I tried your example polygons, and I could reproduce the problem when the coordinate type is int32_t, but could not reproduce it for int64_t. Could you please check again against the latest Boost.Geometry version in the develop branch, and also report the output polygons you get?

My understanding is that your polygons are CCW and open. Correct?

Menelaos

[starinshak1@…]

Replying to mkaravel:

Hi Menelaos,

The polygons in my original example are CCW and closed. In testing, I initialize them with an open string of coordinates can call boost::geometry::correct to close them.

Using the 1.58.0 release of Boost.Geometry, I now reproduce your findings for this problem: the polygon resulting from the intersection is self-intersecting for int32_t coordinates but non-self-intersecting for int64_t coordinates. However, when you plot the result, it is incorrect for both integer types (and incorrect in different ways).

I have another example that further compounds this error: POLYGON((241774944 270613768, 249104265 268648604, 258263822 277993222, 262822082 304885727, 253206525 344982011, 240074874 272654983)) POLYGON((225182076 225182076, 292290940 225182076, 292290940 292290940, 225182076 292290940))

These are also CCW-oriented polygons. I now get the reverse behavior as the original example:

If I intersect them using int32_t coordinates, the result POLYGON((252873436 292290940, 240074874 272654983, 241774944 270613768, 249104265 268648604, 258263822 277993222, 268109663 336081032, 252873436 292290940)) does NOT self-intersect.

If I intersect them using int64_t coordinates, the result POLYGON((240075109 272653826, 240074874 272654983, 241774944 270613768, 249104265 268648604, 258263822 277993222, 262823538 304883653, 240075109 272653826)) does self-intersect.

As before, the polygon resulting from the intersection is not correct.

Dave

Hi.

AFAIC, the macro BOOST_GEOMETRY_NO_ROBUSTNESS has nothing to do with your findings, as rescaling is only activated for floating-point coordinates.

I tried your example polygons, and I could reproduce the problem when the coordinate type is int32_t, but could not reproduce it for int64_t. Could you please check again against the latest Boost.Geometry version in the develop branch, and also report the output polygons you get?

My understanding is that your polygons are CCW and open. Correct?

Menelaos