Some "valid" polygons are treated as invalid by rgeo

[daesan]

Some polygons that are valid with MySQL or QGIS are causing error in rgeo.

Steps to reproduce

The following code results in exception.

RGeo::Geographic.spherical_factory.parse_wkt("POLYGON ((126.968027438107 37.5816708669373, 126.96804356077827 37.58168793850955, 126.96804348189114 37.5816870915542, 126.96804311029837 37.58168238826706, 126.96803990177084 37.581642824769546, 126.968027438107 37.5816708669373))")

Expected behavior

It should be parsed without problem.

Actual behavior

It throws the following exception.

RGeo::Error::InvalidGeometry (LinearRing failed ring test)

System configuration

Ruby version: 2.5.0p0

OS: Mac OS X 10.14.6

[keithdoggett]

I just spent a few days dealing with a similar issue so hopefully, this will be helpful to you or anyone else encountering this in the future.

LinearRing Test

For polygons, the linear ring test checks 2 methods is_closed? and is_simple?. is_closed? ensures that the polygon's first and last point are the same. is_simple? checks that lines or arcs in your polygon don't cross over each other to "split" the polygon. Here are a few examples:

Simple hourglass looking polygon

The southern border of the US State Oklahoma (notice how the polygon pinches off a section in the top left)

Geographic vs. Geometric

This all has to do with projections and geometries vs. geographies. You're using a geographic factory in this situation, so the program is mapping your coordinates to a spherical surface, but you likely got the points from a projection (mapping of the earth to a flat surface). So when you map them back to a spherical surface it's failing the is_simple? requirement. If we take a look at your polygon we see that a few points are very close to each other, likely causing the issue.

Notice the points in the top right

Geometric projections are used to simplify computation and view the map on a flat surface. Projections have the advantage of being treated as cartesian features, but still have lat/lng's associated with them. I successfully parsed this polygon using RGeo::Geographic.simple_mercator_factory which uses a Mercator projection (SRID: 3875).

Solutions

There are 2 solutions that have worked for me: reduce point density/clusters in geographic polygons or use a projection.

If the data you're dealing with is local and you won't need to do precise calculations over long distances then a projection should be fine. You can even find projections specified for certain regions that will give you the highest accuracy there if your app will only be used for one area. If your app is big already, it can be tedious to switch over but can help avoid issues like this in the future.

TLDR

Lines in a polygon can't cross over. If you're using spherical_factory, they probably are if you have a high point density. Either switch to a geometric projection or use fewer points.

[daesan]

@Kdoggett887 Thank you for the detailed explanation. But I think there are more issues to this problem.

While the points are dense in the given triangle, lines do not cross over one another. Indeed, MySQL 8.0(with spherical coordinates support) does validate this polygon.

select st_isvalid(st_geomfromtext("POLYGON ((37.5816708669373 126.968027438107, 37.58168793850955 126.96804356077827, 37.5816870915542 126.96804348189114, 37.58168238826706 126.96804311029837, 37.581642824769546 126.96803990177084, 37.5816708669373 126.968027438107))", 4326))

=> 1

I am not sure about the root cause of this bug. Since this issue is happening with densely located points, maybe some sort of rounding off error is being introduced in RGeo's algorithm?

[keithdoggett]

@daesan That's a good point. Thanks for bringing that up.

I did some more research and got your polygon to be valid by changing the RGeo::Geographic::SphericalMath::PointXYZ class.

It maps the lat/lngs to a cartesian sphere but casts the (x,y,z) points to floats. Turns out around 1e-12 or so the precision breaks down. I changed the types to BigDecimal which has better precision and it worked fine.

I would be happy to submit a PR to get this fix merged in if it makes sense.

[daesan]

@Kdoggett887 That's really cool! Thank so much for digging into this. It would be great if you can submit a PR to fix this issue. 👍

[ykessler]

I've been banging my head over the same issue! https://stackoverflow.com/questions/58996305/getting-invalidgeometry-linearring-failed-ring-test-after-upgrading-rgeo-gem

[keithdoggett]

The new validation system in version 3 allows for creating geometries that are invalid, so issues like this where reading from the database failed due to a validation error will no longer happen.

This doesn't solve the second issue that the spherical math library is not robust to floating point errors at high precision, but I'm going to close this since there's an issue open for improvements to the spherical math library (#274)