Opened 12 years ago

Closed 5 years ago

Last modified 5 years ago

#588 closed defect (fixed)

[JTS fixed] valid polygon when cw, not valid when ccw

Reported by: olivier80 Owned by: geos-devel@…
Priority: major Milestone: 3.8.0
Component: Default Version: 3.3.5
Severity: Unassigned Keywords: jtsfail
Cc:

Description

Geos says this polygon is valid :

POLYGON ((
-86.3958130146539250 114.3482370100377900, 
64.7285128575111490 156.9678884302379600, 
138.3490775437400700 43.1639042523018260, 
87.9271046586986810 -10.5302909001479570, 
87.9271046586986810 -10.5302909001479530, 
55.7321237336437390 -44.8146215164960250, 
-86.3958130146539250 114.3482370100377900))

Now, I reverse the points :

POLYGON ((
-86.3958130146539250 114.3482370100377900, 
55.7321237336437390 -44.8146215164960250, 
87.9271046586986810 -10.5302909001479530, 
87.9271046586986810 -10.5302909001479570, 
138.3490775437400700 43.1639042523018260, 
64.7285128575111490 156.9678884302379600, 
-86.3958130146539250 114.3482370100377900))

Geos notices me "Self-intersection at or near point 87.927104658698681 -10.530290900147953".

Change History (15)

comment:1 by strk, 12 years ago

Ouch! Confirmed, also using st_reverse. I'm with 3.4.0dev here, are you on 3.3.5 ?

comment:2 by olivier80, 12 years ago

Yes.

comment:3 by strk, 12 years ago

The polygon ring has 7 points, but it's a 4 sides polygon. So 2 vertices are very close to other vertices.

I'd love to have a function (in postgis) to analyze these cases and answer questions like: what's the minimum distance between two consecutive vertices ? what's the minimum distance between any two vertices ?

Simplifying the geometry with a tolerance of 1e-10 is enough to fix the invalidity, but anyway the robustness problem exists. I didn't try with JTS but I suspect it may be an issue there as well.

comment:4 by olivier80, 12 years ago

Unfortunately, I'm not a postgis user, I use geos with the C api. This polygon is a simplified version of a GEOSBufferWithStyle() result. I keep only the problematic points (87.9271046586986810 -10.5302909001479570 and 87.9271046586986810 -10.5302909001479530). The distance between those two points is nothing and yes, you're right, simplifying should fix.

comment:5 by strk, 12 years ago

Keywords: jtsfail added
Summary: valid polygon when cw, not valid when ccw[JTS fails] valid polygon when cw, not valid when ccw

comment:6 by strk, 12 years ago

Martin Davis wrote:

Turns out that this isn't an issue in the trunk version of JTS (but it is in JST 1.12). This is probably due to the recent switch to using extended precision to compute determinant signs - which affects all intersection computations. It would be good if GEOS switched to using this new more (fully?) robust technique as well.

See ticket #591 for that

comment:7 by strk, 11 years ago

Milestone: 3.3.63.3.7

comment:8 by strk, 11 years ago

Milestone: 3.3.73.3.x
Summary: [JTS fails] valid polygon when cw, not valid when ccw[JTS fixed] valid polygon when cw, not valid when ccw

comment:9 by robe, 11 years ago

Milestone: 3.3.93.5.0

this sounds complicated and trying to do something in a micro that affects all intersection matrix calculations sounds a bit scary to me. Push

comment:10 by robe, 9 years ago

Milestone: 3.5.03.6.0

still a problem: (tested on 3.5.0dev r4057)

SELECT ST_Isvalid('POLYGON ((
-86.3958130146539250 114.3482370100377900, 
55.7321237336437390 -44.8146215164960250, 
87.9271046586986810 -10.5302909001479530, 
87.9271046586986810 -10.5302909001479570, 
138.3490775437400700 43.1639042523018260, 
64.7285128575111490 156.9678884302379600, 
-86.3958130146539250 114.3482370100377900))'::geometry);

NOTICE:  Self-intersection at or near point 87.927104658698681 -10.530290900147953

comment:11 by strk, 7 years ago

Milestone: 3.6.03.7.0

Ticket retargeted after milestone closed

comment:12 by robe, 7 years ago

Milestone: 3.7.03.8.0

comment:13 by dbaston, 5 years ago

Resolution: fixed
Status: newclosed

Apparently fixed with robust determinant fixes in 3.8.x. Added regression test in 4c8e68a1cf16637be0ef3826c18fc3df628039c8/git

comment:14 by mdavis, 5 years ago

Thanks, DB.

It might be nice to add a comment to the test with this issue number, so we can understand history?

comment:15 by dbaston, 5 years ago

Yes, thanks for catching that. Added in c2bbf31c03ec7a87256caff00917c44b69c4d806/git

Note: See TracTickets for help on using tickets.