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

Geo: Valid complex polygons fail to parse #5773

Closed
marcuswr opened this Issue Apr 11, 2014 · 14 comments

Comments

Projects
None yet
4 participants
@marcuswr
Copy link

marcuswr commented Apr 11, 2014

posting certain valid geojson polygons results in the following exception:

org.elasticsearch.index.mapper.MapperParsingException: failed to parse [geometry] at org.elasticsearch.index.mapper.geo.GeoShapeFieldMapper.parse(GeoShapeFieldMapper.java:249)
...

curl -XDELETE 'http://localhost:9200/test'

curl -XPOST 'http://localhost:9200/test' -d '{
"mappings":{
"test":{
"properties":{
"geometry":{
"type":"geo_shape",
"tree":"quadtree",
"tree_levels":14,
"distance_error_pct":0.0
}
}
}
}
}'

curl -XPOST 'http://localhost:9200/test/test/1' -d '{
"geometry":{
"type":"Polygon",
"coordinates":[
[[-85.0018514,37.1311314],
[-85.0016645,37.1315293],
[-85.0016246,37.1317069],
[-85.0016526,37.1318183],
[-85.0017119,37.1319196],
[-85.0019371,37.1321182],
[-85.0019972,37.1322115],
[-85.0019942,37.1323234],
[-85.0019543,37.1324336],
[-85.001906,37.1324985],
[-85.001834,37.1325497],
[-85.0016965,37.1325907],
[-85.0016011,37.1325873],
[-85.0014816,37.1325353],
[-85.0011755,37.1323509],
[-85.000955,37.1322802],
[-85.0006241,37.1322529],
[-85.0000002,37.1322307],
[-84.9994,37.1323001],
[-84.999109,37.1322864],
[-84.998934,37.1322415],
[-84.9988639,37.1321888],
[-84.9987841,37.1320944],
[-84.9987208,37.131954],
[-84.998736,37.1316611],
[-84.9988091,37.131334],
[-84.9989283,37.1311337],
[-84.9991943,37.1309198],
[-84.9993573,37.1308459],
[-84.9995888,37.1307924],
[-84.9998746,37.130806],
[-85.0000002,37.1308358],
[-85.0004984,37.1310658],
[-85.0008008,37.1311625],
[-85.0009461,37.1311684],
[-85.0011373,37.1311515],
[-85.0016455,37.1310491],
[-85.0018514,37.1311314]],
[[-85.0000002,37.1317672],
[-85.0001983,37.1317538],
[-85.0003378,37.1317582],
[-85.0004697,37.131792],
[-85.0008048,37.1319439],
[-85.0009342,37.1319838],
[-85.0010184,37.1319463],
[-85.0010618,37.13184],
[-85.0010057,37.1315102],
[-85.000977,37.1314403],
[-85.0009182,37.1313793],
[-85.0005366,37.1312209],
[-85.000224,37.1311466],
[-85.000087,37.1311356],
[-85.0000002,37.1311433],
[-84.9995021,37.1312336],
[-84.9993308,37.1312859],
[-84.9992567,37.1313252],
[-84.9991868,37.1314277],
[-84.9991593,37.1315381],
[-84.9991841,37.1316527],
[-84.9992329,37.1317117],
[-84.9993527,37.1317788],
[-84.9994931,37.1318061],
[-84.9996815,37.1317979],
[-85.0000002,37.1317672]]]
}
}'

Expected:
{"ok":true,"_index":"test","_type":"test","_id":"1","_version":1}
Actual:
{"error":"MapperParsingException[failed to parse [geometry]]; nested: ArrayIndexOutOfBoundsException[-1]; ","status":400}

This is an issue with es-1.1.0. The same requests execute successfully against es-0.2.4.

It is possible to view and validate the data in qgis.

screen shot 2014-04-10 at 5 01 56 pm

@marcuswr

This comment has been minimized.

Copy link
Author

marcuswr commented Apr 11, 2014

Checked additional versions of elastic search:
elasticsearch-0.20.4 PASSED
elasticsearch-0.90.13 PASSED
elasticsearch-1.0.0.RC1 FAILED
elasticsearch-1.0.2 FAILED
elasticsearch-1.1.0 FAILED

@marcuswr

This comment has been minimized.

Copy link
Author

marcuswr commented Apr 11, 2014

Here is a small test case which triggers the issue in v1.1.0

import org.elasticsearch.common.geo.builders.ShapeBuilder;
import org.elasticsearch.common.xcontent.XContentParser;
import org.elasticsearch.common.xcontent.json.JsonXContent;

public class Test {
public static void main(String[] args) throws Exception {

    String geoJson = "{ \"type\": \"Polygon\",\"coordinates\": [[[-85.0018514,37.1311314],[-85.0016645,37.1315293],[-85.0016246,37.1317069],[-85.0016526,37.1318183],[-85.0017119,37.1319196],[-85.0019371,37.1321182],[-85.0019972,37.1322115],[-85.0019942,37.1323234],[-85.0019543,37.1324336],[-85.001906,37.1324985],[-85.001834,37.1325497],[-85.0016965,37.1325907],[-85.0016011,37.1325873],[-85.0014816,37.1325353],[-85.0011755,37.1323509],[-85.000955,37.1322802],[-85.0006241,37.1322529],[-85.0000002,37.1322307],[-84.9994,37.1323001],[-84.999109,37.1322864],[-84.998934,37.1322415],[-84.9988639,37.1321888],[-84.9987841,37.1320944],[-84.9987208,37.131954],[-84.998736,37.1316611],[-84.9988091,37.131334],[-84.9989283,37.1311337],[-84.9991943,37.1309198],[-84.9993573,37.1308459],[-84.9995888,37.1307924],[-84.9998746,37.130806],[-85.0000002,37.1308358],[-85.0004984,37.1310658],[-85.0008008,37.1311625],[-85.0009461,37.1311684],[-85.0011373,37.1311515],[-85.0016455,37.1310491],[-85.0018514,37.1311314]],[[-85.0000002,37.1317672],[-85.0001983,37.1317538],[-85.0003378,37.1317582],[-85.0004697,37.131792],[-85.0008048,37.1319439],[-85.0009342,37.1319838],[-85.0010184,37.1319463],[-85.0010618,37.13184],[-85.0010057,37.1315102],[-85.000977,37.1314403],[-85.0009182,37.1313793],[-85.0005366,37.1312209],[-85.000224,37.1311466],[-85.000087,37.1311356],[-85.0000002,37.1311433],[-84.9995021,37.1312336],[-84.9993308,37.1312859],[-84.9992567,37.1313252],[-84.9991868,37.1314277],[-84.9991593,37.1315381],[-84.9991841,37.1316527],[-84.9992329,37.1317117],[-84.9993527,37.1317788],[-84.9994931,37.1318061],[-84.9996815,37.1317979],[-85.0000002,37.1317672]]]}";

    XContentParser parser = JsonXContent.jsonXContent.createParser(geoJson);                                                                                                                                    
   parser.nextToken();
    ShapeBuilder.parse(parser).build();
}

}

// stack trace
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1
at org.elasticsearch.common.geo.builders.BasePolygonBuilder.assign(BasePolygonBuilder.java:366)
at org.elasticsearch.common.geo.builders.BasePolygonBuilder.compose(BasePolygonBuilder.java:347)
at org.elasticsearch.common.geo.builders.BasePolygonBuilder.coordinates(BasePolygonBuilder.java:146)
at org.elasticsearch.common.geo.builders.BasePolygonBuilder.buildGeometry(BasePolygonBuilder.java:175)
at org.elasticsearch.common.geo.builders.BasePolygonBuilder.build(BasePolygonBuilder.java:151)

@marcuswr marcuswr changed the title Regression: failed to parse [geometry], java.lang.ArrayIndexOutOfBoundsException -1 Valid polygons fail to parse in versions 1.0.0-RC1+ Apr 14, 2014

@spinscale

This comment has been minimized.

Copy link
Member

spinscale commented Apr 14, 2014

Hey.

you can also use the github geo json feature as well to visualize this, see https://gist.github.com/spinscale/9cc6ba24bff03cca2be5

there has been a huge geo refactoring going on between those affected versions, will check for a regression there.

Do you have any other data where this happens with, or is it just this single polygon?

Thanks a lot for all your input!

@spinscale spinscale self-assigned this Apr 14, 2014

@spinscale

This comment has been minimized.

Copy link
Member

spinscale commented Apr 14, 2014

I updated my geojson gist above and added a test with a simple polygon (rectangle with hole, which is a rectangle as well), which works... need to investigate

spinscale added a commit to spinscale/elasticsearch that referenced this issue Apr 14, 2014

Geo: Find out min/max values for correct intersection handling
A multi polygon with holes didnt correctly calculate possible intersections
because it used the first edge instead of the edge with the min/max value of
the longitude (depending if positive/negative)

Closes elastic#5773
@marcuswr

This comment has been minimized.

Copy link
Author

marcuswr commented Apr 14, 2014

I have several thousand polygons that result in this error. I have not
pulled them all out of the logs yet, I will hopefully have time to do that
today.

On Mon, Apr 14, 2014 at 1:08 AM, Alexander Reelsen <notifications@github.com

wrote:

Hey.

you can also use the github geo json feature as well to visualize this,
see https://gist.github.com/spinscale/9cc6ba24bff03cca2be5

there has been a huge geo refactoring going on between those affected
versions, will check for a regression there.

Do you have any other data where this happens with, or is it just this
single polygon?

Thanks a lot for all your input!


Reply to this email directly or view it on GitHubhttps://github.com//issues/5773#issuecomment-40342030
.

@spinscale

This comment has been minimized.

Copy link
Member

spinscale commented Apr 14, 2014

I'd highly appreciate it, if you could test with the PR referenced above... it solves this problem, but maybe you could check if I introduced side effects (one just came to mind, which i need to check)...

@marcuswr

This comment has been minimized.

Copy link
Author

marcuswr commented Apr 14, 2014

I have put up a file containing 15k+ polygons which had the same
ArrayIndexOutOfBoundsException against ES1.0+. It is available at
https://github.com/marcuswr/elasticsearch-polygon-data.git

Additionally, the gist at https://gist.github.com/marcuswr/493406918e0a9edeb509 contains a set of polygons which still fail against the patched version (same IndexOutOfBoundsException)

On Mon, Apr 14, 2014 at 7:50 AM, Alexander Reelsen <notifications@github.com

wrote:

I'd highly appreciate it, if you could test with the PR referenced
above... it solves this problem, but maybe you could check if I introduced
side effects (one just came to mind, which i need to check)...


Reply to this email directly or view it on GitHubhttps://github.com//issues/5773#issuecomment-40374176
.

@marcuswr

This comment has been minimized.

Copy link
Author

marcuswr commented Apr 14, 2014

I have added another file to the repository, with the subset of polygons,
which still failed to ingest, after the patch was applied.
https://github.com/marcuswr/elasticsearch-polygon-data/blob/master/patch_errors.geojson

On Mon, Apr 14, 2014 at 1:03 PM, Marcus Richardson
mrichardson@climate.comwrote:

I have put up a file containing 15k+ polygons which had the same
ArrayIndexOutOfBoundsException against ES1.0+. It is available at
https://github.com/marcuswr/elasticsearch-polygon-data.git

Additionally, I have pulled down your fix locally (your branch of master,
and I used your patch against es 1.1). I am able to insert some polygons
but
not all (I have not tried all of them). I also cloned your gist to:
https://gist.github.com/marcuswr/493406918e0a9edeb509 The third
(test.geojson) renders correctly in the gist, however, does not work for me
against either patched version. The 4th file (test1.geojson) does work in
both versions.

On Mon, Apr 14, 2014 at 7:50 AM, Alexander Reelsen <
notifications@github.com> wrote:

I'd highly appreciate it, if you could test with the PR referenced
above... it solves this problem, but maybe you could check if I introduced
side effects (one just came to mind, which i need to check)...


Reply to this email directly or view it on GitHubhttps://github.com//issues/5773#issuecomment-40374176
.

@spinscale

This comment has been minimized.

Copy link
Member

spinscale commented Apr 20, 2014

thanks a lot for all the data, I will test with the other polygons as soon as possible (travelling a bit the next days, but will try to check ASAP).

@marcuswr

This comment has been minimized.

Copy link
Author

marcuswr commented Apr 29, 2014

@spinscale wondering if you had a chance to look at this? We are looking to do a major elastic search upgrade, but will not be able to without a fix. Please let me know if there is anything I can do to assist.

@spinscale

This comment has been minimized.

Copy link
Member

spinscale commented Apr 30, 2014

sorry, did not yet have the time to check out all the other polygons you supplied due to traveling

@marcuswr

This comment has been minimized.

Copy link
Author

marcuswr commented May 8, 2014

These polygons fail to ingest when the point in the hole (the first point in the LineString, or the leftmost point in the patched version #5796) has the same x coordinate (starting or ending) as 2 or more line segments of the shell.
I have created another gist (https://gist.github.com/marcuswr/e0490b4f6e25b344e779) with simplified polygons which demonstrate this problem (hole_aligned.geojson, hole_aligned_simple.geojson). These will fail on the patched version. Changing the order of the coordinates in the hole so the leftmost coordinate is first and last (repeated), should result in it failing in both patched and non-patched). There are additional polygons shown which touch or cross the dateline (the dateline hole should be removed from these polygons -> convert to multi-polygon).
These failures only occur when fixdateline = true.

Additionally, could you tell me why there is special handling of the ear in ShapeBuilder.intersections?
if (Double.compare(p1.x, dateline) == Double.compare(edges[i].next.next.coordinate.x, dateline)) {
// Ignore the ear

Also Double.compare is not guaranteed to return -1, 0, 1 I'm not sure what the equality is testing for.

@spinscale

This comment has been minimized.

Copy link
Member

spinscale commented May 9, 2014

thanks a lot for testing and debugging, your comments make a lot of sense, I will close the PR

marcuswr added a commit to marcuswr/elasticsearch that referenced this issue May 13, 2014

Only use dateline fix when polygon crosses dateline.
- es1.x attempts to split polygons on the dateline along
  with holes, and then re-assign the holes to the new
  polygons.  In certain circumstances this assignment
  fails (elastic#5773)
  The geojson format makes it clear which hole belongs to which
  polygon, and these issues can be avoided for polygons which
  do not span the dateline.
- there are additional issues with splitting polygons on the
  dateline.  Some shapes are lost in certain circumstances (bug
  yet to be filed).
  Sample shape: https://gist.github.com/anonymous/7f1bb6d7e9cd72f5977c
@olimcc

This comment has been minimized.

Copy link

olimcc commented May 20, 2014

Hey @spinscale sorry to bug, but do you think you could glance at this PR and at least indicate if ES would move forward with it? If so, we (I work with Marcus) can proceed locally as the finer details of the PR are worked out.

marcuswr added a commit to TheClimateCorporation/elasticsearch that referenced this issue May 20, 2014

Only use dateline fix when polygon crosses dateline.
- es1.x attempts to split polygons on the dateline along
  with holes, and then re-assign the holes to the new
  polygons.  In certain circumstances this assignment
  fails (elastic#5773)
  The geojson format makes it clear which hole belongs to which
  polygon, and these issues can be avoided for polygons which
  do not span the dateline.
- there are additional issues with splitting polygons on the
  dateline.  Some shapes are lost in certain circumstances (bug
  yet to be filed).
  Sample shape: https://gist.github.com/anonymous/7f1bb6d7e9cd72f5977c

@spinscale spinscale removed their assignment Jul 18, 2014

@spinscale spinscale added the adoptme label Jul 18, 2014

@colings86 colings86 removed the adoptme label Jul 23, 2014

@colings86 colings86 self-assigned this Jul 23, 2014

@colings86 colings86 added bug labels Jul 23, 2014

@colings86 colings86 added the v2.0.0 label Jul 23, 2014

colings86 added a commit to colings86/elasticsearch that referenced this issue Jul 24, 2014

Geo: Fixes parse error with complex shapes
The bug reproduces when the point under test for the placement of the hole of the polygon has an x coordinate which only intersects with the ends of edges in the main polygon. The previous code threw out these cases as not relevant but an intersect at 1.0 of the distance from the start to the end of an edge is just as valid as an intersect at any other point along the edge.  The fix corrects this and adds a test.

Closes elastic#5773

colings86 added a commit that referenced this issue Jul 24, 2014

Geo: Fixes parse error with complex shapes
The bug reproduces when the point under test for the placement of the hole of the polygon has an x coordinate which only intersects with the ends of edges in the main polygon. The previous code threw out these cases as not relevant but an intersect at 1.0 of the distance from the start to the end of an edge is just as valid as an intersect at any other point along the edge.  The fix corrects this and adds a test.

Closes #5773

@colings86 colings86 changed the title Valid polygons fail to parse in versions 1.0.0-RC1+ Geo: Valid complex polygons fail to parse Jul 29, 2014

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.