You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by rm...@apache.org on 2025/04/11 19:52:00 UTC
(lucene) branch main updated: Removing unnecessary splitX in ComponentTree (#14476)
This is an automated email from the ASF dual-hosted git repository.
rmuir pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/lucene.git
The following commit(s) were added to refs/heads/main by this push:
new 6e5b2acc2a6 Removing unnecessary splitX in ComponentTree (#14476)
6e5b2acc2a6 is described below
commit 6e5b2acc2a62c1475cffbd1f946afcc86a423bf8
Author: Ankit Jain <ja...@gmail.com>
AuthorDate: Sat Apr 12 01:21:54 2025 +0530
Removing unnecessary splitX in ComponentTree (#14476)
---------
Signed-off-by: Ankit Jain <ja...@gmail.com>
---
lucene/CHANGES.txt | 2 +
.../java/org/apache/lucene/geo/ComponentTree.java | 113 ++++++++++++++++-----
2 files changed, 89 insertions(+), 26 deletions(-)
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index 9ca05b7b705..011fb7e675c 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -69,6 +69,8 @@ Improvements
---------------------
* GITHUB#14458 : Add an IndexDeletion policy that retains the last N commits. (Owais Kazi)
+* GITHUB#14476: Removing unnecessary splitX in ComponentTree (Ankit Jain)
+
Optimizations
---------------------
* GITHUB#14418: Quick exit on filter query matching no docs when rewriting knn query. (Pan Guixin)
diff --git a/lucene/core/src/java/org/apache/lucene/geo/ComponentTree.java b/lucene/core/src/java/org/apache/lucene/geo/ComponentTree.java
index 9fc77ccc969..073e3baf17d 100644
--- a/lucene/core/src/java/org/apache/lucene/geo/ComponentTree.java
+++ b/lucene/core/src/java/org/apache/lucene/geo/ComponentTree.java
@@ -27,12 +27,14 @@ import org.apache.lucene.util.ArrayUtil;
*/
final class ComponentTree implements Component2D {
- private static final Comparator<Component2D> XComparator =
+ private static final Comparator<Component2D> X_COMPARATOR =
Comparator.comparingDouble(Component2D::getMinX).thenComparingDouble(Component2D::getMaxX);
- private static final Comparator<Component2D> YComparator =
+ private static final Comparator<Component2D> Y_COMPARATOR =
Comparator.comparingDouble(Component2D::getMinY).thenComparingDouble(Component2D::getMaxY);
+ private static final boolean ROOT_SPLITX = false;
+
/** minimum Y of this geometry's bounding box area */
private double minY;
@@ -48,23 +50,18 @@ final class ComponentTree implements Component2D {
// child components, or null. Note internal nodes might mot have
// a consistent bounding box. Internal nodes should not be accessed
// outside if this class.
- private Component2D left;
- private Component2D right;
-
- /** which dimension was this node split on */
- // TODO: its implicit based on level, but boolean keeps code simple
- private final boolean splitX;
+ private ComponentTree left;
+ private ComponentTree right;
/** root node of edge tree */
private final Component2D component;
- private ComponentTree(Component2D component, boolean splitX) {
+ private ComponentTree(Component2D component) {
this.minY = component.getMinY();
this.maxY = component.getMaxY();
this.minX = component.getMinX();
this.maxX = component.getMaxX();
this.component = component;
- this.splitX = splitX;
}
@Override
@@ -89,19 +86,23 @@ final class ComponentTree implements Component2D {
@Override
public boolean contains(double x, double y) {
+ return contains(x, y, ROOT_SPLITX);
+ }
+
+ private boolean contains(double x, double y, boolean splitX) {
if (y <= this.maxY && x <= this.maxX) {
if (component.contains(x, y)) {
return true;
}
if (left != null) {
- if (left.contains(x, y)) {
+ if (left.contains(x, y, !splitX)) {
return true;
}
}
if (right != null
&& ((splitX == false && y >= this.component.getMinY())
|| (splitX && x >= this.component.getMinX()))) {
- return right.contains(x, y);
+ return right.contains(x, y, !splitX);
}
}
return false;
@@ -117,19 +118,32 @@ final class ComponentTree implements Component2D {
double aY,
double bX,
double bY) {
+ return intersectsLine(minX, maxX, minY, maxY, aX, aY, bX, bY, ROOT_SPLITX);
+ }
+
+ private boolean intersectsLine(
+ double minX,
+ double maxX,
+ double minY,
+ double maxY,
+ double aX,
+ double aY,
+ double bX,
+ double bY,
+ boolean splitX) {
if (minY <= this.maxY && minX <= this.maxX) {
if (component.intersectsLine(minX, maxX, minY, maxY, aX, aY, bX, bY)) {
return true;
}
if (left != null) {
- if (left.intersectsLine(minX, maxX, minY, maxY, aX, aY, bX, bY)) {
+ if (left.intersectsLine(minX, maxX, minY, maxY, aX, aY, bX, bY, !splitX)) {
return true;
}
}
if (right != null
&& ((splitX == false && maxY >= this.component.getMinY())
|| (splitX && maxX >= this.component.getMinX()))) {
- return right.intersectsLine(minX, maxX, minY, maxY, aX, aY, bX, bY);
+ return right.intersectsLine(minX, maxX, minY, maxY, aX, aY, bX, bY, !splitX);
}
}
return false;
@@ -147,19 +161,34 @@ final class ComponentTree implements Component2D {
double bY,
double cX,
double cY) {
+ return intersectsTriangle(minX, maxX, minY, maxY, aX, aY, bX, bY, cX, cY, ROOT_SPLITX);
+ }
+
+ private boolean intersectsTriangle(
+ double minX,
+ double maxX,
+ double minY,
+ double maxY,
+ double aX,
+ double aY,
+ double bX,
+ double bY,
+ double cX,
+ double cY,
+ boolean splitX) {
if (minY <= this.maxY && minX <= this.maxX) {
if (component.intersectsTriangle(minX, maxX, minY, maxY, aX, aY, bX, bY, cX, cY)) {
return true;
}
if (left != null) {
- if (left.intersectsTriangle(minX, maxX, minY, maxY, aX, aY, bX, bY, cX, cY)) {
+ if (left.intersectsTriangle(minX, maxX, minY, maxY, aX, aY, bX, bY, cX, cY, !splitX)) {
return true;
}
}
if (right != null
&& ((splitX == false && maxY >= this.component.getMinY())
|| (splitX && maxX >= this.component.getMinX()))) {
- return right.intersectsTriangle(minX, maxX, minY, maxY, aX, aY, bX, bY, cX, cY);
+ return right.intersectsTriangle(minX, maxX, minY, maxY, aX, aY, bX, bY, cX, cY, !splitX);
}
}
return false;
@@ -175,19 +204,32 @@ final class ComponentTree implements Component2D {
double aY,
double bX,
double bY) {
+ return containsLine(minX, maxX, minY, maxY, aX, aY, bX, bY, ROOT_SPLITX);
+ }
+
+ private boolean containsLine(
+ double minX,
+ double maxX,
+ double minY,
+ double maxY,
+ double aX,
+ double aY,
+ double bX,
+ double bY,
+ boolean splitX) {
if (minY <= this.maxY && minX <= this.maxX) {
if (component.containsLine(minX, maxX, minY, maxY, aX, aY, bX, bY)) {
return true;
}
if (left != null) {
- if (left.containsLine(minX, maxX, minY, maxY, aX, aY, bX, bY)) {
+ if (left.containsLine(minX, maxX, minY, maxY, aX, aY, bX, bY, !splitX)) {
return true;
}
}
if (right != null
&& ((splitX == false && maxY >= this.component.getMinY())
|| (splitX && maxX >= this.component.getMinX()))) {
- return right.containsLine(minX, maxX, minY, maxY, aX, aY, bX, bY);
+ return right.containsLine(minX, maxX, minY, maxY, aX, aY, bX, bY, !splitX);
}
}
return false;
@@ -205,19 +247,34 @@ final class ComponentTree implements Component2D {
double bY,
double cX,
double cY) {
+ return containsTriangle(minX, maxX, minY, maxY, aX, aY, bX, bY, cX, cY, ROOT_SPLITX);
+ }
+
+ private boolean containsTriangle(
+ double minX,
+ double maxX,
+ double minY,
+ double maxY,
+ double aX,
+ double aY,
+ double bX,
+ double bY,
+ double cX,
+ double cY,
+ boolean splitX) {
if (minY <= this.maxY && minX <= this.maxX) {
if (component.containsTriangle(minX, maxX, minY, maxY, aX, aY, bX, bY, cX, cY)) {
return true;
}
if (left != null) {
- if (left.containsTriangle(minX, maxX, minY, maxY, aX, aY, bX, bY, cX, cY)) {
+ if (left.containsTriangle(minX, maxX, minY, maxY, aX, aY, bX, bY, cX, cY, !splitX)) {
return true;
}
}
if (right != null
&& ((splitX == false && maxY >= this.component.getMinY())
|| (splitX && maxX >= this.component.getMinX()))) {
- return right.containsTriangle(minX, maxX, minY, maxY, aX, aY, bX, bY, cX, cY);
+ return right.containsTriangle(minX, maxX, minY, maxY, aX, aY, bX, bY, cX, cY, !splitX);
}
}
return false;
@@ -274,13 +331,17 @@ final class ComponentTree implements Component2D {
@Override
public Relation relate(double minX, double maxX, double minY, double maxY) {
+ return relate(minX, maxX, minY, maxY, ROOT_SPLITX);
+ }
+
+ private Relation relate(double minX, double maxX, double minY, double maxY, boolean splitX) {
if (minY <= this.maxY && minX <= this.maxX) {
Relation relation = component.relate(minX, maxX, minY, maxY);
if (relation != Relation.CELL_OUTSIDE_QUERY) {
return relation;
}
if (left != null) {
- relation = left.relate(minX, maxX, minY, maxY);
+ relation = left.relate(minX, maxX, minY, maxY, !splitX);
if (relation != Relation.CELL_OUTSIDE_QUERY) {
return relation;
}
@@ -288,7 +349,7 @@ final class ComponentTree implements Component2D {
if (right != null
&& ((splitX == false && maxY >= this.component.getMinY())
|| (splitX && maxX >= this.component.getMinX()))) {
- relation = right.relate(minX, maxX, minY, maxY);
+ relation = right.relate(minX, maxX, minY, maxY, !splitX);
return relation;
}
}
@@ -300,7 +361,7 @@ final class ComponentTree implements Component2D {
if (components.length == 1) {
return components[0];
}
- ComponentTree root = createTree(components, 0, components.length - 1, false);
+ ComponentTree root = createTree(components, 0, components.length - 1, ROOT_SPLITX);
// pull up min values for the root node so it contains a consistent bounding box
for (Component2D component : components) {
root.minY = Math.min(root.minY, component.getMinY());
@@ -318,12 +379,12 @@ final class ComponentTree implements Component2D {
final int mid = (low + high) >>> 1;
if (low < high) {
if (splitX) {
- ArrayUtil.select(components, low, high + 1, mid, XComparator);
+ ArrayUtil.select(components, low, high + 1, mid, X_COMPARATOR);
} else {
- ArrayUtil.select(components, low, high + 1, mid, YComparator);
+ ArrayUtil.select(components, low, high + 1, mid, Y_COMPARATOR);
}
}
- ComponentTree newNode = new ComponentTree(components[mid], splitX);
+ ComponentTree newNode = new ComponentTree(components[mid]);
// find children
newNode.left = createTree(components, low, mid - 1, !splitX);
newNode.right = createTree(components, mid + 1, high, !splitX);