apache / apache/lucene

LatLonShapePolygonQuery returning incorrect WITHIN results with shared boundaries [LUCENE-8736]

Open
#9,782 25 comments 0 reactions 1 assignee Claimed by @nknize View on GitHub
legacy-jira-fix-version:8.1 legacy-jira-priority:Major type:bug
Dominant language
Java
Stars
3.6k
Forks
1.4k
Avg merge
2d 11h
Merged PRs (30d)
88

Description

Triangles that are `WITHIN` a target polygon query that also share a boundary with the polygon are incorrectly reported as `CROSSES` instead of `INSIDE`. This leads to incorrect `WITHIN` query results as demonstrated in the following test:

```java
public void testWithinFailure() throws Exception {
Directory dir = newDirectory();
RandomIndexWriter w = new RandomIndexWriter(random(), dir);

// test polygons:
Polygon indexPoly1 = new Polygon(new double[] {4d, 4d, 3d, 3d, 4d}, new double[] {3d, 4d, 4d, 3d, 3d});
Polygon indexPoly2 = new Polygon(new double[] {2d, 2d, 1d, 1d, 2d}, new double[] {6d, 7d, 7d, 6d, 6d});
Polygon indexPoly3 = new Polygon(new double[] {1d, 1d, 0d, 0d, 1d}, new double[] {3d, 4d, 4d, 3d, 3d});
Polygon indexPoly4 = new Polygon(new double[] {2d, 2d, 1d, 1d, 2d}, new double[] {0d, 1d, 1d, 0d, 0d});

// index polygons:
Document doc;
addPolygonsToDoc(FIELDNAME, doc = new Document(), indexPoly1);
w.addDocument(doc);
addPolygonsToDoc(FIELDNAME, doc = new Document(), indexPoly2);
w.addDocument(doc);
addPolygonsToDoc(FIELDNAME, doc = new Document(), indexPoly3);
w.addDocument(doc);
addPolygonsToDoc(FIELDNAME, doc = new Document(), indexPoly4);
w.addDocument(doc);

///// search //////
IndexReader reader = w.getReader();
w.close();
IndexSearcher searcher = newSearcher(reader);

Polygon[] searchPoly = new Polygon[] {new Polygon(new double[] {4d, 4d, 0d, 0d, 4d}, new double[] {0d, 7d, 7d, 0d, 0d})};

Query q = LatLonShape.newPolygonQuery(FIELDNAME, QueryRelation.WITHIN, searchPoly);
assertEquals(4, searcher.count(q));
IOUtils.close(w, reader, dir);
}
```

---
Migrated from [LUCENE-8736](https://issues.apache.org/jira/browse/LUCENE-8736) by Nick Knize (@nknize), updated Dec 08 2021
Attachments: [adaptive-decoding.patch](https://apache.github.io/lucene-jira-archive/attachments/LUCENE-8736/adaptive-decoding.patch), [LUCENE-8736.patch](https://apache.github.io/lucene-jira-archive/attachments/LUCENE-8736/LUCENE-8736.patch) (versions: 2)

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.