Opened 8 years ago

Closed 8 years ago

Last modified 8 years ago

#1302 closed defect (fixed)

AddFace getting left/right wrong

Reported by: strk Owned by: strk
Priority: medium Milestone: PostGIS 2.0.0
Component: topology Version: master
Keywords: Cc:

Description (last modified by strk)

Next bug in the series derived from dataset in #1274. This one seems related to robustness of computation of next_left_edge and next_right_edge, which is based on ST_Azimuth.

The error actually comes from topology.AddEdge

Attachments (1)

self_contained_bug.sql (943 bytes) - added by strk 8 years ago.
self contained testcase triggering the error

Download all attachments as: .zip

Change History (14)

Changed 8 years ago by strk

Attachment: self_contained_bug.sql added

self contained testcase triggering the error

comment:1 Changed 8 years ago by strk

Component: postgistopology
Description: modified (diff)
Owner: changed from pramsey to strk
Summary: ST_CreateTopoGeo: ERROR: Edge 5 has face 0 registered on the side of this face, while edge 4 has face 2 on the same sideST_AddEdgeModFace: ERROR: Edge 5 has face 0 registered on the side of this face, while edge 4 has face 2 on the same side

comment:2 Changed 8 years ago by strk

I've carefully read the DEBUG notices and it looks to me as the azimuth computation and startpoint-endpoint analisys is all good. This leaves AddFace? as the most likely culprit.

comment:3 Changed 8 years ago by strk

The problem seems to be in figuring out on which side of an edge the newly added face is.

comment:4 Changed 8 years ago by strk

Summary: ST_AddEdgeModFace: ERROR: Edge 5 has face 0 registered on the side of this face, while edge 4 has face 2 on the same sideAddFace getting left/right wrong

Here's a small testcase:

--
-- Test narrow face. 
--
SELECT '#1302', topology.CreateTopology('tt') > 0;

SELECT '#1302', 'E' || topology.addEdge('tt', '01020000000300000000917E9BA468294100917E9B8AEA2841C976BE1FA4682941C976BE9F8AEA2841B39ABE1FA46829415ACCC29F8AEA2841');
SELECT '#1302', 'E' || topology.addEdge('tt', '010200000003000000B39ABE1FA46829415ACCC29F8AEA284137894120A4682941C976BE9F8AEA284100917E9BA468294100917E9B8AEA2841');
SELECT '#1302', 'F' || topology.addFace('tt', '0103000000010000000500000000917E9BA468294100917E9B8AEA2841C976BE1FA4682941C976BE9F8AEA2841B39ABE1FA46829415ACCC29F8AEA284137894120A4682941C976BE9F8AEA284100917E9BA468294100917E9B8AEA2841');

SELECT '#1302', 'E' || edge_id, 'L' || left_face, 'R' || right_face FROM tt.edge_data ORDER BY edge_id;

SELECT topology.DropTopology('tt');

Both edges will end up having the face on the wrong side.

comment:5 Changed 8 years ago by strk

Analisys changed, the issue seems to be related to ForceRHR. Is this clockwise or counterclockwise ?

0103000000010000000500000000917E9BA468294100917E9B8AEA284137894120A4682941C976BE9F8AEA2841B39ABE1FA46829415ACCC29F8AEA2841C976BE1FA4682941C976BE9F8AEA284100917E9BA468294100917E9B8AEA2841

Make it clockwise if you can. ForceRHR doesn't seem to do that.

comment:6 Changed 8 years ago by strk

Note we're talking about an area of 4.1665335341137e-06 units

comment:7 Changed 8 years ago by strk

Note: there's _no_ regression testing for ST_ForceRHR

comment:8 Changed 8 years ago by strk

That's lwgeom_force_clockwise at the liblwgeom side of things. Still not tested in cunit.

comment:9 Changed 8 years ago by strk

A-ha, found something interesting thaanks to valgrind (and cunit testing):

==17918== Source and destination overlap in memcpy(0x65f5ec0, 0x65f5ec0, 16)
==17918==    at 0x4C28E2A: memcpy (mc_replace_strmem.c:497)
==17918==    by 0x4E43361: ptarray_reverse (string3.h:52)
==17918==    by 0x4E48474: lwpoly_force_clockwise (lwpoly.c:181)

comment:10 Changed 8 years ago by strk

r8193 fixes the memcpy source/destination overlap. I've also added a few tests for both ptarray_isccw (r8189) and lwgeom_force_clockwise (r8190).

I think one of them fails on a 32bit system, will take a closer look tomorrow.

comment:11 Changed 8 years ago by strk

Ok, hudson confirms I'm not crazy: http://office.refractions.net:1500/job/PostGIS-trunk-regression/1523/artifact/results_9.0.1_3.2.2_4.7.0/regress-TRUNK_8191_9.0.1_3.2.2_4.7.0.log

Now to figure if that polygon is really clockwise or counterclockwise. QGis thinks it is counterclockwise and requires reversing. That's what we're expecting. A 64bit machine confirms (qgis also running there, actually). Interesting enough, the _same_ ring passed to ptarray_isccw is considered counterclockwise also by the 32bit machine.

Dragons fight tomorrow.

comment:12 Changed 8 years ago by strk

Resolution: fixed
Status: newclosed

Alright, with r8202 we have the testcase under automated regression testing. It passes since r8198, with improvement of ptarray_isccw robustness.

comment:13 Changed 8 years ago by strk

#1383 contains another case with same symptoms as this one

Note: See TracTickets for help on using tickets.