Bug 84032 - Intersection of some polygons produces wrong result
Summary: Intersection of some polygons produces wrong result
Status: NEW
Alias: None
Product: LibreOffice
Classification: Unclassified
Component: Draw (show other bugs)
Version:
(earliest affected)
Inherited From OOo
Hardware: All All
: medium normal
Assignee: Not Assigned
URL:
Whiteboard:
Keywords:
Depends on:
Blocks: 86211 100042
  Show dependency treegraph
 
Reported: 2014-09-18 08:58 UTC by vvort
Modified: 2024-03-20 14:40 UTC (History)
4 users (show)

See Also:
Crash report or crash signature:


Attachments
Test file (10.76 KB, application/vnd.oasis.opendocument.graphics)
2014-09-18 08:58 UTC, vvort
Details
Graphical explanation (11.83 KB, image/png)
2014-09-18 09:05 UTC, vvort
Details
Modified sample ODG illustrating how line thickness and Z-order matter (24.04 KB, application/vnd.oasis.opendocument.graphics)
2024-03-20 01:24 UTC, Stéphane Guillou (stragu)
Details

Note You need to log in before you can comment on or make changes to this bug.
Description vvort 2014-09-18 08:58:50 UTC
Created attachment 106486 [details]
Test file

Open 'intersect_bug.odg', select circle (A) and ring (B) objects, run Modify->Shapes->Intersect.
The resulting polygon (A ∩ B) must be equal to ring (B), not to A \ B.

Tested with version 4.4.0.0.alpha0+ (f39ed4c680fe8ef2ea3f0ace91ea3175551ec9c5)
Comment 1 vvort 2014-09-18 09:05:04 UTC
Created attachment 106487 [details]
Graphical explanation
Comment 2 V Stuart Foote 2014-11-12 16:35:04 UTC
Confirmed on Windows 7 sp1, 64-bit en-US with
Version: 4.3.4.1
Build ID: bc356b2f991740509f321d70e4512a6a54c5f243

and
Version: 4.4.0.0.alpha2+
Build ID: 9229170920ab770624415c4330da57af5b1b5398
TinderBox: Win-x86@39, Branch:master, Time: 2014-11-09_03:16:43
Comment 3 QA Administrators 2015-12-20 16:17:47 UTC Comment hidden (obsolete)
Comment 4 ZioTibia81 2015-12-20 21:21:52 UTC
Problem persist:

Version: 5.0.4.2 (x64)
Build ID: 2b9802c1994aa0b7dc6079e128979269cf95bc78
Locale: it-IT (it_IT)
Comment 5 QA Administrators 2017-09-01 11:19:35 UTC Comment hidden (obsolete)
Comment 6 V Stuart Foote 2018-12-16 14:53:11 UTC
Steps to reproduce with changes to menus, but issue remains with
Version: 6.1.4.2 (x64)
Build ID: 9d0f32d1f0b509096fd65e0d4bec26ddd1938fd3
CPU threads: 4; OS: Windows 10.0; UI render: GL; 
Locale: en-US (en_US); Calc: CL

and current master/6.3.0
Comment 7 QA Administrators 2020-12-16 03:57:35 UTC Comment hidden (obsolete)
Comment 8 ZioTibia81 2020-12-16 08:47:57 UTC
Still in:

Version: 7.0.3.1 (x64)
Build ID: d7547858d014d4cf69878db179d326fc3483e082
CPU threads: 24; OS: Windows 10.0 Build 19041; UI render: Skia/Raster; VCL: win
Locale: it-IT (it_IT); Interfaccia utente: it-IT
Calc: threaded
Comment 9 QA Administrators 2022-12-17 03:19:31 UTC Comment hidden (obsolete)
Comment 10 Stéphane Guillou (stragu) 2024-03-20 01:24:26 UTC
Created attachment 193207 [details]
Modified sample ODG illustrating how line thickness and Z-order matter

Still as described in:

Version: 24.8.0.0.alpha0+ (X86_64) / LibreOffice Community
Build ID: 479b5bbe8ca2177ba7574e7aa2308b5d0de1895c
CPU threads: 8; OS: Linux 6.5; UI render: default; VCL: gtk3
Locale: en-AU (en_AU.UTF-8); UI: en-US
Calc: CL threaded

Same in OOo 3.3, so behaviour is inherited.

But to me it is not clear that this is a bug, or what the bug is:
- I understand the intersection to be "everything that is contained in all of the objects simultaneously"[1], which for two overlapping circles, with a line thickness of 0, would include a fill if it exists.
- If the line has a non-zero thickness, and there is no fill, then it makes sense to use that ring for the intersection.
- In the sample file, the grey disc is a "Bézier curve", and the circle is "polygon with 400 corners". I'm not sure why the object is presented as an empty pink circle when its Line has "Style: none" and its area is filled with pink.
- LO uses the object styling (area fill, line properties...) of the object that is behind for the resulting intersection object. In the original sample, the circle is at the front, so the styling used is the grey disc's. If the Z-order is switched, the result is a pink disc.
- If the objects are copied, result is different: 0-corner polygon regardless of Z-order.

See attached modified sample, with shape examples illustrating how Z-order and line thickness matter.

IMO, the actual issues are:
* Display of original objects:
   - line visible even though it's set to "none", uses fill colour;
   - no fill visible even though it is set to solid colour;
* Intersection of copies results in 0-corner polygons.

Version: 24.8.0.0.alpha0+ (X86_64) / LibreOffice Community
Build ID: 479b5bbe8ca2177ba7574e7aa2308b5d0de1895c
CPU threads: 8; OS: Linux 6.5; UI render: default; VCL: gtk3
Locale: en-AU (en_AU.UTF-8); UI: en-US
Calc: CL threaded

[1]: https://en.wikipedia.org/wiki/Intersection
Comment 11 Stéphane Guillou (stragu) 2024-03-20 01:26:21 UTC
Regina, do you have any insights regarding my comment 10? (In particular on differences between object types, my knowledge is limited on the topic.)
Comment 12 Regina Henschel 2024-03-20 14:40:57 UTC
I'm not an expert with "intersection". But Armin should know.

The relevant methods are
https://opengrok.libreoffice.org/xref/core/svx/source/svdraw/svdedtv2.cxx?r=b26ddd42&fi=MergeMarkedObjects#991
and
https://opengrok.libreoffice.org/xref/core/basegfx/source/polygon/b2dpolypolygoncutter.cxx?r=7979508e&fi=solvePolygonOperationAnd#969

As far as I know, there are these principles:
(1) Intersection is done on the area which is enclosed by a polygon.
(2) Objects are converted to contour during the intersection process. Thus an object with a hairline stroke becomes one object, but an object with a thick stroke becomes two objects, one for the stroke and one for the fill.
(3) The resulting object gets the style of the object furthest back.

The "Test file" (attachment 106486 [details]) has a "ring" object which is a polypolygon with stroke none, fill color #ff9999 and 0% transparency, and a "circle" object which is a path with stroke none, fill color #dddddd and 50% transparency. The "ring" is in front. It looks as if it is completely on the area of the "circle". Therefore I expect as result of intersecting a ring with stroke none, fill color #dddddd and 50% transparency. So for me it is a bug.

There might be a problem with working in integer, because the coordinate differences between outer part of ring and circle are in range of 1/100 mm. When you first convert the circle (which is a Bezier curve) to polygon and then intersect the objects, then you get the Gray ring I expect.