geo_polygon not handling polygons that cross the date line properly

[pablocastro]

Using Elasticsearch 1.1.1. I'm seeing geo_polygon behave oddly when the input polygon cross the date line. From a quick look at GeoPolygonFilter.GeoPolygonDocSet.pointInPolygon it doesn't seem that this is explicitly handled.

The reproduce this create an index/mapping as:

POST /geo

{ "mappings": { "docs": { "properties": { "p": { "type": "geo_point" } } } } }

Upload a document:

PUT /geo/docs/1

{ "p": { "lat": 40, "lon": 179 } }

Search with a polygon that's a box around the uploaded point and that crosses the date line:

POST /geo/docs/_search

{
  "filter": { "geo_polygon": { "p": { "points": [
      { "lat": 42, "lon": 178 },
      { "lat": 39, "lon": 178 },
      { "lat": 39, "lon": -179 },
      { "lat": 42, "lon": -179 },
      { "lat": 42, "lon": 178 }
  ] } } }
}

ES returns 0 results. If I use a polygon that stays to the west of the date line I do get results:

{
  "filter": { "geo_polygon": { "p": { "points": [
      { "lat": 42, "lon": 178 },
      { "lat": 39, "lon": 178 },
      { "lat": 39, "lon": 179.5 },
      { "lat": 42, "lon": 179.5 },
      { "lat": 42, "lon": 178 }
  ] } } }
}

Also, if I use a bounding box query with the same coordinates as the initial polygon, it does work:

{
  "filter": { "geo_bounding_box": { "p": 
    { "top_left": { "lat": 42, "lon": 178 },
       "bottom_right": { "lat": 39, "lon": -179 }
     }
  } }
}

It seems that this code needs to either split the check into east and west checks or normalize the input values. Am I missing something?

[colings86]

This is actually working as expected. Your first query will resolve as shown in the following GeoJSON gist which will not contain your document:
https://gist.github.com/anonymous/82b50b74a7b6d170bfc6

To create the desired results you specified you would need to split the polygon in to two polygons, one to the left of the date line and the other to the right. This can be done with the following query:

curl -XPOST 'localhost:9200/geo/_search?pretty' -d '{
    "query" : {
        "filtered" : {
            "query" : {
                "match_all" : {}
            },
            "filter" : {
                "or" : [
                    {
                        "geo_polygon" : {
                            "p" : {
                                "points" : [
                                     { "lat": 42, "lon": 178 },
                                     { "lat": 39, "lon": 178 },
                                     { "lat": 39, "lon": 180 },
                                     { "lat": 42, "lon": 180 },
                                     { "lat": 42, "lon": 178 }
                                ]
                            }
                        }
                    },
                    {
                        "geo_polygon" : {
                            "p" : {
                                "points" : [
                                     { "lat": 42, "lon": -180 },
                                     { "lat": 39, "lon": -180 },
                                     { "lat": 39, "lon": -179 },
                                     { "lat": 42, "lon": -179 },
                                     { "lat": 42, "lon": -180 }
                                ]
                            }
                        }
                    }
                ]
            }
        }
    }
}'

The bounding box is a little different since by specifying which coordinate is top_left and which is top_right you are fixing the box to overlap the date line.

[jtibshirani]

For me, I'd expect the line segment between two points to lie in the same direction as the great circle arc. Splitting an arbitrary query into sub-polygons isn't entirely straightforward, because it could intersect longitude 180 multiple times.

I have a rough draft of a commit that fixes this issue by shifting the polygon in GeoPolygonFilter (and all points passed in to pointInPolygon) so that it lies completely on one side of longitude 180. It is low-overhead and has basically no effect on the normal case. The only constraint is that the polygon can't span more than 360 degrees in longitude.

Does this sound reasonable, and is it worth submitting a PR?

[clintongormley]

@colings86 could this be solved with a left/right parameter or something similar?

[colings86]

@nknize is this fixed by #8521 ?

[nknize]

It does not. This is the infamous "ambiguous polygon" problem that occurs when treating a spherical coordinate system as a cartesian plane. I opened a discussion and feature branch to address this in #8672

tldr: GeoJSON doesn't specify order, but OGC does.

Feature fix: Default behavior = For GeoJSON poly's specified in OGC order (shell: ccw, holes: cw) ES Ring logic will correctly transform and split polys across the dateline (e.g., see https://gist.github.com/nknize/d122b243dc63dcba8474). For GeoJSON poly's provided in the opposite order original behavior will occur (e.g., @colings86 example https://gist.github.com/anonymous/82b50b74a7b6d170bfc6).

Additionally, I like @clintongormley suggestion of adding an optional left/right parameter. Its an easy fix letting user's clearly specify intent.

[nknize]

This is now addressed in PR #8762

[nknize]

Optional left/right parameter added in PR #8978