Opened 12 years ago

Closed 12 years ago

#527 closed defect (fixed)

Union and UnaryUnion both fail at correctly node input lines

Reported by: strk Owned by: geos-devel@…
Priority: major Milestone: 3.3.4
Component: Default Version: 3.3.3
Severity: Unassigned Keywords:
Cc:

Description

GEOSUnaryUnion fails to correctly node this line:

MULTILINESTRING((1725063 4819121,1725104 4819067,1725060 4819087,1725064.14183882 4819094.70208557,1725064.13656044 4819094.70235069,1725064.14210359 4819094.70227252,1725064.14210362 4819094.70227252,1725064.13656043 4819094.70235069,1725055 4819094,1725055 4819094,1725055 4819094,1725063 4819121))

I'm assuming ST_IsSimple is a good sign of correct noding:

=# select ST_IsSimple( ST_UnaryUnion( 'MULTILINESTRING((1725063 4819121,1725104 4819067,1725060 4819087,1725064.14183882 4819094.70208557,1725064.13656044 4819094.70235069,1725064.14210359 4819094.70227252,1725064.14210362 4819094.70227252,1725064.13656043 4819094.70235069,1725055 4819094,1725055 4819094,1725055 4819094,1725063 4819121))' ) );
 st_issimple 
-------------
 f
(1 row)

}}}

Change History (12)

comment:1 by strk, 12 years ago

Uff, ST_IsSimple isn't a good check when it comes to _closed_ lines, in that they have no bounday so the node would be considered as an interior/interior intersection, like here:

MULTILINESTRING((0 0, 10 0, 10 10, 0 0), (0 0, -10 0, -10 -10, 0 0))

The boundary node rule is really getting in my way.

@mbdavis : how can I check for correct noding ? And is Polygonizer happy with noding which involves closed lines ?

/me goes on to try again the polygonizer call with more closed lines.

comment:2 by strk, 12 years ago

Checked: polygonizer is happy with closed components.

Wouldn't it be great if we discovered that the noding checker was also fooled by boundary node rule, throwing topology exceptions on perfectly good noding ? (found non-noded intersection etc.etc.)

comment:3 by strk, 12 years ago

A second attempt at checking for correct noding: compute intersection matrix between each pair of lines. Expected outcome: interior/interior intersection is always false in a correctly noded arrangement.

This confirms UnaryUnion isn't correctly noding:

with noded as ( 
 select ST_UnaryUnion( 
'LINESTRING(1725063 4819121,1725104 4819067,1725060 4819087,1725064.14183882 4819094.70208557,1725064.13656044 4819094.70235069,1725064.14210359 4819094.70227252,1725064.14210362 4819094.70227252,1725064.13656043 4819094.70235069,1725055 4819094,1725055 4819094,1725055 4819094,1725063 4819121)'
 ) as g ), 
dumped as (  select (st_dump(g)).* from noded ), 
matrices as ( select a.path as ap, b.path as bp, st_relate(a.geom, b.geom, 2) as im 
           from dumped a, dumped b where a.path < b.path) 
select ap, bp, im from matrices where ST_RelateMatch(im, 'T********');
 ap  | bp  |    im     
-----+-----+-----------
 {1} | {2} | 0F1F00102
 {2} | {5} | 1F1F00102
(2 rows)

So first and second line have puntual interior/interior intersection, while second and fifth line have lineal interior/interior intersection. Shouldn't happen, right ?

comment:4 by strk, 12 years ago

I've attached the script defining an SQL function to check for correct noding here: http://trac.osgeo.org/postgis/attachment/ticket/1735/CheckNoding.sql

comment:5 by strk, 12 years ago

Further analysis: the first attempt at running the union overlay op fails the internal noding validator step:

EdgeNodingValidator found noding invalid: TopologyException: found non-noded intersection between LINESTRING (1.72506e+06 4.81909e+06, 1.72506e+06 4.81909e+06) and LINESTRING (1.72506e+06 4.81909e+06, 1.72506e+06 4.81909e+06) at 1725064.1365604457 4819094.70235069

So SnapIfNeededOverlayOp switches on snapping, which seems to pass the check:

EdgeNodingValidator accepted the noding

Now it'd be interesting to see _why_ the internal edge noding validator passes while our own checking fails it !

comment:6 by strk, 12 years ago

Ah, I see the EdgeNodingValidator runs _before_ we re-add the common bits that we removed before runnign the operation. I bet the re-addition of commit bits is introducing more non-noded intersection. It would not be the first time I detect such behavior. I start thinking that removing common bits heuristic isn't such a good one.

comment:7 by strk, 12 years ago

Simplified input still reproducing the bogus noding:

LINESTRING(
 1725063 4819121,
 1725064.14183882 4819094.70208557,
 1725064.13656044 4819094.70235069,
 1725064.14210362 4819094.70227252,
 1725064.13656043 4819094.70235069,
 1725063 4819121
)

comment:8 by strk, 12 years ago

For the record: the IteratedNoder succeeds in noding the above input with 2 iterations, but the overlay operation isn't using the noding classes at all if I'm not mistaken.

comment:9 by strk, 12 years ago

I've to correct myself, it takes 5 iterations to correctly node the above!

Iteration1: # nodes created: 3
Iteration2: # nodes created: 3
Iteration3: # nodes created: 5
Iteration4: # nodes created: 5
Iteration5: # nodes created: 5
Iteration6: # nodes created: 0

Since IteratedNoder returns 19 output segments, many of which being duplicates, I'm not sure it's doing its work the way it's meant to.

comment:10 by strk, 12 years ago

With r3606 in 3.3 branch and r3607 in trunk the binary union is enhanced to always re-union (self union) the results of operations to which common bits are re-added. Doing so fixes this case and the PostGIS case http://trac.osgeo.org/postgis/ticket/1735

Unary union itself is still not fixed in that it takes a different path (doesn't use BinaryOp). May be worth updating it to use BinaryOp as well, but must be aware of possible infinite loops as one would be calling the other...

comment:11 by strk, 12 years ago

r3608 in 3.3 branch and r3609 in trunk/3.4 also switch unary union over. I'll work on an automated testcase before closing this.

comment:12 by strk, 12 years ago

Resolution: fixed
Status: newclosed

r3610 / r3611 add a testcase for this (3.3 / trunk)

Note: See TracTickets for help on using tickets.