boostorg / boostorg/geometry

Incorrect results of boost::geometry::difference (using mpq_rational)

Open
#1,212 7 comments 0 reactions 0 assignees View on GitHub
bug
Dominant language
C++
Stars
517
Forks
232
PR merge metrics
No merged PRs in 30d

Description

Hi~, under version 1.83 (same as 1.81), I seem to have encountered an operation result error of boost::geometry::difference(r1, r2, res). The following is the corresponding polygon data:

r1 = POLYGON((850000 0,1330000 320000,1350000 500000,1180000 1280000,790000 1280000,290000 1270000,220000 1190000,160000 1120000,30000 770000,20000 620000,0 110000,850000 0),(510711 675561,620711 945561,680711 735561,510711 675561),(1035911 461661,835911 421661,715911 361661,725911 381661,795911 411661,655911 501661,655911 541661,715911 591661,755911 691661,815911 821661,695911 761661,705911 781661,775911 811661,635911 901661,635911 941661,695911 991661,735911 1091661,795911 1221661,656523 1221661,526523 1241661,846523 1221661,925911 1221661,1025911 1201661,855911 1071661,735911 1031661,779571 1009831,915911 941661,1055911 971661,1065911 761661,1045911 801661,875911 671661,755911 631661,935911 541661,1075911 571661,1085911 361661,1035911 461661));
r2 = POLYGON((711861 626536,741861 656536,651861 836536,711861 626536))

Among them, polygon r1 is a polygon containing two holes, and r2 is a simple polygon, as shown in the following figure:
![error](https://github.com/boostorg/geometry/assets/53161611/175d9a1e-0a25-4010-9752-640816c71815)

The operation directly caused one of the holes to disappear, as shown in the figure below:
![error_res](https://github.com/boostorg/geometry/assets/53161611/6fb7cdbc-fcf9-4059-920c-678e9dc42456)

It is worth mentioning that the coordinates of all vertices of these two polygons are integers, and I use boost::multiprecision::mpq_rational as my basic data type, so in theory, there is no calculation precision error.

The possible problem is that the polygon r2 is in touch with two holes of polygon r1 simultaneously, forming a complex polygon Boolean operation that leads to wrong results.

Could you reproduce this situation?

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.