You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by iv...@apache.org on 2021/01/04 08:48:55 UTC
[lucene-solr] branch branch_8x updated: LUCENE-9642: Rotate
triangle points before checking triangle orientation (#2154)
This is an automated email from the ASF dual-hosted git repository.
ivera pushed a commit to branch branch_8x
in repository https://gitbox.apache.org/repos/asf/lucene-solr.git
The following commit(s) were added to refs/heads/branch_8x by this push:
new fd2294f LUCENE-9642: Rotate triangle points before checking triangle orientation (#2154)
fd2294f is described below
commit fd2294f585db65c6bb093ebde6a51ddd6cb986a5
Author: Ignacio Vera <iv...@apache.org>
AuthorDate: Mon Jan 4 09:42:44 2021 +0100
LUCENE-9642: Rotate triangle points before checking triangle orientation (#2154)
When encoding triangles in ShapeField, make sure generated triangles are CCW by rotating triangle points before checking triangle orientation.
---
lucene/CHANGES.txt | 3 +
.../org/apache/lucene/document/ShapeField.java | 81 +++++++++-------------
.../lucene/document/BaseShapeEncodingTestCase.java | 2 +-
.../lucene/document/TestXYShapeEncoding.java | 10 +++
4 files changed, 45 insertions(+), 51 deletions(-)
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index 373af94..563d8e2 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -66,6 +66,9 @@ Bug Fixes
* LUCENE-9617: Fix per-field memory leak in IndexWriter.deleteAll(). Reset next available internal
field number to 0 on FieldInfos.clear(), to avoid wasting FieldInfo references. (Michael Froh)
+* LUCENE-9642: When encoding triangles in ShapeField, make sure generated triangles are CCW by rotating
+ triangle points before checking triangle orientation. (Ignacio Vera)
+
Other
---------------------
diff --git a/lucene/core/src/java/org/apache/lucene/document/ShapeField.java b/lucene/core/src/java/org/apache/lucene/document/ShapeField.java
index 516fdb5c..f3e89d6 100644
--- a/lucene/core/src/java/org/apache/lucene/document/ShapeField.java
+++ b/lucene/core/src/java/org/apache/lucene/document/ShapeField.java
@@ -66,8 +66,8 @@ public final class ShapeField {
Triangle(String name, Tessellator.Triangle t) {
super(name, TYPE);
setTriangleValue(t.getEncodedX(0), t.getEncodedY(0), t.isEdgefromPolygon(0),
- t.getEncodedX(1), t.getEncodedY(1), t.isEdgefromPolygon(1),
- t.getEncodedX(2), t.getEncodedY(2), t.isEdgefromPolygon(2));
+ t.getEncodedX(1), t.getEncodedY(1), t.isEdgefromPolygon(1),
+ t.getEncodedX(2), t.getEncodedY(2), t.isEdgefromPolygon(2));
}
/** sets the vertices of the triangle as integer encoded values */
@@ -110,43 +110,14 @@ public final class ShapeField {
* Triangles are encoded with CCW orientation and might be rotated to limit the number of possible reconstructions to 2^3.
* Reconstruction always happens from west to east.
*/
- public static void encodeTriangle(byte[] bytes, int aLat, int aLon, boolean abFromShape, int bLat, int bLon, boolean bcFromShape, int cLat, int cLon, boolean caFromShape) {
+ public static void encodeTriangle(byte[] bytes, int aY, int aX, boolean ab, int bY, int bX, boolean bc, int cY, int cX, boolean ca) {
assert bytes.length == 7 * BYTES;
- int aX;
- int bX;
- int cX;
- int aY;
- int bY;
- int cY;
- boolean ab, bc, ca;
- //change orientation if CW
- if (GeoUtils.orient(aLon, aLat, bLon, bLat, cLon, cLat) == -1) {
- aX = cLon;
- bX = bLon;
- cX = aLon;
- aY = cLat;
- bY = bLat;
- cY = aLat;
- ab = bcFromShape;
- bc = abFromShape;
- ca = caFromShape;
- } else {
- aX = aLon;
- bX = bLon;
- cX = cLon;
- aY = aLat;
- bY = bLat;
- cY = cLat;
- ab = abFromShape;
- bc = bcFromShape;
- ca = caFromShape;
- }
- //rotate edges and place minX at the beginning
+ // rotate edges and place minX at the beginning
if (bX < aX || cX < aX) {
+ final int tempX = aX;
+ final int tempY = aY;
+ final boolean tempBool = ab;
if (bX < cX) {
- int tempX = aX;
- int tempY = aY;
- boolean tempBool = ab;
aX = bX;
aY = bY;
ab = bc;
@@ -156,10 +127,7 @@ public final class ShapeField {
cX = tempX;
cY = tempY;
ca = tempBool;
- } else if (cX < aX) {
- int tempX = aX;
- int tempY = aY;
- boolean tempBool = ab;
+ } else {
aX = cX;
aY = cY;
ab = ca;
@@ -171,13 +139,13 @@ public final class ShapeField {
bc = tempBool;
}
} else if (aX == bX && aX == cX) {
- //degenerated case, all points with same longitude
- //we need to prevent that aX is in the middle (not part of the MBS)
+ // degenerated case, all points with same longitude
+ // we need to prevent that aX is in the middle (not part of the MBS)
if (bY < aY || cY < aY) {
+ final int tempX = aX;
+ final int tempY = aY;
+ final boolean tempBool = ab;
if (bY < cY) {
- int tempX = aX;
- int tempY = aY;
- boolean tempBool = ab;
aX = bX;
aY = bY;
ab = bc;
@@ -187,10 +155,7 @@ public final class ShapeField {
cX = tempX;
cY = tempY;
ca = tempBool;
- } else if (cY < aY) {
- int tempX = aX;
- int tempY = aY;
- boolean tempBool = ab;
+ } else {
aX = cX;
aY = cY;
ab = ca;
@@ -204,6 +169,22 @@ public final class ShapeField {
}
}
+ // change orientation if CW
+ if (GeoUtils.orient(aX, aY, bX, bY, cX, cY) == -1) {
+ // swap b with c
+ final int tempX = bX;
+ final int tempY = bY;
+ final boolean tempBool = ab;
+ // aX and aY do not change, ab becomes bc
+ ab = bc;
+ bX = cX;
+ bY = cY;
+ // bc does not change, ca becomes ab
+ cX = tempX;
+ cY = tempY;
+ ca = tempBool;
+ }
+
int minX = aX;
int minY = StrictMath.min(aY, StrictMath.min(bY, cY));
int maxX = StrictMath.max(aX, StrictMath.max(bX, cX));
@@ -298,7 +279,7 @@ public final class ShapeField {
aY = NumericUtils.sortableBytesToInt(t, 2 * BYTES);
aX = NumericUtils.sortableBytesToInt(t, 1 * BYTES);
bY = NumericUtils.sortableBytesToInt(t, 0 * BYTES);
- bX = NumericUtils.sortableBytesToInt(t, 3 * BYTES);
+ bX = NumericUtils.sortableBytesToInt(t, 3 * BYTES);
cY = NumericUtils.sortableBytesToInt(t, 4 * BYTES);
cX = NumericUtils.sortableBytesToInt(t, 5 * BYTES);
break;
diff --git a/lucene/core/src/test/org/apache/lucene/document/BaseShapeEncodingTestCase.java b/lucene/core/src/test/org/apache/lucene/document/BaseShapeEncodingTestCase.java
index a3678ed..4c7ba7d 100644
--- a/lucene/core/src/test/org/apache/lucene/document/BaseShapeEncodingTestCase.java
+++ b/lucene/core/src/test/org/apache/lucene/document/BaseShapeEncodingTestCase.java
@@ -489,7 +489,7 @@ public abstract class BaseShapeEncodingTestCase extends LuceneTestCase {
verifyEncoding(ay, ax, by, bx, cy, cx);
}
- private void verifyEncoding(double ay, double ax, double by, double bx, double cy, double cx) {
+ protected void verifyEncoding(double ay, double ax, double by, double bx, double cy, double cx) {
// encode triangle
int[] original = new int[]{encodeX(ax), encodeY(ay), encodeX(bx), encodeY(by), encodeX(cx), encodeY(cy)};
byte[] b = new byte[7 * ShapeField.BYTES];
diff --git a/lucene/core/src/test/org/apache/lucene/document/TestXYShapeEncoding.java b/lucene/core/src/test/org/apache/lucene/document/TestXYShapeEncoding.java
index 030ea6b..723d056 100644
--- a/lucene/core/src/test/org/apache/lucene/document/TestXYShapeEncoding.java
+++ b/lucene/core/src/test/org/apache/lucene/document/TestXYShapeEncoding.java
@@ -63,4 +63,14 @@ public class TestXYShapeEncoding extends BaseShapeEncodingTestCase {
protected Component2D createPolygon2D(Object polygon) {
return XYGeometry.create((XYPolygon)polygon);
}
+
+ public void testRotationChangesOrientation() {
+ double ay = -3.4028218437925203E38;
+ double ax = 3.4028220466166163E38;
+ double by = 3.4028218437925203E38;
+ double bx = -3.4028218437925203E38;
+ double cy = 3.4028230607370965E38;
+ double cx = -3.4028230607370965E38;
+ verifyEncoding(ay, ax, by, bx, cy, cx);
+ }
}