Ticket #244 (closed defect: fixed)

Opened 4 years ago

Last modified 4 years ago

Buffer fails to buffer elements of multpolygon

Reported by: pramsey Owned by: strk
Priority: major Milestone: 3.1.1
Component: Default Version: 3.0.3
Severity: Critical Keywords:
Cc: randre@…, mbdavis@…

Description

Buffering the attached multipolygon, one of the elements is dropped during the process.

Attachments

papua_wkb.txt Download (96.3 KB) - added by pramsey 4 years ago.
New Guinea Multipolygon HEXWKB
bug244.xml Download (206.5 KB) - added by strk 4 years ago.
bug244-simp1.xml Download (45.5 KB) - added by strk 4 years ago.
Simplified testcase. Multipolygon has 5 polygons none with hole, output of buffer(0) contain only 2 of them.
bug244-simp2.xml Download (43.3 KB) - added by strk 4 years ago.
4 polys input, 1 poly buffer0 output

Change History

Changed 4 years ago by pramsey

New Guinea Multipolygon HEXWKB

Changed 4 years ago by strk

Confirmed, still a problem. From 52 polygons to 48. Input is found to be valid. This is an ugly bug occasionally popping out in different situations. For example the geom in bug #219 also trigger a silent "eat-up" of a component (well, input is invalid in that case).

Another case (giving more informations about how bad this bug is) is TestBufferExternal?2.xml, which contain a test in which you get an EMPTY geometry from a buffer operation depending on -ffloat-store. Check buildbot for the history of this, or build w/out -ffloat-store on a 32bit system and run make check.

Changed 4 years ago by strk

Changed 4 years ago by strk

I attach an XML tester, Martin any tip from your side ? How does JTS deal with that ?

Changed 4 years ago by strk

I've verified that all components of input geometry are Polygons with no holes. All are valid. All cleanly buffer(0)...

Changed 4 years ago by strk

of the 52 polygons, 52 BufferSubgraphs? are created and passed to PolygonBuilder? which returns 48 polygons only.

Changed 4 years ago by strk

Simplified testcase. Multipolygon has 5 polygons none with hole, output of buffer(0) contain only 2 of them.

Changed 4 years ago by strk

bug244-simp1.xml is a simplification of the testcases. The input multipolygon contains 5 polygons, none with holes. 2 are returned by buffer(0).

Changed 4 years ago by strk

4 polys input, 1 poly buffer0 output

Changed 4 years ago by strk

bug244-simp2.xml yet another simplification. This time it's 4 polygons input. Note that dropping any more polygon from input results in a correct output. Keeping all of 4 polygons results in a single polygon output

orig |

: MultiPolygon?[BS] with 3 elements : Polygon[] with 1 rings : ring 0 has 204 points : Polygon[] with 1 rings : ring 0 has 404 points : Polygon[] with 1 rings : ring 0 has 25 points :

buffered |

: Polygon[BS] with 1 rings : ring 0 has 204 points :

Changed 4 years ago by strk

Ehm, you may have noticed the input polygons are 3, not 4. The rest applies.

Changed 4 years ago by strk

This seems interesting. Of the 3 calls to ::buildMaximalEdgeRings, each for each polygon in input, only one returns a "maxEdgeRing":

0x7fff2ad7da30] PolygonBuilder::buildMaximalEdgeRings got 2 dirEdges 0x7fff2ad7da30] PolygonBuilder::buildMaximalEdgeRings returning 1 maxEdgeRings

0x7fff2ad7da30] PolygonBuilder::buildMaximalEdgeRings got 2 dirEdges 0x7fff2ad7da30] PolygonBuilder::buildMaximalEdgeRings returning 0 maxEdgeRings

0x7fff2ad7da30] PolygonBuilder::buildMaximalEdgeRings got 2 dirEdges 0x7fff2ad7da30] PolygonBuilder::buildMaximalEdgeRings returning 0 maxEdgeRings

Changed 4 years ago by strk

  • cc mbdavis@… added

Alright, got to build JTS correctly and added debugging traces there. So far I'm in BufferBuilder?, where depths are computed and result edges found. JTS and GEOS differ in the depths they compute:

JTS goes like this:

(1)

dirEdge 0 inResult:false isArea:true leftDepth:1 rightDepth:0 dirEdge 1 inResult:true isArea:true leftDepth:0 rightDepth:1

(2)

dirEdge 0 inResult:true isArea:true leftDepth:0 rightDepth:1 dirEdge 1 inResult:false isArea:true leftDepth:1 rightDepth:0

(3)

dirEdge 0 inResult:false isArea:true leftDepth:1 rightDepth:0 dirEdge 1 inResult:true isArea:true leftDepth:0 rightDepth:1

GEOS, on the other hand, gets to compute depths > 1 for polygon 2 and 3 (the ones that disappear from output):

(1) <--- FINE

dirEdge 0 inResult:0 isArea:1 leftDepth:1 rightDepth:0 dirEdge 1 inResult:1 isArea:1 leftDepth:0 rightDepth:1

(2) <--- BOGUS DEPTHS !

dirEdge 0 inResult:0 isArea:1 leftDepth:1 rightDepth:2 dirEdge 1 inResult:0 isArea:1 leftDepth:2 rightDepth:1

(3) <--- BOGUS DEPTHS !

dirEdge 0 inResult:0 isArea:1 leftDepth:2 rightDepth:1 dirEdge 1 inResult:0 isArea:1 leftDepth:1 rightDepth:2

Martin, I'll keep going, if anything rings a bell there please let me know :)

Changed 4 years ago by strk

In JTS, SubgraphDepthLocater? finds outsideDepth=0 for all input polygons In GEOS, it finds outsideDepth=0 for the first, =1 for the second and third (the one not getting into the result)

Changed 4 years ago by strk

  • owner changed from geos-devel@… to strk
  • status changed from new to assigned

Oh well, GEOS was playing too much with references where copies where needed. DepthSegment? was being passed the same LineSegment? reference, while changing the LineSegment? value...

Changed 4 years ago by strk

  • status changed from assigned to closed
  • resolution set to fixed
  • severity changed from Unassigned to Critical

Changed 4 years ago by warmerdam

It appears the relavent patch was r2503 in trunk, I see no sign that it has been backported.

Note: See TracTickets for help on using tickets.