Opened 12 years ago

Closed 12 years ago

Last modified 12 years ago

#2025 closed defect (fixed)

side location conflict at topogeo_AddLineString() of separate edges

Reported by: wimned Owned by: strk
Priority: medium Milestone: PostGIS 2.1.0
Component: topology Version: master
Keywords: history Cc:


Version I use: POSTGIS="2.1.0SVN r10195" GEOS="3.3.4-CAPI-1.7.3" PROJ="Rel. 4.7.1, 23 September 2009" LIBXML="2.7.8" TOPOLOGY

Currently I build up topologies in separate districts, each in their own schema. When I enter the resulting edges into a main topology I get this error.

The message:

ERROR:  GEOSContains: TopologyException: side location conflict at 2 4
CONTEXT:  SQL statement "UPDATE wimpy.edge_data SET left_face = CASE WHEN left_face = 3 THEN 4 ELSE left_face END, right_face = CASE WHEN right_face = 3 THEN 4 ELSE right_face END WHERE ( left_face = 3 OR right_face = 3) AND NOT edge_id = ANY ('{6,3,5,2,5}') AND NOT ST_Contains('0103000020E6100000010000000D0000000000000000000040000000000000104000000000000000400000000000000840000000000000F03F0000000000000840000000000000F03F0000000000001040000000000000F03F00000000000014400000000000000040000000000000144000000000000000400000000000001040000000000000184000000000000000400000000000001C4000000000000000400000000000001C40000000000000F03F0000000000001840000000000000F03F0000000000001840000000000000004000000000000000400000000000001040'::geometry, geom)"
PL/pgSQL function "_st_addfacesplit" line 114 at EXECUTE statement
SQL statement "SELECT topology._ST_AddFaceSplit(atopology, newedge.edge_id, newedge.left_face, false)"
PL/pgSQL function "st_addedgemodface" line 510 at SQL statement
PL/pgSQL function "topogeo_addlinestring" line 124 at assignment
SQL statement "SELECT topogeo_AddLineString('wimpy', line5)"

The code:

 returns void as
    declare line1 geometry;
    declare line2 geometry;
    declare line3 geometry;
    declare line4 geometry;
    declare line5 geometry;
    declare line6 geometry;
    declare simpl_tol float;
    raise notice 'version: %', postgis_full_version();

    perform CreateTopology('wimpy', 4326, 0.0000001);

    simpl_tol = 0.00001;
    line1 = ST_GeometryFromText(
        'LINESTRING(0 0, 0 6,8 6,8 0,0 0)', 4326);

    line2 = ST_GeometryFromText(
        'LINESTRING(6 2,7 2,7 1,6 1,6 2)', 4326);

    line3 = ST_GeometryFromText(
        'LINESTRING(1 4,1 5,2 5,2 4)', 4326);

    line4 = ST_GeometryFromText(
        'LINESTRING(2 4,1 4)', 4326);

    line5 = ST_GeometryFromText(
        'LINESTRING(2 4,2 3,1 3,1 4)', 4326);

    line6 = ST_GeometryFromText(
        'LINESTRING(6 2,2 4)', 4326);

    perform topogeo_AddLineString('wimpy', line1);
    perform topogeo_AddLineString('wimpy', line2);
    perform topogeo_AddLineString('wimpy', line3);
    perform topogeo_AddLineString('wimpy', line4);
    perform topogeo_AddLineString('wimpy', line6);
    perform topogeo_AddLineString('wimpy', line5);
LANGUAGE plpgsql;

When I insert line 5 before line 6 I don't get the error. Also validatetopology() doesn't report errors then. I understand that line 6 breaks proper polygon topology here, but it is part of a face being built up.

When I have to AddLineString the complete polygon rings, I'll loose the performance gain I have by building up in separate districts

Attachments (2)

topo_err.jpg (8.8 KB ) - added by wimned 12 years ago.
The edges built up with line 5 before line 6
before_five.png (7.3 KB ) - added by strk 12 years ago.

Download all attachments as: .zip

Change History (13)

by wimned, 12 years ago

Attachment: topo_err.jpg added

The edges built up with line 5 before line 6

comment:1 by strk, 12 years ago

Putting image inline for discussion.

The edges built up with line 5 before line 6

So you're basically getting a side-location conflict when adding line 5 after line 6, right ? Could you attach another image showing the topology with all lines but 6 inserted ? Also add output of TopologySummary to make sure we see all the nodes and the edges. And ideally insert a scale too, so that we can see how big 0.0000001 is (your tolerance).

by strk, 12 years ago

Attachment: before_five.png added

comment:2 by strk, 12 years ago

I'm attaching it. This is the topology still valid before attempt to add edge 5. The smallest distance you can see is the square side, which is 1.0. I can reproduce the problem even with NO tolerance.

comment:3 by strk, 12 years ago

Status: newassigned

The "AND NOT ST_Contains" query is from topology._ST_AddFaceSplit. I'm pretty sure the function could be improved to avoid full containment check, given we know there's no edge crossing.

You're the best tester wimned, thanks a lot !

comment:4 by strk, 12 years ago

So the problem is that what we compute as being the face created by the newly added edge is an invalid polygon. We compute the face as bound by the ring obtained by walking around the newly added edge. Such face becomes thus composed by both tiny squares (faces 1 and 2 in before_five.png) plus the new square (the one bound by the new edge + edge 4).

The line being added is oriented to have start point in node:4 and end point in node:3, The face being split is face:3. The newly created face should be on its left side (so basically face 3 should become the new small square and the outer face should become the _new_ face).

comment:5 by wimned, 12 years ago

As I understand, the problem won't occur when AddLineString is fed with complete rings. I just want to add them in pieces, because I know already were they are going to be split in the near future. It would be nice to add them as a collection, so the testing on the newly made face can be done after the eventual splitting of edges of other districts is done.

It is not happening very often. In my setup I can make a list of faces in the districts that are to be inserted into the main topology as complete rings. I'll post some statistics later here.

comment:6 by strk, 12 years ago

The problem must not occur. But the testing for new faces is currently built-in the standard ST_AddEdgeModFace / ST_AddEdgeNewFaces, the first of which is used by TopoGeo_addLinestring.

Checking later might indeed be faster, but currently there's no function to "build" a topology from edges already inserted. Well, there was an attempt (topology.polygonize) but I think it doesn't set the proper edge linking and isn't even necessarely faster.

Anyway please keep performance considerations away from this ticket. I'm happy to discuss about that but this ticket is for a confirmed bug.

comment:7 by wimned, 12 years ago

So indeed it legal to insert linestrings not being complete rings.

After having merged 64 districts, I have 2938 edges and 2566 faces. The problem did not yet occur, because now I'm inserting the faces with the largest amount of edges first. (my program now crashes for another reason….)

comment:8 by strk, 12 years ago

Yes, it is legal to add non-closed linestrings as edges. Make sure to check your topology for being valid as while testing this case I found another case that produces an invalid topology rather than throwing an exception.

comment:9 by strk, 12 years ago

So both bugs are fixed with r10364 in 2.0 branch and r10365 in trunk

comment:10 by strk, 12 years ago

Keywords: history added
Resolution: fixed
Status: assignedclosed

comment:11 by wimned, 12 years ago

great! Thanks, Wim

Note: See TracTickets for help on using tickets.