Unable to tesselate shape error on indexing ES 7.11.1

mario.l · March 25, 2021, 1:59pm

Dear all,
I'm tring to save the following geometry

MULTIPOLYGON(((177.59 59.9735,180 62.288856810085,180 63.763900213475,178.731 64.0348,177.44 64.2967,176.148 64.5406,174.809 64.7792,173.45 65.005,172.047 65.2202,170.64 65.421,169.219 65.6075,167.797 65.7863,166.333 65.9439,164.861 66.0891,163.335 66.224,161.828 66.3404,160.292 66.4432,158.765 66.5298,157.216 66.6019,155.649 66.6591,154.109 66.6932,153.59 62.9316,154.943 62.8917,156.287 62.8324,157.653 62.7588,158.98 62.6742,160.302 62.5769,161.624 62.4665,162.95 62.3415,164.25 62.2062,165.537 62.0617,166.792 61.8975,168.06 61.7262,169.302 61.5448,170.554 61.3497,171.768 61.1458,172.97 60.9305,174.138 60.71,175.307 60.4739,176.454 60.2312,177.59 59.9735)),((-180 62.288856810085,-178.761 63.4792,-180 63.7639,-180 63.763900213475,-180 62.288856810085)))

into a geo_shape using ElasticSearch 7.11.1, but I have the following error:

{"error":{"root_cause":[{"type":"mapper_parsing_exception","reason":"failed to parse field [footprint] of type [geo_shape]"}],"type":"mapper_parsing_exception","reason":"failed to parse field [footprint] of type [geo_shape]","caused_by":{"type":"illegal_argument_exception","reason":"Unable to Tessellate shape [[62.288856810085, -180.0] [63.7639, -180.0] [63.763900213475, -180.0] [62.288856810085, -180.0] ]. Possible malformed shape detected."}},"status":400}

Here the Java StackTrace:

Caused by: org.elasticsearch.ElasticsearchException: Elasticsearch exception [type=illegal_argument_exception, reason=Unable to Tessellate shape [[62.288856810085, -180.0] [63.7639, -180.0] [63.763900213475, -180.0] [62.288856810085, -180.0] ]. Possible malformed shape detected.]
	at org.elasticsearch.ElasticsearchException.innerFromXContent(ElasticsearchException.java:485) ~[elasticsearch-7.11.1.jar:7.11.1]
	at org.elasticsearch.ElasticsearchException.fromXContent(ElasticsearchException.java:396) ~[elasticsearch-7.11.1.jar:7.11.1]
	at org.elasticsearch.ElasticsearchException.innerFromXContent(ElasticsearchException.java:426) ~[elasticsearch-7.11.1.jar:7.11.1]
	at org.elasticsearch.ElasticsearchException.failureFromXContent(ElasticsearchException.java:592) ~[elasticsearch-7.11.1.jar:7.11.1]
	at org.elasticsearch.rest.BytesRestResponse.errorFromXContent(BytesRestResponse.java:168) ~[elasticsearch-7.11.1.jar:7.11.1]
	... 32 more

Is it a bug? Is there a workaround?
I'm looking forward to reading your reply
Regards

Ignacio_Vera · March 26, 2021, 9:58am

I had a look and the problem is the orientation of the polygon. By default Elasticsearch expects polygons to have counter-clockwise orientation but your polygon contains clockwise orientation. this is making the logic fail as we are trying to build a polygon that crosses the dateline.

dadoonet · March 26, 2021, 10:14am

Should they use "orientation": "LEFT" in the mapping then? As per Geoshape field type | Elasticsearch Guide [8.11] | Elastic :

Optional. Vertex order for the shape’s coordinates list.

This parameter sets and returns only a RIGHT (counterclockwise) or LEFT (clockwise) value. However, you can specify either value in multiple ways.

To set RIGHT , use one of the following arguments or its uppercase variant:

right

counterclockwise

ccw

To set LEFT , use one of the following arguments or its uppercase variant:

left

clockwise

cw

Defaults to RIGHT to comply with OGC standards. OGC standards define outer ring vertices in counterclockwise order with inner ring (hole) vertices in clockwise order.

Individual GeoJSON or WKT documents can override this parameter.

Also this part of the documentation, gives some ideas but if I read it correctly it's not possible to define the orientation when using WKT, right?

IMPORTANT NOTE: WKT does not enforce a specific order for vertices thus ambiguous polygons around the dateline and poles are possible. GeoJSON mandates that the outer polygon must be counterclockwise and interior shapes must be clockwise, which agrees with the Open Geospatial Consortium (OGC) Simple Feature Access specification for vertex ordering.

Ignacio_Vera · March 26, 2021, 10:35am

The above says that in the case of GeoJson, a polygon should have CCW orientation in order to be valid and therefore should not be a problem in Elasticsearch.

WKT does not impose orientation, therefore the above WKT is totally valid but problematic for us as we need to assume an orientation in order to support polygons that crosses dateline.

My first recommendation is to use CCW polygons if possible, there have been discussions to deprecate the orientation parameter.

Alternatively, you can set the orientation parameter in there mapping.

mario.l · March 26, 2021, 11:13am

Dear all,
thank you for your replies.
Sorry, but I didn't catch: my MultiPolygon is composed by 2 polygons, both listing vertices in counter-clockwise order.

First polygon is

((177.59 59.9735,180 62.288856810085,180 63.763900213475,178.731 64.0348,177.44 64.2967,176.148 64.5406,174.809 64.7792,173.45 65.005,172.047 65.2202,170.64 65.421,169.219 65.6075,167.797 65.7863,166.333 65.9439,164.861 66.0891,163.335 66.224,161.828 66.3404,160.292 66.4432,158.765 66.5298,157.216 66.6019,155.649 66.6591,154.109 66.6932,153.59 62.9316,154.943 62.8917,156.287 62.8324,157.653 62.7588,158.98 62.6742,160.302 62.5769,161.624 62.4665,162.95 62.3415,164.25 62.2062,165.537 62.0617,166.792 61.8975,168.06 61.7262,169.302 61.5448,170.554 61.3497,171.768 61.1458,172.97 60.9305,174.138 60.71,175.307 60.4739,176.454 60.2312,177.59 59.9735))

and second polygon is

((-180 62.288856810085,-178.761 63.4792,-180 63.7639,-180 63.763900213475,-180 62.288856810085))

and both of them are listing points in counter-clockwise.

Moreover, to insert the geometry into ElasticSearch, I firstly convert the WKT to a GeoJson (I didn't write about it in my first post) because I didn't find a way of indexing the geometry from WKT directly.
By the way, even the converted GeoJson seems listing vetices in counter-clockwise order:

GeoJson: {"type":"MultiPolygon","coordinates":[[[[177.59,59.9735],[180.0,62.288856810085],[180.0,63.763900213475],[178.731,64.0348],[177.44,64.2967],[176.148,64.5406],[174.809,64.7792],[173.45,65.005],[172.047,65.2202],[170.64,65.421],[169.219,65.6075],[167.797,65.7863],[166.333,65.9439],[164.861,66.0891],[163.335,66.224],[161.828,66.3404],[160.292,66.4432],[158.765,66.5298],[157.216,66.6019],[155.649,66.6591],[154.109,66.6932],[153.59,62.9316],[154.943,62.8917],[156.287,62.8324],[157.653,62.7588],[158.98,62.6742],[160.302,62.5769],[161.624,62.4665],[162.95,62.3415],[164.25,62.2062],[165.537,62.0617],[166.792,61.8975],[168.06,61.7262],[169.302,61.5448],[170.554,61.3497],[171.768,61.1458],[172.97,60.9305],[174.138,60.71],[175.307,60.4739],[176.454,60.2312],[177.59,59.9735]]],[[[-180.0,62.288856810085],[-178.761,63.4792],[-180.0,63.7639],[-180.0,63.763900213475],[-180.0,62.288856810085]]]]}

So, sorry, I don't understand why you say that my geometry is not CCW compliant.
I'm looking forward to reading your reply.

Ignacio_Vera · March 26, 2021, 1:20pm

You are right @mario.l , the polygons are actually counter-clockwise. Interesting I got confuse but I was using a Lucene library to check the polygon and it uses orientation on the opposite way:

github.com

apache/lucene/blob/2d6ad2fee6dfd96388594f4de9b37c037efe8017/lucene/core/src/java/org/apache/lucene/geo/Polygon.java#L133


    maxLon = Math.max(polyLons[i], maxLon);
    // compute signed area
    windingSum +=
        (polyLons[j] - polyLons[numPts]) * (polyLats[i] - polyLats[numPts])
            - (polyLats[j] - polyLats[numPts]) * (polyLons[i] - polyLons[numPts]);
  }
  this.minLat = minLat;
  this.maxLat = maxLat;
  this.minLon = minLon;
  this.maxLon = maxLon;
  this.windingOrder = (windingSum < 0) ? GeoUtils.WindingOrder.CCW : GeoUtils.WindingOrder.CW;
}

/** returns the number of vertex points */
public int numPoints() {
  return polyLats.length;
}

/** Returns a copy of the internal latitude array */
public double[] getPolyLats() {
  return polyLats.clone();

I had a closer look into what is happening and it seems the issue comes with the small triangle. I open an issue as this is a bug. I had the feeling that the algorithm that decompose polygons might fail when a polygon has an edge along the negative dateline.

If you don't break the polygon, for example:

POLYGON((177.59 59.9735,180 62.288856810085,-178.761 63.4792, 180 63.763900213475,178.731 64.0348,177.44 64.2967,176.148 64.5406,174.809 64.7792,173.45 65.005,172.047 65.2202,170.64 65.421,169.219 65.6075,167.797 65.7863,166.333 65.9439,164.861 66.0891,163.335 66.224,161.828 66.3404,160.292 66.4432,158.765 66.5298,157.216 66.6019,155.649 66.6591,154.109 66.6932,153.59 62.9316,154.943 62.8917,156.287 62.8324,157.653 62.7588,158.98 62.6742,160.302 62.5769,161.624 62.4665,162.95 62.3415,164.25 62.2062,165.537 62.0617,166.792 61.8975,168.06 61.7262,169.302 61.5448,170.554 61.3497,171.768 61.1458,172.97 60.9305,174.138 60.71,175.307 60.4739,176.454 60.2312,177.59 59.9735))

Then the final indexed polygon is actually correct. Would that be a solution for you?

mario.l · March 26, 2021, 2:05pm

Dear Ignacio,
thank you for your reply.
Unfortunately, I got geometries from an external provider and I should store them as is.
I also tried to normalize the geometry using JTS library, but the exception persists.
Regards

Ignacio_Vera · March 26, 2021, 3:14pm

Actually the second polygon is invalid. If we have a closer look:

POLYGON((-180 62.288856810085,-178.761 63.4792,-180 63.7639,-180 63.763900213475,-180 62.288856810085))

The last three points are:

point1 = [-180, 63.7639]
point2 = [-180, 63.763900213475] -> goes just slightly north of point 1
point3 =[-180, 62.288856810085] -> goes south of point 1

Therefore the edge is running over it self and that is not allowed unfortunately. You will have to fix those things before sending the data to Elasticsearch.

mario.l · March 26, 2021, 4:18pm

Dear Ignacio
Yes, you are right: the geometry has a edge running over it self.
See picture where I exagerated the edge

However, I receive the geometry from an external provider and... how could I fix it? Should I remove edge from point 3 to 4? If so, output geometry will be different from the original one.

Is there any other workaround, taking into account that my original geometry is considered valid from other geographic tools, like JTS or PostGis?

system · April 23, 2021, 4:18pm

This topic was automatically closed 28 days after the last reply. New replies are no longer allowed.