Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Hole is not within polygon #9511

Closed
bictorman opened this issue Jan 30, 2015 · 14 comments
Closed

Hole is not within polygon #9511

bictorman opened this issue Jan 30, 2015 · 14 comments
Assignees
Labels
:Analytics/Geo Indexing, search aggregations of geo points and shapes >bug good first issue low hanging fruit v1.4.5 v1.5.2 v1.6.0 v2.0.0-beta1

Comments

@bictorman
Copy link

Hi,

I've had some trouble importing some geo_shapes in 1.4+, I get the exception:
ElasticsearchParseException: Invaild shape: Hole is not within polygon

I got an example. Now, I'm not an expert in GIS, but:

  • The area looks like this: http://i.imgur.com/oDzSeDQ.png with one vertex of the hole in the same point as one vertex of the polygon.
  • The data is from postgis' ST_AsGeoJSON and according to ST_isValid it's a valid area.
  • Every version of ES from 0.90 to 1.3.x takes the area just fine. The problems happens after 1.4.0.

Here's the gist with all the data to reproduce it:
https://gist.github.com/bictorman/064a777499719ad66194

@clintongormley clintongormley added :Analytics/Geo Indexing, search aggregations of geo points and shapes discuss labels Feb 4, 2015
@colings86
Copy link
Contributor

@nknize I think this problem relates to the code to deal with polygons around the international date line. We rely on the fact that a hole is actually a hole (i.e. is within the polygon) to be able to place it properly. By definition a hole which intersects the polygons edges is not actually a hole but a modification to the external shape of the main polygon. Maybe we need to add some logic to rewrite the polygon to cut out the hole from the main polygon shape if it intersects with the edge?

@colings86 colings86 removed the discuss label Feb 6, 2015
@tschaub
Copy link

tschaub commented Mar 20, 2015

We've been hitting the same issues with polygons that are not close to the dateline and don't have interior rings that cross an exterior ring.

#!/bin/sh

curl -XDELETE http://localhost:9200/test_index

curl -XPUT http://localhost:9200/test_index/

curl -XPUT http://localhost:9200/test_index/test_type/_mapping -d '
 {
     "properties": {
         "geom": {
             "type": "geo_shape",
             "tree": "quadtree",
             "tree_levels": "26"
         }
     }
 }'

curl -XGET localhost:9200/test_index/test_type/_search?pretty -d \
    '{"query": {"filtered": {"filter": {"bool": {"must": [{"geo_shape": {"geom": {"shape": {"type": "polygon", "coordinates": [[[-150.0, -30.0], [-150.0, 30.0], [150.0, 30.0], [150.0, -30.0], [-150.0, -30.0]], [[0.01, 0.01], [0.02, 0.02], [0.01, 0.02], [0.01, 0.01]]]}}}}, "from": 0, "size": 50}'

Here's the polygon geometry from that query: http://bl.ocks.org/anonymous/raw/0fb706605fe9e53c52f8/

If the exterior ring is changed so that it spans from -90 (west) to 90 (east) longitude, the query succeeds. When the exterior ring spans more than 180 degrees, the query fails - even if the exterior ring is not near the dateline.

@tschaub
Copy link

tschaub commented Mar 20, 2015

Are you by chance assuming that rings spanning more than 180 degrees need to be "inverted"? In my opinion, you're best off pretending the world is flat and accepting that 0, 0 is inside a polygon spanning -91 (west) to 91 (east) - regardless of the winding order of exterior rings.

@tschaub
Copy link

tschaub commented Mar 20, 2015

I should debug to confirm, but it feels like you may be testing whether an interior ring is inside an exterior ring with different logic than the intersect query. Perhaps the query above fails because you decide that the interior ring (a small ring near 0, 0) is not inside the exterior ring. Maybe that is because you assume that because the exterior ring spans more than 180 degrees longitude you need to invert it.

But a similar query without the interior ring returns results that are inside the exterior ring in the same sense that the interior ring is inside (i.e. without assuming that the > 180 spanning exterior ring implies a ring that crosses the dateline).

@nknize
Copy link
Contributor

nknize commented Mar 21, 2015

Hey @bictorman and Tim, thanks for the update. I'll bump this up on the priority list to review before the next release. After looking at the provided examples it appears to be working as expected. We comply with OGC SFA spec (https://portal.opengeospatial.org/files/?artifact_id=829 see section 2.1.10 - specifically figure 2.5). "Figure 2.5 shows some examples of geometric objects that violate the above assertions and are not representable as single instances of Polygon." That is, holes should not intersect edges (these need to be converted to multi-polygon or multiple polygon objects).

Just to make sure there isn't some other latent bug, which version are you working with? Prior to 1.4.3 the ring orientation logic was incorrectly computed for polys > 180 (leading to behavior Tim described). That was corrected in 1.4.3+ to follow the OGC SFF right-hand rule along with an added orientation option to explicitly define orientation behavior. Per the right-hand rule, the polygon provided crosses the dateline, so the hole is outside the poly. A simple fix for this case should be to add

"orientation": "left"

And the ring vertices will be clockwise ordered.

@tschaub
Copy link

tschaub commented Mar 23, 2015

Thanks for the additional detail @nknize. I'll confirm the version we are using and try the orientation property. One concern is that GeoJSON doesn't specify the winding order and OGR (and more) don't enforce a winding order when serializing. Would it be possible to provide an option to disable the winding order check for polygons > 180? I like the behavior we're getting for polygons that don't span 180 and would find it convenient to force the same for all polygons (dateline be damned).

@tschaub
Copy link

tschaub commented Mar 23, 2015

We're running 1.4.4. I'll try to come up with some simple test cases to ensure we can get consistent behavior (for polygons with and without holes, regardless of span).

@nknize
Copy link
Contributor

nknize commented Mar 23, 2015

@tschaub We can certainly add an ignore option to the orientation and provide the "old" behavior if that's desired (the default would remain "right"). We ultimately chose OGC compliance (despite the GeoJSON indifference) as a solution to the ongoing issues surrounding dateline crossing polys. If you don't have any dateline crossing polys (or already have application logic to handle it) then an ignore option certainly makes sense. Would this option help you out?

In the meantime, 1.4.4 supports the orientation option which can be applied to the mapping and/or on a per document basis. This way you can have a shape field default to the left-hand rule but have specific documents processed using the right hand rule. In the above case you'd pass this particular document with the orientation: left parameter and all is well.

@nknize
Copy link
Contributor

nknize commented Mar 24, 2015

@bictorman There are 2 discussions here (latest surrounding winding order). I want to make sure we answered your original question/issue.

We comply with OGC SFA spec (https://portal.opengeospatial.org/files/?artifact_id=829 see section 2.1.10 - specifically figure 2.5). "Figure 2.5 shows some examples of geometric objects that violate the above assertions and are not representable as single instances of Polygon." That is, holes should not intersect edges. So you'll need to convert those geometric objects to multi-polygons or multiple polygon objects.

Let us know if there are any other questions. If not I'll close this as a non-issue. The second discussion (winding order) has been moved to #10227

@bictorman
Copy link
Author

@nknize Understood. Seems like I was misled by the behaviour of PostGIS and previous ES versions. We'll try to fix the data, thanks for the answer.

@nknize
Copy link
Contributor

nknize commented Mar 24, 2015

Closing as non-issue

@dbaston
Copy link

dbaston commented Mar 25, 2015

@nknize A lot of other software out there (PostGIS, GEOS, JTS, etc.) interprets the OGC spec to allow an interior ring to touch the outside of a boundary, provided that it only touches at one point. (If only OGC had included a drawing of this simple case in the spec!) Does ES have a different interpretation of the spec than PostGIS etc, and if so, how is one to represent a polygon like the one @bictorman posted in ES? I'm familiar with the ESRI/ArcGIS way of representing this -- as an exterior ring that loops back on itself -- but I've always understood that to be different from the OGC way.

Some more examples of OGC-valid polygons, including the case @bictorman posted, are found in the PostGIS docs:
http://postgis.net/docs/using_postgis_dbmanagement.html#OGC_Validity

@nknize
Copy link
Contributor

nknize commented Mar 25, 2015

@dbaston While I cannot comment on OGC compliance for other software packages your question did expose an issue with the ShapeBuilder incorrectly counting the closed coordinate of the interior ring as a violation of 2.1.10 assertion 3 (a conflict between the geojson parser and the OGC builder counting that point as 3 intersections). I'm going to reopen this issue to correct the closed coordinate issue.

Hopefully @bictorman was able to adjust his polygon accordingly. If not a working coordinate order can be found at the following GIST: https://gist.github.com/nknize/7a5d2bf9a9e654e1cbb5

As to the question of ES interpretation of the spec, its implemented to follow the spec as closely as possible per collaboration with the OGC and OSGeo community. Variations are often discovered by way of the mailing lists and issue discussions such as these (which keep the implementation in check). Thanks again for revisiting this. The feedback is greatly appreciated.

nknize added a commit to nknize/elasticsearch that referenced this issue Mar 31, 2015
OGC SFA 2.1.10 assertion 3 allows interior boundaries to touch exterior boundaries provided they intersect at a single point. Issue elastic#9511 provides an example where a valid shape is incorrectly interpreted as invalid (a false violation of assertion 3).  When the intersecting point appears as the first and last coordinate of the interior boundary in a polygon, the ShapeBuilder incorrectly counted this as multiple intersecting vertices. The fix required a little more than just a logic check. Passing the duplicate vertices resulted in a connected component in the edge graph causing an invalid self crossing polygon. This required additional logic to the edge assignment in order to correctly segment the connected components. Finally, an additional hole validation has been added along with proper unit tests for testing valid and invalid conditions (including dateline crossing polys).

closes elastic#9511
clement-tourriere pushed a commit to opendatasoft/elasticsearch that referenced this issue Apr 2, 2015
OGC SFA 2.1.10 assertion 3 allows interior boundaries to touch exterior boundaries provided they intersect at a single point. Issue elastic#9511 provides an example where a valid shape is incorrectly interpreted as invalid (a false violation of assertion 3).  When the intersecting point appears as the first and last coordinate of the interior boundary in a polygon, the ShapeBuilder incorrectly counted this as multiple intersecting vertices. The fix required a little more than just a logic check. Passing the duplicate vertices resulted in a connected component in the edge graph causing an invalid self crossing polygon. This required additional logic to the edge assignment in order to correctly segment the connected components. Finally, an additional hole validation has been added along with proper unit tests for testing valid and invalid conditions (including dateline crossing polys).

closes elastic#9511

Conflicts:
	src/test/java/org/elasticsearch/common/geo/ShapeBuilderTests.java
clement-tourriere pushed a commit to opendatasoft/elasticsearch that referenced this issue Apr 2, 2015
OGC SFA 2.1.10 assertion 3 allows interior boundaries to touch exterior boundaries provided they intersect at a single point. Issue elastic#9511 provides an example where a valid shape is incorrectly interpreted as invalid (a false violation of assertion 3).  When the intersecting point appears as the first and last coordinate of the interior boundary in a polygon, the ShapeBuilder incorrectly counted this as multiple intersecting vertices. The fix required a little more than just a logic check. Passing the duplicate vertices resulted in a connected component in the edge graph causing an invalid self crossing polygon. This required additional logic to the edge assignment in order to correctly segment the connected components. Finally, an additional hole validation has been added along with proper unit tests for testing valid and invalid conditions (including dateline crossing polys).

closes elastic#9511

Conflicts:
	src/test/java/org/elasticsearch/common/geo/ShapeBuilderTests.java
@nknize nknize closed this as completed in a8a35d7 Apr 10, 2015
nknize added a commit that referenced this issue Apr 10, 2015
OGC SFA 2.1.10 assertion 3 allows interior boundaries to touch exterior boundaries provided they intersect at a single point. Issue #9511 provides an example where a valid shape is incorrectly interpreted as invalid (a false violation of assertion 3).  When the intersecting point appears as the first and last coordinate of the interior boundary in a polygon, the ShapeBuilder incorrectly counted this as multiple intersecting vertices. The fix required a little more than just a logic check. Passing the duplicate vertices resulted in a connected component in the edge graph causing an invalid self crossing polygon. This required additional logic to the edge assignment in order to correctly segment the connected components. Finally, an additional hole validation has been added along with proper unit tests for testing valid and invalid conditions (including dateline crossing polys).

closes #9511
nknize added a commit that referenced this issue Apr 10, 2015
OGC SFA 2.1.10 assertion 3 allows interior boundaries to touch exterior boundaries provided they intersect at a single point. Issue #9511 provides an example where a valid shape is incorrectly interpreted as invalid (a false violation of assertion 3).  When the intersecting point appears as the first and last coordinate of the interior boundary in a polygon, the ShapeBuilder incorrectly counted this as multiple intersecting vertices. The fix required a little more than just a logic check. Passing the duplicate vertices resulted in a connected component in the edge graph causing an invalid self crossing polygon. This required additional logic to the edge assignment in order to correctly segment the connected components. Finally, an additional hole validation has been added along with proper unit tests for testing valid and invalid conditions (including dateline crossing polys).

closes #9511
nknize added a commit that referenced this issue Apr 10, 2015
OGC SFA 2.1.10 assertion 3 allows interior boundaries to touch exterior boundaries provided they intersect at a single point. Issue #9511 provides an example where a valid shape is incorrectly interpreted as invalid (a false violation of assertion 3).  When the intersecting point appears as the first and last coordinate of the interior boundary in a polygon, the ShapeBuilder incorrectly counted this as multiple intersecting vertices. The fix required a little more than just a logic check. Passing the duplicate vertices resulted in a connected component in the edge graph causing an invalid self crossing polygon. This required additional logic to the edge assignment in order to correctly segment the connected components. Finally, an additional hole validation has been added along with proper unit tests for testing valid and invalid conditions (including dateline crossing polys).

closes #9511
mute pushed a commit to mute/elasticsearch that referenced this issue Jul 29, 2015
OGC SFA 2.1.10 assertion 3 allows interior boundaries to touch exterior boundaries provided they intersect at a single point. Issue elastic#9511 provides an example where a valid shape is incorrectly interpreted as invalid (a false violation of assertion 3).  When the intersecting point appears as the first and last coordinate of the interior boundary in a polygon, the ShapeBuilder incorrectly counted this as multiple intersecting vertices. The fix required a little more than just a logic check. Passing the duplicate vertices resulted in a connected component in the edge graph causing an invalid self crossing polygon. This required additional logic to the edge assignment in order to correctly segment the connected components. Finally, an additional hole validation has been added along with proper unit tests for testing valid and invalid conditions (including dateline crossing polys).

closes elastic#9511
mute pushed a commit to mute/elasticsearch that referenced this issue Jul 29, 2015
OGC SFA 2.1.10 assertion 3 allows interior boundaries to touch exterior boundaries provided they intersect at a single point. Issue elastic#9511 provides an example where a valid shape is incorrectly interpreted as invalid (a false violation of assertion 3).  When the intersecting point appears as the first and last coordinate of the interior boundary in a polygon, the ShapeBuilder incorrectly counted this as multiple intersecting vertices. The fix required a little more than just a logic check. Passing the duplicate vertices resulted in a connected component in the edge graph causing an invalid self crossing polygon. This required additional logic to the edge assignment in order to correctly segment the connected components. Finally, an additional hole validation has been added along with proper unit tests for testing valid and invalid conditions (including dateline crossing polys).

closes elastic#9511
@muka
Copy link

muka commented Nov 6, 2015

+1

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
:Analytics/Geo Indexing, search aggregations of geo points and shapes >bug good first issue low hanging fruit v1.4.5 v1.5.2 v1.6.0 v2.0.0-beta1
Projects
None yet
Development

Successfully merging a pull request may close this issue.

8 participants