This project is read-only.

TopogyException, Side location conflict at [ DotSpatial.Topology.Coordinate ]

Jun 20, 2013 at 9:03 AM
Hi all,

I am trying to calculate a union based on two geometries like this (see WKT-Strings for the geometries below the post):
overallBuffer = overallBuffer.Union(newBuffer);
DotSpatial throws a DotSpatial.Topology.TopologyException:
Message=Side location conflict at [ DotSpatial.Topology.Coordinate ]
Source=DotSpatial.Topology
StackTrace:
   at DotSpatial.Topology.GeometriesGraph.EdgeEndStar.PropagateSideLabels(Int32 geomIndex)... (see full trace at the end of the post).
Does anybody have a hint for me? What is going wrong? Is it some sort of precision problem?
Any help appreciated,

Cheers,
Nothi

overallBuffer:
POLYGON ((-9168.1848717050200000 238936.2978505550000000, -9162.8862121115900000 238939.6822545150000000, -9160.4971075931100000 238941.2397150450000000, -9160.4971075931100000 238941.2397150450000000, -9160.3341515625100000 238941.3256854880000000, -9160.1581892280100000 238941.3803008860000000, -9159.9751937339800000 238941.4017072890000000, -9159.7913769695000000 238941.3891780430000000, -9159.6129787021600000 238941.3431384610000000, -9159.4460547654800000 238941.2651513830000000, -9159.2962714901400000 238941.1578641270000000, -9154.5952714901400000 238937.0858641270000000, -9154.5788645140800000 238937.0713347150000000, -9144.9688645140800000 238928.3713347150000000, -9144.9688645140800000 238928.3713347150000000, -9144.8371535263900000 238928.2261858270000000, -9144.7362846760400000 238928.0581338730000000, -9144.6701329391700000 238927.8736347350000000, -9144.6412395998500000 238927.6797761300000000, -9144.6507146241500000 238927.4840053250000000, -9144.6981940196700000 238927.2938430490000000, -9144.7818538187300000 238927.1165945740000000, -9144.8984801478100000 238926.9590690730000000, -9154.8784801478100000 238915.9290690730000000, -9154.8784801478100000 238915.9290690730000000, -9155.0217549345900000 238915.7986868020000000, -9155.1874801843000000 238915.6983755720000000, -9155.3694366921400000 238915.6318997840000000, -9155.5607961396500000 238915.6017540870000000, -9155.7543773423300000 238915.6090697650000000, -9155.9429157394600000 238915.6535722820000000, -9156.1193360126600000 238915.7335915820000000, -9156.2770176028600000 238915.8461247650000000, -9156.2770176028600000 238915.8461247650000000, -9160.9470176028600000 238919.9161247650000000, -9160.9470176028600000 238919.9161247650000000, -9161.0875971600000000 238920.0668095070000000, -9161.1943039594400000 238920.2431108470000000, -9161.2287978431500000 238920.3413017300000000, -9165.1074108442200000 238923.8602046540000000, -9165.1203714896300000 238923.8518887270000000, -9165.2923286156700000 238923.7822708240000000, -9165.4741862129300000 238923.7456140370000000, -9165.6596854875200000 238923.7431799440000000, -9165.8424423138800000 238923.7750523160000000, -9166.0161669503200000 238923.8401342370000000, -9166.1748805061300000 238923.9361858530000000, -9177.2548805061300000 238932.1361858530000000, -9177.2595744964500000 238932.1396810490000000, -9183.2795744964600000 238936.6496810490000000, -9183.2795744964500000 238936.6496810490000000, -9183.4258819106300000 238936.7839217950000000, -9183.5427818584600000 238936.9444236310000000, -9183.6256653914700000 238937.1248585430000000, -9183.6712647072400000 238937.3181126230000000, -9183.6777819872100000 238937.5165665530000000, -9183.6449602782600000 238937.7123960010000000, -9183.5740936234300000 238937.8978801100000000, -9183.4679760424400000 238938.0657059010000000, -9183.3307913734500000 238938.2092566020000000, -9179.0607913734500000 238941.8692566020000000, -9179.0228337015800000 238941.9002119050000000, -9178.0338337015800000 238942.6672119050000000, -9178.0338337015800000 238942.6672119050000000, -9177.8779120870600000 238942.7665118580000000, -9177.7063768587500000 238942.8354153840000000, -9177.5250897237100000 238942.8715679110000000, -9177.3402456314600000 238942.8737340330000000, -9177.1581610799500000 238942.8418397290000000, -9176.9850582680400000 238942.7769748920000000, -9176.8268524703000000 238942.6813560860000000, -9176.8268524703000000 238942.6813560860000000, -9168.1848717050200000 238936.2978505550000000))

newBuffer:
POLYGON ((-9165.1074108442200000 238923.8602046540000000, -9165.1203714896300000 238923.8518887270000000, -9165.2923286156700000 238923.7822708240000000, -9165.4741862129300000 238923.7456140370000000, -9165.6596854875200000 238923.7431799440000000, -9165.8424423138800000 238923.7750523160000000, -9166.0161669503200000 238923.8401342370000000, -9166.1748805061300000 238923.9361858530000000, -9177.2548805061300000 238932.1361858530000000, -9177.2595744964500000 238932.1396810490000000, -9183.2795744964600000 238936.6496810490000000, -9183.2795744964500000 238936.6496810490000000, -9183.4258819106300000 238936.7839217950000000, -9183.5427818584600000 238936.9444236310000000, -9183.6256653914700000 238937.1248585430000000, -9183.6712647072400000 238937.3181126230000000, -9183.6777819872100000 238937.5165665530000000, -9183.6449602782600000 238937.7123960010000000, -9183.5740936234300000 238937.8978801100000000, -9183.4679760424400000 238938.0657059010000000, -9183.3307913734500000 238938.2092566020000000, -9179.0607913734500000 238941.8692566020000000, -9179.0228337015800000 238941.9002119050000000, -9178.0338337015800000 238942.6672119050000000, -9178.0335328004300000 238942.6674451710000000, -9170.4095683976400000 238948.5754175860000000, -9166.9686039535600000 238951.2423900280000000, -9166.9686039535600000 238951.2423900280000000, -9166.7916914752700000 238951.3520960720000000, -9166.5958989861300000 238951.4227978560000000, -9166.3897108484200000 238951.4514316280000000, -9166.1820619036400000 238951.4367565890000000, -9165.9819502951100000 238951.3794086580000000, -9165.7980475474100000 238951.2818729180000000, -9165.6383227994300000 238951.1483759300000000, -9165.5096974741100000 238950.9847025760000000, -9161.9391190522400000 238945.3121384240000000, -9159.1888530594100000 238941.0648184240000000, -9154.5952714901400000 238937.0858641270000000, -9154.5788645140800000 238937.0713347150000000, -9144.9688645140800000 238928.3713347150000000, -9144.9688645140800000 238928.3713347150000000, -9144.8371535263900000 238928.2261858270000000, -9144.7362846760400000 238928.0581338730000000, -9144.6701329391700000 238927.8736347350000000, -9144.6412395998500000 238927.6797761300000000, -9144.6507146241500000 238927.4840053250000000, -9144.6981940196700000 238927.2938430490000000, -9144.7818538187300000 238927.1165945740000000, -9144.8984801478100000 238926.9590690730000000, -9154.8784801478100000 238915.9290690730000000, -9154.8784801478100000 238915.9290690730000000, -9155.0217549345900000 238915.7986868020000000, -9155.1874801843000000 238915.6983755720000000, -9155.3694366921400000 238915.6318997840000000, -9155.5607961396500000 238915.6017540870000000, -9155.7543773423300000 238915.6090697650000000, -9155.9429157394600000 238915.6535722820000000, -9156.1193360126600000 238915.7335915820000000, -9156.2770176028600000 238915.8461247650000000, -9156.2770176028600000 238915.8461247650000000, -9160.9470176028600000 238919.9161247650000000, -9160.9470176028600000 238919.9161247650000000, -9161.0875971600000000 238920.0668095070000000, -9161.1943039594400000 238920.2431108470000000, -9161.2287978431500000 238920.3413017300000000, -9165.1074108442200000 238923.8602046540000000))

Exception details:
DotSpatial.Topology.TopologyException was caught
Message=Side location conflict at [ DotSpatial.Topology.Coordinate ]
Source=DotSpatial.Topology
StackTrace:
   at DotSpatial.Topology.GeometriesGraph.EdgeEndStar.PropagateSideLabels(Int32 geomIndex)
   at DotSpatial.Topology.GeometriesGraph.EdgeEndStar.ComputeLabelling(GeometryGraph[] geom)
   at DotSpatial.Topology.GeometriesGraph.DirectedEdgeStar.ComputeLabelling(GeometryGraph[] geom)
   at DotSpatial.Topology.Operation.Overlay.OverlayOp.ComputeLabelling()
   at DotSpatial.Topology.Operation.Overlay.OverlayOp.ComputeOverlay(SpatialFunction opCode)
   at DotSpatial.Topology.Operation.Overlay.OverlayOp.GetResultGeometry(SpatialFunction funcCode)
   at DotSpatial.Topology.Operation.Overlay.OverlayOp.Overlay(IGeometry geom0, IGeometry geom1, SpatialFunction opCode)
   at DotSpatial.Topology.Geometry.Union(IGeometry other)
   at rmdata.Math.Geometry.DotSpatialGeometryAdapter.CreateBuffer(IMathGeometry mathGeometry, Double bufferDistance)
   at rmdata.Math.Geometry.MathGeometryExtensions.Buffer(IMathGeometry geom, Double distance)
   at rmdata.Commands.Gis.Analysis.CreateBuffer.BufferObjects(IEnumerable`1 bobjCol, SelectionResultDouble offset) in D:\source\ng\extensions\latest\gis\source\rmdata.Commands.Gis\Analysis\CreateBuffer.cs:line 226
   at rmdata.Commands.Gis.Analysis.CreateBuffer.Start(Object[] arguments) in D:\source\ng\extensions\latest\gis\source\rmdata.Commands.Gis\Analysis\CreateBuffer.cs:line 58
   at rmdata.Application.Core.Command.Management.InvokeInternal(CommandInfo info, Func`2 cmdDelegate, ICustomLoopFinish customFinish)
InnerException:
Jun 20, 2013 at 10:55 AM
Each of the polygons has duplicate points. If you remove those, your union should work.
Jun 20, 2013 at 2:24 PM
Hello,

thank you for your hint.
I re-checked the Polygons using DotSpatial:
hasDuplicateCoords = DotSpatial.Topology.CoordinateArrays.HasRepeatedPoints(overallBuffer.ExteriorRing.Coordinates);
hasDuplicateCoords = DotSpatial.Topology.CoordinateArrays.HasRepeatedPoints(newBuffer.ExteriorRing.Coordinates);
Both predicates are "false". Looking at the coordinate list I can see that the first and last coordinates are duplicates. I thought , that was OK for the exterior of a closed polygon?
I also tried to remove any duplicates by using:
DotSpatial.Topology.CoordinateArrays.RemoveRepeatedPoints
Still the TopologyException is thrown.

Any other ideas?

Thanks a lot,
Nothi
Jun 20, 2013 at 3:29 PM
From the data you posted, there are at least 7 duplicate points

POLYGON ((
-9168.1848717050200000 238936.2978505550000000,
-9162.8862121115900000 238939.6822545150000000,
-9160.4971075931100000 238941.2397150450000000,
-9160.4971075931100000 238941.2397150450000000,
-9160.3341515625100000 238941.3256854880000000,
-9160.1581892280100000 238941.3803008860000000,
-9159.9751937339800000 238941.4017072890000000,
-9159.7913769695000000 238941.3891780430000000,
-9159.6129787021600000 238941.3431384610000000,
-9159.4460547654800000 238941.2651513830000000,
-9159.2962714901400000 238941.157864127000000,
-9154.5952714901400000 238937.0858641270000000,
-9154.5788645140800000 238937.0713347150000000,
-9144.9688645140800000 238928.3713347150000000,
-9144.9688645140800000 238928.3713347150000000,
-9144.8371535263900000 238928.2261858270000000,
-9144.7362846760400000 238928.0581338730000000,
-9144.6701329391700000 238927.8736347350000000,
-9144.6412395998500000 238927.6797761300000000,
-9144.6507146241500000 238927.4840053250000000,
-9144.6981940196700000 238927.2938430490000000,
-9144.7818538187300000 238927.1165945740000000,
-9144.8984801478100000 238926.9590690730000000,
-9154.8784801478100000 238915.9290690730000000,
-9154.8784801478100000 238915.9290690730000000,
-9155.0217549345900000 238915.7986868020000000,
-9155.1874801843000000 238915.6983755720000000,
-9155.3694366921400000 238915.6318997840000000,
-9155.5607961396500000 238915.6017540870000000,
-9155.7543773423300000 238915.6090697650000000,
-9155.9429157394600000 238915.6535722820000000,
-9156.1193360126600000 238915.7335915820000000,
-9156.2770176028600000 238915.8461247650000000,
-9156.2770176028600000 238915.8461247650000000,
-9160.9470176028600000 238919.9161247650000000,
-9160.9470176028600000 238919.9161247650000000,
-9161.0875971600000000 238920.0668095070000000,
-9161.1943039594400000 238920.2431108470000000,
-9161.2287978431500000 238920.3413017300000000,
-9165.1074108442200000 238923.8602046540000000,
-9165.1203714896300000 238923.8518887270000000,
-9165.2923286156700000 238923.7822708240000000,
-9165.4741862129300000 238923.7456140370000000,
-9165.6596854875200000 238923.7431799440000000,
-9165.8424423138800000 238923.7750523160000000,
-9166.0161669503200000 238923.8401342370000000,
-9166.1748805061300000 238923.9361858530000000,
-9177.2548805061300000 238932.1361858530000000,
-9177.2595744964500000 238932.1396810490000000,
-9183.2795744964600000 238936.6496810490000000,
-9183.2795744964500000 238936.6496810490000000,
-9183.4258819106300000 238936.7839217950000000,
-9183.5427818584600000 238936.9444236310000000,
-9183.6256653914700000 238937.1248585430000000,
-9183.6712647072400000 238937.3181126230000000,
-9183.6777819872100000 238937.5165665530000000,
-9183.6449602782600000 238937.7123960010000000,
-9183.5740936234300000 238937.8978801100000000,
-9183.4679760424400000 238938.0657059010000000,
-9183.3307913734500000 238938.2092566020000000,
-9179.0607913734500000 238941.8692566020000000,
-9179.0228337015800000 238941.9002119050000000,
-9178.0338337015800000 238942.6672119050000000,
-9178.0338337015800000 238942.6672119050000000,
-9177.8779120870600000 238942.7665118580000000,
-9177.7063768587500000 238942.8354153840000000,
-9177.5250897237100000 238942.8715679110000000,
-9177.3402456314600000 238942.8737340330000000,
-9177.1581610799500000 238942.8418397290000000,
-9176.9850582680400000 238942.7769748920000000,
-9176.8268524703000000 238942.6813560860000000,
-9176.8268524703000000 238942.6813560860000000,
-9168.1848717050200000 238936.2978505550000000))

If DotSpatial.Topology does not mark them as topologically equal, than the issue is that they are so close to each other that the topology computiation fails.
Remove the marked points by iterating over them and computing the distance between each. If the distance is less than a threshold value, ignore the point.
Hth FObermaier
Jun 21, 2013 at 11:44 AM
Hello,

Indeed there are duplicate Points in my geometries, at least looking at the WKT-output. So I examined the coordinates in code and found out, that they differ very slightly on double precision. I guess, that's why DotSpatial will not remove them using RemoveRepeatedPoints.
Anyway, I solved the problem by filtering out duplicates based on your suggestion (threshhold 1 mm is ok for my use case) and now the buffer is created fine.

Thanks again for your valuable Input!

Cheers,
Nothi