side location conflict at topogeo_AddLineString() of separate edges

[wimned]

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:

CREATE OR REPLACE FUNCTION testerror1()
 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;
begin
    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);
END
$$
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

[wimned]

The edges built up with line 5 before line 6

[strk]

Putting image inline for discussion.

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).

[strk]

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.

[strk]

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 !

[strk]

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).

[wimned]

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.

[strk]

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.

[wimned]

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….)

[strk]

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.

[strk]

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

[wimned]

great! Thanks, Wim