[GitHub] [lucene-solr] iverase commented on a change in pull request #726: LUCENE-8632: New XYShape Field and Queries for indexing and searching general cartesian geometries
iverase commented on a change in pull request #726: LUCENE-8632: New XYShape
Field and Queries for indexing and searching general cartesian geometries
URL: https://github.com/apache/lucene-solr/pull/726#discussion_r299915146
##
File path: lucene/sandbox/src/java/org/apache/lucene/document/ShapeField.java
##
@@ -0,0 +1,303 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.document;
+
+import org.apache.lucene.geo.GeoUtils;
+import org.apache.lucene.geo.Line;
+import org.apache.lucene.geo.Polygon;
+import org.apache.lucene.geo.Tessellator;
+import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.NumericUtils;
+
+/**
+ * A base shape utility class used for both LatLon (spherical) and XY
(cartesian) shape fields.
+ *
+ * {@link Polygon}'s and {@link Line}'s are decomposed into a triangular mesh
using the {@link Tessellator} utility class.
+ * Each {@link Triangle} is encoded by this base class and indexed as a seven
dimension multi-value field.
+ *
+ * Finding all shapes that intersect a range (e.g., bounding box), or target
shape, at search time is efficient.
+ *
+ * This class defines the static methods for encoding the three vertices of a
tessellated triangles as a seven dimension point.
+ * The coordinates are converted from double precision values into 32 bit
integers so they are sortable at index time.
+ *
+ *
+ * @lucene.experimental
+ */
+public abstract class ShapeField {
+ /** vertex coordinates are encoded as 4 byte integers */
Review comment:
This class is abstract but not implemented by any other.
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
us...@infra.apache.org
With regards,
Apache Git Services
-
To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org
For additional commands, e-mail: dev-h...@lucene.apache.org
[GitHub] [lucene-solr] iverase commented on a change in pull request #726: LUCENE-8632: New XYShape Field and Queries for indexing and searching general cartesian geometries
iverase commented on a change in pull request #726: LUCENE-8632: New XYShape
Field and Queries for indexing and searching general cartesian geometries
URL: https://github.com/apache/lucene-solr/pull/726#discussion_r299914492
##
File path: lucene/sandbox/src/java/org/apache/lucene/document/XYShape.java
##
@@ -0,0 +1,103 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.document;
+
+import java.util.ArrayList;
+import java.util.List;
+
+import org.apache.lucene.document.ShapeField.QueryRelation; // javadoc
+import org.apache.lucene.document.ShapeField.Triangle;
+import org.apache.lucene.geo.Tessellator;
+import org.apache.lucene.index.PointValues; // javadoc
+import org.apache.lucene.geo.XYLine;
+import org.apache.lucene.geo.XYPolygon;
+import org.apache.lucene.search.Query;
+
+import static org.apache.lucene.geo.XYEncodingUtils.encode;
+
+/**
+ * A cartesian shape utility class for indexing and searching geometries whose
vertices are unitless x, y values.
+ *
+ * This class defines six static factory methods for common indexing and
search operations:
+ *
+ * {@link #createIndexableFields(String, XYPolygon)} for indexing a
cartesian polygon.
+ * {@link #createIndexableFields(String, XYLine)} for indexing a
cartesian linestring.
+ * {@link #createIndexableFields(String, double, double)} for indexing a
x, y cartesian point.
+ * {@link #newBoxQuery newBoxQuery()} for matching cartesian shapes that
have some {@link QueryRelation} with a bounding box.
+ * {@link #newBoxQuery newLineQuery()} for matching cartesian shapes
that have some {@link QueryRelation} with a linestring.
+ * {@link #newBoxQuery newPolygonQuery()} for matching cartesian shapes
that have some {@link QueryRelation} with a polygon.
+ *
+
+ * WARNING: Like {@link LatLonPoint}, vertex values are indexed with
some loss of precision from the
+ * original {@code double} values.
+ * @see PointValues
+ * @see LatLonDocValuesField
+ *
+ * @lucene.experimental
+ */
+public class XYShape {
+
+ // no instance:
+ private XYShape() {
+ }
+
+ /** create indexable fields for cartesian polygon geometry */
+ public static Field[] createIndexableFields(String fieldName, XYPolygon
polygon) {
+
+List tessellation = Tessellator.tessellate(polygon);
+List fields = new ArrayList<>(tessellation.size());
+for (Tessellator.Triangle t : tessellation) {
+ fields.add(new Triangle(fieldName, t));
+}
+return fields.toArray(new Field[fields.size()]);
+ }
+
+ /** create indexable fields for cartesian line geometry */
+ public static Field[] createIndexableFields(String fieldName, XYLine line) {
+int numPoints = line.numPoints();
+Field[] fields = new Field[numPoints - 1];
+// create "flat" triangles
+for (int i = 0, j = 1; j < numPoints; ++i, ++j) {
+ fields[i] = new Triangle(fieldName,
+ encode(line.getX(i)), encode(line.getY(i)),
+ encode(line.getX(j)), encode(line.getY(j)),
+ encode(line.getX(i)), encode(line.getY(i)));
+}
+return fields;
+ }
+
+ /** create indexable fields for cartesian point geometry */
+ public static Field[] createIndexableFields(String fieldName, double x,
double y) {
+return new Field[] {new Triangle(fieldName,
Review comment:
Should we have floats here instead?
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
us...@infra.apache.org
With regards,
Apache Git Services
-
To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org
For additional commands, e-mail: dev-h...@lucene.apache.org
[GitHub] [lucene-solr] iverase commented on a change in pull request #726: LUCENE-8632: New XYShape Field and Queries for indexing and searching general cartesian geometries
iverase commented on a change in pull request #726: LUCENE-8632: New XYShape
Field and Queries for indexing and searching general cartesian geometries
URL: https://github.com/apache/lucene-solr/pull/726#discussion_r299914357
##
File path: lucene/sandbox/src/java/org/apache/lucene/document/XYShape.java
##
@@ -0,0 +1,103 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.document;
+
+import java.util.ArrayList;
+import java.util.List;
+
+import org.apache.lucene.document.ShapeField.QueryRelation; // javadoc
+import org.apache.lucene.document.ShapeField.Triangle;
+import org.apache.lucene.geo.Tessellator;
+import org.apache.lucene.index.PointValues; // javadoc
+import org.apache.lucene.geo.XYLine;
+import org.apache.lucene.geo.XYPolygon;
+import org.apache.lucene.search.Query;
+
+import static org.apache.lucene.geo.XYEncodingUtils.encode;
+
+/**
+ * A cartesian shape utility class for indexing and searching geometries whose
vertices are unitless x, y values.
+ *
+ * This class defines six static factory methods for common indexing and
search operations:
+ *
+ * {@link #createIndexableFields(String, XYPolygon)} for indexing a
cartesian polygon.
+ * {@link #createIndexableFields(String, XYLine)} for indexing a
cartesian linestring.
+ * {@link #createIndexableFields(String, double, double)} for indexing a
x, y cartesian point.
+ * {@link #newBoxQuery newBoxQuery()} for matching cartesian shapes that
have some {@link QueryRelation} with a bounding box.
+ * {@link #newBoxQuery newLineQuery()} for matching cartesian shapes
that have some {@link QueryRelation} with a linestring.
+ * {@link #newBoxQuery newPolygonQuery()} for matching cartesian shapes
that have some {@link QueryRelation} with a polygon.
+ *
+
+ * WARNING: Like {@link LatLonPoint}, vertex values are indexed with
some loss of precision from the
+ * original {@code double} values.
+ * @see PointValues
+ * @see LatLonDocValuesField
+ *
+ * @lucene.experimental
+ */
+public class XYShape {
+
+ // no instance:
+ private XYShape() {
+ }
+
+ /** create indexable fields for cartesian polygon geometry */
+ public static Field[] createIndexableFields(String fieldName, XYPolygon
polygon) {
+
+List tessellation = Tessellator.tessellate(polygon);
+List fields = new ArrayList<>(tessellation.size());
+for (Tessellator.Triangle t : tessellation) {
+ fields.add(new Triangle(fieldName, t));
+}
+return fields.toArray(new Field[fields.size()]);
+ }
+
+ /** create indexable fields for cartesian line geometry */
+ public static Field[] createIndexableFields(String fieldName, XYLine line) {
+int numPoints = line.numPoints();
+Field[] fields = new Field[numPoints - 1];
+// create "flat" triangles
+for (int i = 0, j = 1; j < numPoints; ++i, ++j) {
+ fields[i] = new Triangle(fieldName,
+ encode(line.getX(i)), encode(line.getY(i)),
+ encode(line.getX(j)), encode(line.getY(j)),
+ encode(line.getX(i)), encode(line.getY(i)));
+}
+return fields;
+ }
+
+ /** create indexable fields for cartesian point geometry */
+ public static Field[] createIndexableFields(String fieldName, double x,
double y) {
+return new Field[] {new Triangle(fieldName,
+encode(x), encode(y), encode(x), encode(y), encode(x), encode(y))};
+ }
+
+ /** create a query to find all cartesian shapes that intersect a defined
bounding box **/
+ public static Query newBoxQuery(String field, QueryRelation queryRelation,
double minX, double maxX, double minY, double maxY) {
+return new XYShapeBoundingBoxQuery(field, queryRelation, minX, maxX, minY,
maxY);
Review comment:
Should we have floats here instead?
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
us...@infra.apache.org
With regards,
Apache Git Services
-
To unsubscribe, e-mail:
[GitHub] [lucene-solr] iverase commented on a change in pull request #726: LUCENE-8632: New XYShape Field and Queries for indexing and searching general cartesian geometries
iverase commented on a change in pull request #726: LUCENE-8632: New XYShape
Field and Queries for indexing and searching general cartesian geometries
URL: https://github.com/apache/lucene-solr/pull/726#discussion_r299802571
##
File path: lucene/sandbox/src/java/org/apache/lucene/geo/Tessellator.java
##
@@ -142,6 +183,27 @@ private static final Node createDoublyLinkedList(final
Polygon polygon, int star
return filterPoints(lastNode, null);
}
+ private static final Node eliminateHoles(final XYPolygon polygon, Node
outerNode) {
+// Define a list to hole a reference to each filtered hole list.
+final List holeList = new ArrayList<>();
+// keep a reference to the hole
+final Map holeListPolygons = new HashMap<>();
+// Iterate through each array of hole vertices.
+XYPolygon[] holes = polygon.getHoles();
+int nodeIndex = polygon.numPoints() ;
+for(int i = 0; i < polygon.numHoles(); ++i) {
+ // create the doubly-linked hole list
+ Node list = createDoublyLinkedList(holes[i].getPolyX(),
holes[i].getPolyY(), holes[i].getWindingOrder(), false, nodeIndex,
WindingOrder.CCW);
+ // Determine if the resulting hole polygon was successful.
+ if(list != null) {
+// Add the leftmost vertex of the hole.
+holeList.add(fetchLeftmost(list));
+ }
Review comment:
You need to populate here `holeListPolygons` or you get an NPE downstream
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
us...@infra.apache.org
With regards,
Apache Git Services
-
To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org
For additional commands, e-mail: dev-h...@lucene.apache.org
[GitHub] [lucene-solr] iverase commented on a change in pull request #726: LUCENE-8632: New XYShape Field and Queries for indexing and searching general cartesian geometries
iverase commented on a change in pull request #726: LUCENE-8632: New XYShape
Field and Queries for indexing and searching general cartesian geometries
URL: https://github.com/apache/lucene-solr/pull/726#discussion_r299802905
##
File path: lucene/sandbox/src/java/org/apache/lucene/geo/Tessellator.java
##
@@ -167,7 +228,10 @@ private static final Node eliminateHoles(final Polygon
polygon, Node outerNode)
}
nodeIndex += holes[i].numPoints();
}
+return eliminateHoles(holeList, holeListPolygons, outerNode);
+ }
+ private static final Node eliminateHoles(List holeList, final Map
holeListPolygons, Node outerNode) {
Review comment:
Map should have generics?
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
us...@infra.apache.org
With regards,
Apache Git Services
-
To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org
For additional commands, e-mail: dev-h...@lucene.apache.org
[GitHub] [lucene-solr] iverase commented on a change in pull request #726: LUCENE-8632: New XYShape Field and Queries for indexing and searching general cartesian geometries
iverase commented on a change in pull request #726: LUCENE-8632: New XYShape
Field and Queries for indexing and searching general cartesian geometries
URL: https://github.com/apache/lucene-solr/pull/726#discussion_r299084238
##
File path: lucene/sandbox/src/java/org/apache/lucene/geo/XYPolygon2D.java
##
@@ -0,0 +1,44 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.geo;
+
+/**
+ * 2D cartesian polygon implementation represented as a balanced interval tree
of edges.
+ *
+ * @lucene.internal
+ */
+public class XYPolygon2D extends Polygon2D {
+
+ protected XYPolygon2D(XYPolygon polygon, XYPolygon2D holes) {
Review comment:
I see, good call.
I am gearing towards the idea that if we are going to have a spatial module,
we should move everything there (even LatLonPoint). It is strange to have
classes in two different places.
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
us...@infra.apache.org
With regards,
Apache Git Services
-
To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org
For additional commands, e-mail: dev-h...@lucene.apache.org
[GitHub] [lucene-solr] iverase commented on a change in pull request #726: LUCENE-8632: New XYShape Field and Queries for indexing and searching general cartesian geometries
iverase commented on a change in pull request #726: LUCENE-8632: New XYShape
Field and Queries for indexing and searching general cartesian geometries
URL: https://github.com/apache/lucene-solr/pull/726#discussion_r298479770
##
File path: lucene/sandbox/src/java/org/apache/lucene/geo/XYRectangle2D.java
##
@@ -0,0 +1,252 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.geo;
+
+import java.util.Arrays;
+
+import org.apache.lucene.index.PointValues.Relation;
+import org.apache.lucene.util.NumericUtils;
+
+import static java.lang.Integer.BYTES;
+import static org.apache.lucene.geo.GeoUtils.orient;
+import static org.apache.lucene.geo.XYEncodingUtils.decode;
+
+/**
+ * 2D rectangle implementation containing cartesian spatial logic.
+ *
+ * @lucene.internal
+ */
+public class XYRectangle2D {
Review comment:
There is a lot of common logic with Rectangle2D, would it be worthy to try
to create a base class where all this common logic is?
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
us...@infra.apache.org
With regards,
Apache Git Services
-
To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org
For additional commands, e-mail: dev-h...@lucene.apache.org
[GitHub] [lucene-solr] iverase commented on a change in pull request #726: LUCENE-8632: New XYShape Field and Queries for indexing and searching general cartesian geometries
iverase commented on a change in pull request #726: LUCENE-8632: New XYShape
Field and Queries for indexing and searching general cartesian geometries
URL: https://github.com/apache/lucene-solr/pull/726#discussion_r298470637
##
File path: lucene/sandbox/src/java/org/apache/lucene/geo/XYPolygon2D.java
##
@@ -0,0 +1,44 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.geo;
+
+/**
+ * 2D cartesian polygon implementation represented as a balanced interval tree
of edges.
+ *
+ * @lucene.internal
+ */
+public class XYPolygon2D extends Polygon2D {
+
+ protected XYPolygon2D(XYPolygon polygon, XYPolygon2D holes) {
Review comment:
Do we really need this subclass, cannot we add this static method in
Polygon2D so there is two ways of constructing the Polygon2D, one from
(LatLon)Polygon and one from XYPolygon?
(We are actually doing so for Line2D)
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
us...@infra.apache.org
With regards,
Apache Git Services
-
To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org
For additional commands, e-mail: dev-h...@lucene.apache.org
[GitHub] [lucene-solr] iverase commented on a change in pull request #726: LUCENE-8632: New XYShape Field and Queries for indexing and searching general cartesian geometries
iverase commented on a change in pull request #726: LUCENE-8632: New XYShape
Field and Queries for indexing and searching general cartesian geometries
URL: https://github.com/apache/lucene-solr/pull/726#discussion_r298475736
##
File path: lucene/sandbox/src/java/org/apache/lucene/geo/Tessellator.java
##
@@ -119,17 +118,67 @@ private Tessellator() {}
return result;
}
+
+ public static final List tessellate(final XYPolygon polygon) {
+// Attempt to establish a doubly-linked list of the provided shell points
(should be CCW, but this will correct);
+// then filter instances of intersections.
+Node outerNode = createDoublyLinkedList(polygon, 0, WindingOrder.CW);
+// If an outer node hasn't been detected, the shape is malformed. (must
comply with OGC SFA specification)
+if(outerNode == null) {
+ throw new IllegalArgumentException("Malformed shape detected in
Tessellator!");
+}
+
+// Determine if the specified list of points contains holes
+if (polygon.numHoles() > 0) {
+ // Eliminate the hole triangulation.
+ outerNode = eliminateHoles(polygon, outerNode);
+}
+
+// If the shape crosses VERTEX_THRESHOLD, use z-order curve hashing:
+final boolean mortonOptimized;
+{
+ int threshold = VERTEX_THRESHOLD - polygon.numPoints();
+ for (int i = 0; threshold >= 0 && i < polygon.numHoles(); ++i) {
+threshold -= polygon.getHole(i).numPoints();
+ }
+
+ // Link polygon nodes in Z-Order
+ mortonOptimized = threshold < 0;
+ if (mortonOptimized == true) {
+sortByMorton(outerNode);
+ }
+}
+// Calculate the tessellation using the doubly LinkedList.
+List result = earcutLinkedList(polygon, outerNode, new
ArrayList<>(), State.INIT, mortonOptimized);
+if (result.size() == 0) {
+ throw new IllegalArgumentException("Unable to Tessellate shape [" +
polygon + "]. Possible malformed shape detected.");
+}
+
+return result;
+ }
+
+ private static final Node createDoublyLinkedList(XYPolygon polygon, int
startIndex, final WindingOrder windingOrder) {
Review comment:
We can remove this method and make the tessellate method call directly the
other one in either case (Polygon and XYPolygon)
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
us...@infra.apache.org
With regards,
Apache Git Services
-
To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org
For additional commands, e-mail: dev-h...@lucene.apache.org
