Opened 14 years ago

Closed 20 months ago

#368 closed defect (fixed)

TopologyException on Union of valid geometries [JTS fails too]

Reported by: yabo Owned by: strk
Priority: major Milestone: Upstream
Component: Default Version: main
Severity: Unassigned Keywords: jtsbug
Cc:

Description

I have a topology exception when unioning two valid geomtries. Tested with geos 3.2.1 and geos svn (r2999). 

g1: 010600000003000000010300000001000000210000007711061EC4DE06C1B56E2A7A590F0F4124BB1E1EC4DE06C14E21D979590F0F410000000028E406C100000000900C0F410000000078EA06C10000000070090F410000000038ED06C10000000020080F4100000000C0F706C10000000050030F4100000000580C07C10000000048FB0E4100000000F03307C10000000010F10E4100000000306C07C10000000048EE0E410000000080AA07C10000000000FA0E4100000000B8FF07C100000000901E0F4100000000785208C10000000078510F4100000000E8A308C100000000308B0F4174C9FEC2BFF408C12FD8B0D3E7C50F4113C7FEC2BFF408C196D6B0D3E7C50F41E1D0D6FFE7A308C1FD4D3900308B0F41257C3830CC6A08C1FB85F738B6620F415C13F5C8046A08C10FAD4CF9CB620F419CFDB25F956908C12E4B3B1DA8620F4120CE9B206F6908C14C46985980620F41EE59F5B7566908C1C4681D0347620F41AB33315D526908C11519783FE5610F41A3915A77746908C1415A1B9CC2610F41BC295D36785208C1A5C6872678510F413F6E957FB8FF07C13FB57C4E901E0F41C8E5AACE80AA07C19F62AB5800FA0E410C8D11ED306C07C168B7952C48EE0E41CBC32D03F03307C12778E01410F10E41C4243C02580C07C16AC5ED0648FB0E411B9D2F36C0F706C1FA47DEEA4F030F412633850F38ED06C1EA5BE8F81F080F41CF5B10F027E406C137673D08900C0F417711061EC4DE06C1B56E2A7A590F0F4101030000000100000022000000E17D8C71E6DE06C103E99351E80E0F412296F1BD93F406C138D0C0BB72C70E41173108A4ED1907C1FD63D4AD91810E41FA7DADCA314C07C1FA7DADCA51440E41FC63D4AD718907C1183108A40D120E4137D0C0BB52CF07C12296F1BDB3EC0D41607F117D251B08C158E4C38DB3D50D41FFFFFFFFFF6908C140221E5BEFCD0D419F80EE82DAB808C158E4C38DB3D50D41C82F3F44AD0409C12196F1BDB3EC0D41039C2B528E4A09C1173108A40D120E4105825235CE8709C1F97DADCA51440E41E8CEF75B12BA09C1FC63D4AD91810E41DE690E426CDF09C136D0C0BB72C70E41A81B3C726CF609C15F7F117D45130F41C0DDE1A430FE09C1FFFFFFFF1F620F41A81B3C726CF609C19E80EE82FAB00F41DF690E426CDF09C1C72F3F44CDFC0F41B903BE563CC009C13FFD7C10931B104100000000989A09C100000000C014104100000000504609C10000000038FC0F4100000000F8F408C10000000098C50F410000000020A408C100000000E08A0F4100000000B05208C10000000028510F4100000000E0FF07C100000000401E0F410000000098AA07C100000000B0F90E4100000000386C07C100000000F0ED0E4100000000E03307C100000000C0F00E4100000000380C07C100000000F8FA0E410000000098F706C10000000000030F410000000010ED06C100000000D8070F410000000058EA06C10000000028090F410000000008E406C100000000400C0F41E17D8C71E6DE06C103E99351E80E0F41010300000001000000040000009A293C480BB709C1CBD46C641E1A104106202119719A09C1D00AEB32F014104102202119719A09C1CF0AEB32F01410419A293C480BB709C1CBD46C641E1A1041
g2: 01060000000100000001030000000100000021000000A887CB005F6908C10000000020620F412CD0BB18626908C1EEF84F9700620F410A9F1D426B6908C1E6B79F63E2610F410A3CCF227A6908C108190F8EC6610F4129F772288E6908C129F77228AE610F4108190F8EA66908C10A3CCF229A610F41E6B79F63C26908C10A9F1D428B610F41EEF84F97E06908C12CD0BB1882610F4100000000006A08C1A887CB007F610F411207B0681F6A08C12CD0BB1882610F411A48609C3D6A08C10A9F1D428B610F41F8E6F071596A08C10A3CCF229A610F41D7088DD7716A08C129F77228AE610F41F6C330DD856A08C108190F8EC6610F41F660E2BD946A08C1E6B79F63E2610F41D42F44E79D6A08C1EEF84F9700620F41587834FFA06A08C10000000020620F41D42F44E79D6A08C11207B0683F620F41F660E2BD946A08C11A48609C5D620F41F6C330DD856A08C1F8E6F07179620F41D7088DD7716A08C1D7088DD791620F41F8E6F071596A08C1F6C330DDA5620F411A48609C3D6A08C1F660E2BDB4620F411207B0681F6A08C1D42F44E7BD620F4100000000006A08C1587834FFC0620F41EEF84F97E06908C1D42F44E7BD620F41E6B79F63C26908C1F660E2BDB4620F4108190F8EA66908C1F6C330DDA5620F4129F772288E6908C1D7088DD791620F410A3CCF227A6908C1F8E6F07179620F410A9F1D426B6908C11A48609C5D620F412CD0BB18626908C11207B0683F620F41A887CB005F6908C10000000020620F41

Minimal test case attached.

Attachments (3)

test.cc​ (4.2 KB ) - added by yabo 14 years ago.
bug368.xml​ (3.8 KB ) - added by strk 13 years ago.
bug368jts.xml​ (4.2 KB ) - added by strk 13 years ago.

Download all attachments as: .zip

Change History (17)

by yabo, 14 years ago

Attachment: test.cc​ added

comment:1 by yabo, 14 years ago

Forget the error message : 

terminate called after throwing an instance of 'geos::util::TopologyException'
  what():  TopologyException: found non-noded intersection between LINESTRING (-2639 256559, -3375.26 257081) and LINESTRING (-3374.56 257080, -2639.03 256559) at -3228.11 256977
Aborted

comment:2 by giohappy, 14 years ago

We have had the same problems. str has opened similar tickets on this: #358 #360

by strk, 13 years ago

Attachment: bug368.xml​ added

comment:4 by strk, 13 years ago

Keywords: jtsbug added
Summary: TopologyException on Union of valid geometries. → TopologyException on Union of valid geometries [JTS fails too]

comment:5 by strk, 13 years ago

I took a look at the geometries. Wow, you can't even see the second geometry while looking at the first one.

A.area: 276,625,072 B.area: 1,264

The first geometry (A) is a multipoligon, composed by 3 poligons. Unioning geometry B with each of the polygons in geometry A succeeds.

comment:6 by strk, 13 years ago

But then again... unioning A1B with A2B re-throws the robustness issue.

comment:7 by strk, 13 years ago

The problem is with 3rd polygon in A, which is a long and narrow ring. ST_Area returns 0 for it.. The non-noded intersection seems to be between the two wings of that "ring", or a snapped version of them.

comment:8 by strk, 13 years ago

Milestone: → 3.3.0
Owner: changed from geos-devel@… to strk
Status: new → assigned

Evidently I was wrong, JTS doesn't fail here. I'm attaching an updated test with expected result in it.

by strk, 13 years ago

Attachment: bug368jts.xml​ added

comment:9 by strk, 13 years ago

Now I see that the JTS result is an invalid polygon (self-intersecting). This is with JTS rev 386 (1.12+)

comment:10 by strk, 13 years ago

Milestone: 3.3.0 → GEOS Future

We'll wait for this to be fixed on the JTS side first.

comment:11 by strk, 12 years ago

Martin: is this case also fixed with current JTS ?

comment:12 by robe, 6 years ago

Milestone: GEOS Future → GEOS Fund Me

Milestone renamed

comment:13 by pramsey, 3 years ago

Milestone: GEOS Fund Me → Upstream

comment:14 by dbaston, 20 months ago

Resolution: → fixed
Status: assigned → closed

This looks to have been addressed with OverlayNG; a test case was added in 4d3e571ed1b88697a3135c51ca14c73f4493f377/git

Note: See TracTickets for help on using tickets.