[geos-devel] MSVC Unit Failure

[Mike Taves]

This issue is getting stranger. I was wrong, it's old and not entirely
a Windows MSVC one either. It may have something to do with the order
of geometries passed to TaggedLineStringSimplifier.


Take re-ordered input:
MULTILINESTRING((0 0, 50 1, 60 1, 100 0), (0 0, 50 0, 70 0, 80 0, 100 0))

Should the expected topo-simplified output be re-ordered too? i.e.:
MULTILINESTRING ((0 0, 50 1, 100 0), (0 0, 100 0))

But it is always: MULTILINESTRING ((0 0, 100 0), (0 0, 100 0))
Is this unexpected? If so, then this fails.


I'm now able to get the "random" result behavior with Linux GCC with a
GEOS-3.7.3 build. Take the attached test_simplify.py script (based on
shapely) to run the tests, which call GEOSTopologyPreserveSimplify
1000 times on two input geometries, and count the number of times it
"equals" the expected geometry (which is order-agnostic), showing
True/False. E.g.

$ export LD_LIBRARY_PATH=/path/to/builds/geos-3.7.3/lib
$ python test_simplify.py
3.7.3-CAPI-1.11.3 f00e007
input: MULTILINESTRING((0 0, 50 0, 70 0, 80 0, 100 0), (0 0, 50 1, 60 1, 100 0))
Counter({False: 513, True: 487})
input: MULTILINESTRING((0 0, 50 1, 60 1, 100 0), (0 0, 50 0, 70 0, 80 0, 100 0))
Counter({False: 527, True: 473})

This shows a close 50%/50% pass/fail for either geometry input order.
Testing the same script with more recent GEOS versions:

$ export LD_LIBRARY_PATH=/path/to/builds/geos-3.8.1/lib
$ python test_simplify.py
3.8.1-CAPI-1.13.3
input: MULTILINESTRING((0 0, 50 0, 70 0, 80 0, 100 0), (0 0, 50 1, 60 1, 100 0))
Counter({True: 1000})
input: MULTILINESTRING((0 0, 50 1, 60 1, 100 0), (0 0, 50 0, 70 0, 80 0, 100 0))
Counter({False: 1000})

which has no randomness, with 100% pass for the first, and 100% fail
(if that's what we are calling it) for the second re-ordered geometry.
This is the same behaviour with GEOS-3.9.0beta1.


Enabling GEOS_DEBUG for TaggedLineStringSimplifier.cpp (in 3.9.0beta1
on MSVC) shows some details in a small C++ application.

Output using only input geometry with a good result:

input: MULTILINESTRING((0 0, 50 0, 70 0, 80 0, 100 0), (0 0, 50 1, 60 1, 100 0))
TaggedLineStringSimplifier[000002216BBD7920]
TaggedLineString[000002216BBDB950]  has 4 coords in input
TaggedLineStringSimplifier[000002216BBD7920]  simplifying section 0-3
geos::simplify::TaggedLineStringSimplifier::findFurthestPointsegment
LINESEGMENT(0 0,100 0)
dist to 50 1: 1
this is max
dist to 60 1: 1
furthest point 1 at distance 1
TaggedLineStringSimplifier[000002216BBD7920]  simplifying section 0-1
single segment, no flattening
TaggedLineStringSimplifier[000002216BBD7920]  simplifying section 1-3
geos::simplify::TaggedLineStringSimplifier::findFurthestPointsegment
LINESEGMENT(50 1,100 0)
dist to 60 1: 0.19996
this is max
furthest point 2 at distance 0.19996
isValidToSimplify, adding seg 50 1, 100 0 to
TaggedLineSegment[000002216BBDB950] result
TaggedLineStringSimplifier[000002216BBD7920]
TaggedLineString[000002216BBDB6C0]  has 5 coords in input
TaggedLineStringSimplifier[000002216BBD7920]  simplifying section 0-4
geos::simplify::TaggedLineStringSimplifier::findFurthestPointsegment
LINESEGMENT(0 0,100 0)
dist to 50 0: 0
this is max
dist to 70 0: 0
dist to 80 0: 0
furthest point 1 at distance 0
isValidToSimplify, adding seg 0 0, 100 0 to
TaggedLineSegment[000002216BBDB6C0] result
result: MULTILINESTRING ((0 0, 100 0), (0 0, 50 1, 100 0))

Output with a bad result:

input: MULTILINESTRING((0 0, 50 0, 70 0, 80 0, 100 0), (0 0, 50 1, 60 1, 100 0))
TaggedLineStringSimplifier[000001FA84EF6270]
TaggedLineString[000001FA84EE5B70]  has 5 coords in input
TaggedLineStringSimplifier[000001FA84EF6270]  simplifying section 0-4
geos::simplify::TaggedLineStringSimplifier::findFurthestPointsegment
LINESEGMENT(0 0,100 0)
dist to 50 0: 0
this is max
dist to 70 0: 0
dist to 80 0: 0
furthest point 1 at distance 0
isValidToSimplify, adding seg 0 0, 100 0 to
TaggedLineSegment[000001FA84EE5B70] result
TaggedLineStringSimplifier[000001FA84EF6270]
TaggedLineString[000001FA84EF9FC0]  has 4 coords in input
TaggedLineStringSimplifier[000001FA84EF6270]  simplifying section 0-3
geos::simplify::TaggedLineStringSimplifier::findFurthestPointsegment
LINESEGMENT(0 0,100 0)
dist to 50 1: 1
this is max
dist to 60 1: 1
furthest point 1 at distance 1
isValidToSimplify, adding seg 0 0, 100 0 to
TaggedLineSegment[000001FA84EF9FC0] result
result: MULTILINESTRING ((0 0, 100 0), (0 0, 100 0))

The main difference between the two outputs is the order of geometry
parts received by TaggedLineStringSimplifier.

I haven't looked at the underlying C++ containers, but it seems that
order is not guaranteed for MSVC, but it is for other compilers.

One fix would be to change this container to an ordered one. A better
fix would also return a 5-point geometry from the re-ordered geometry
input shown earlier.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: test_simplify.py
Type: text/x-python
Size: 576 bytes
Desc: not available
URL: <http://lists.osgeo.org/pipermail/geos-devel/attachments/20201203/0a7aa9a5/attachment-0001.py>