lucene/core/src/java/org/apache/lucene/geo/EdgeTree.java

/*
 * 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 static org.apache.lucene.geo.GeoUtils.lineCrossesLine;
import static org.apache.lucene.geo.GeoUtils.lineCrossesLineWithBoundary;
import static org.apache.lucene.geo.GeoUtils.orient;

/**
 * Internal tree node: represents geometry edge from [x1, y1] to [x2, y2].
 * The sort value is {@code low}, which is the minimum y of the edge.
 * {@code max} stores the maximum y of this edge or any children.
 * <p>
 * Construction takes {@code O(n log n)} time for sorting and tree construction.
 * Methods are {@code O(n)}, but for most
 * practical lines and polygons are much faster than brute force.
 */
final class EdgeTree {
  // X-Y pair (in original order) of the two vertices
  final double y1, y2;
  final double x1, x2;
  /** min Y of this edge */
  final double low;
  /** max Y of this edge or any children */
  double max;
  /** left child edge, or null */
  EdgeTree left;
  /** right child edge, or null */
  EdgeTree right;
  /** helper bytes to signal if a point is on an edge, it is within the edge tree or disjoint */
  final private static byte FALSE = 0x00;
  final private static byte TRUE = 0x01;
  final private static byte ON_EDGE = 0x02;

  private EdgeTree(double x1, double y1, double x2, double y2, double low, double max) {
    this.y1 = y1;
    this.x1 = x1;
    this.y2 = y2;
    this.x2 = x2;
    this.low = low;
    this.max = max;
  }

  /**
   * Returns true if the point is on an edge or crosses the edge subtree an odd number
   * of times.
   */
  protected boolean contains(double x, double y) {
    return containsPnPoly(x, y) > FALSE;
  }

  /**
   * Returns byte 0x00 if the point crosses this edge subtree an even number of times.
   * Returns byte 0x01 if the point crosses this edge subtree an odd number of times.
   * Returns byte 0x02 if the point is on one of the edges.
   * <p>
   * See <a href="https://www.ecse.rpi.edu/~wrf/Research/Short_Notes/pnpoly.html">
   * https://www.ecse.rpi.edu/~wrf/Research/Short_Notes/pnpoly.html</a> for more information.
   */
  // ported to java from https://www.ecse.rpi.edu/~wrf/Research/Short_Notes/pnpoly.html
  // original code under the BSD license (https://www.ecse.rpi.edu/~wrf/Research/Short_Notes/pnpoly.html#License%20to%20Use)
  //
  // Copyright (c) 1970-2003, Wm. Randolph Franklin
  //
  // Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated
  // documentation files (the "Software"), to deal in the Software without restriction, including without limitation
  // the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and
  // to permit persons to whom the Software is furnished to do so, subject to the following conditions:
  //
  // 1. Redistributions of source code must retain the above copyright
  //    notice, this list of conditions and the following disclaimers.
  // 2. Redistributions in binary form must reproduce the above copyright
  //    notice in the documentation and/or other materials provided with
  //    the distribution.
  // 3. The name of W. Randolph Franklin may not be used to endorse or
  //    promote products derived from this Software without specific
  //    prior written permission.
  //
  // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
  // TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
  // THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF
  // CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
  // IN THE SOFTWARE.
  private byte containsPnPoly(double x, double y) {
    byte res = FALSE;
    if (y <= this.max) {
      if (y == this.y1 && y == this.y2 ||
          (y <= this.y1 && y >= this.y2) != (y >= this.y1 && y <= this.y2)) {
        if ((x == this.x1 && x == this.x2) ||
            ((x <= this.x1 && x >= this.x2) != (x >= this.x1 && x <= this.x2) &&
                GeoUtils.orient(this.x1, this.y1, this.x2, this.y2, x, y) == 0)) {
          return ON_EDGE;
        } else if (this.y1 > y != this.y2 > y) {
          res = x < (this.x2 - this.x1) * (y - this.y1) / (this.y2 - this.y1) + this.x1 ? TRUE : FALSE;
        }
      }
      if (this.left != null) {
        res ^= left.containsPnPoly(x, y);
        if ((res & 0x02) == 0x02) {
          return ON_EDGE;
        }
      }

      if (this.right != null && y >= this.low) {
        res ^= right.containsPnPoly(x, y);
        if ((res & 0x02) == 0x02) {
          return ON_EDGE;
        }
      }
    }
    assert res >= FALSE && res <= ON_EDGE;
    return res;
  }

  /** returns true if the provided x, y point lies on the line */
  boolean isPointOnLine(double x, double y) {
    if (y <= max) {
      double a1x = x1;
      double a1y = y1;
      double b1x = x2;
      double b1y = y2;
      boolean outside = (a1y < y && b1y < y) ||
          (a1y > y && b1y > y) ||
          (a1x < x && b1x < x) ||
          (a1x > x && b1x > x);
      if (outside == false && orient(a1x, a1y, b1x, b1y, x, y) == 0) {
        return true;
      }
      if (left != null && left.isPointOnLine(x, y)) {
        return true;
      }
      if (right != null && y >= this.low && right.isPointOnLine(x, y)) {
        return true;
      }
    }
    return false;
  }


  /** Returns true if the triangle crosses any edge in this edge subtree */
  boolean crossesTriangle(double minX, double maxX, double minY, double maxY,
                          double ax, double ay, double bx, double by, double cx, double cy, boolean includeBoundary) {
      if (minY <= max) {
        double dy = y1;
        double ey = y2;
        double dx = x1;
        double ex = x2;

        // optimization: see if the rectangle is outside of the "bounding box" of the polyline at all
        // if not, don't waste our time trying more complicated stuff
        boolean outside = (dy < minY && ey < minY) ||
            (dy > maxY && ey > maxY) ||
            (dx < minX && ex < minX) ||
            (dx > maxX && ex > maxX);

        if (outside == false) {
          if (includeBoundary == true) {
            if (lineCrossesLineWithBoundary(dx, dy, ex, ey, ax, ay, bx, by) ||
                lineCrossesLineWithBoundary(dx, dy, ex, ey, bx, by, cx, cy) ||
                lineCrossesLineWithBoundary(dx, dy, ex, ey, cx, cy, ax, ay)) {
              return true;
            }
          } else {
            if (lineCrossesLine(dx, dy, ex, ey, ax, ay, bx, by) ||
                lineCrossesLine(dx, dy, ex, ey, bx, by, cx, cy) ||
                lineCrossesLine(dx, dy, ex, ey, cx, cy, ax, ay)) {
              return true;
            }
          }
        }


        if (left != null && left.crossesTriangle(minX, maxX, minY, maxY, ax, ay, bx, by, cx, cy, includeBoundary)) {
          return true;
        }

        if (right != null && maxY >= low && right.crossesTriangle(minX, maxX, minY, maxY, ax, ay, bx, by, cx, cy, includeBoundary)) {
          return true;
        }
      }
      return false;
    }

  /** Returns true if the box crosses any edge in this edge subtree */
  boolean crossesBox(double minX, double maxX, double minY, double maxY, boolean includeBoundary) {
    // we just have to cross one edge to answer the question, so we descend the tree and return when we do.
    if (minY <= max) {
      // we compute line intersections of every polygon edge with every box line.
      // if we find one, return true.
      // for each box line (AB):
      //   for each poly line (CD):
      //     intersects = orient(C,D,A) * orient(C,D,B) <= 0 && orient(A,B,C) * orient(A,B,D) <= 0
      double cy = y1;
      double dy = y2;
      double cx = x1;
      double dx = x2;

      // optimization: see if either end of the line segment is contained by the rectangle
      if (Rectangle.containsPoint(cy, cx, minY, maxY, minX, maxX) ||
          Rectangle.containsPoint(dy, dx, minY, maxY, minX, maxX)) {
        return true;
      }

      // optimization: see if the rectangle is outside of the "bounding box" of the polyline at all
      // if not, don't waste our time trying more complicated stuff
      boolean outside = (cy < minY && dy < minY) ||
          (cy > maxY && dy > maxY) ||
          (cx < minX && dx < minX) ||
          (cx > maxX && dx > maxX);

      if (outside == false) {
        if (includeBoundary == true) {
           if (lineCrossesLineWithBoundary(cx, cy, dx, dy, minX, minY, maxX, minY) ||
            lineCrossesLineWithBoundary(cx, cy, dx, dy, maxX, minY, maxX, maxY) ||
            lineCrossesLineWithBoundary(cx, cy, dx, dy, maxX, maxY, minX, maxY) ||
            lineCrossesLineWithBoundary(cx, cy, dx, dy, minX, maxY, minX, minY)) {
             // include boundaries: ensures box edges that terminate on the polygon are included
             return true;
           }
        } else {
          if (lineCrossesLine(cx, cy, dx, dy, minX, minY, maxX, minY) ||
              lineCrossesLine(cx, cy, dx, dy, maxX, minY, maxX, maxY) ||
              lineCrossesLine(cx, cy, dx, dy, maxX, maxY, minX, maxY) ||
              lineCrossesLine(cx, cy, dx, dy, minX, maxY, minX, minY)) {
            return true;
          }
        }
      }

      if (left != null && left.crossesBox(minX, maxX, minY, maxY, includeBoundary)) {
        return true;
      }

      if (right != null && maxY >= low && right.crossesBox(minX, maxX, minY, maxY, includeBoundary)) {
        return true;
      }
    }
    return false;
  }

  /** Returns true if the line crosses any edge in this edge subtree */
  boolean crossesLine(double minX, double maxX, double minY, double maxY, double a2x, double a2y, double b2x, double b2y, boolean includeBoundary) {
    if (minY <= max) {
      double a1x = x1;
      double a1y = y1;
      double b1x = x2;
      double b1y = y2;

      boolean outside = (a1y < minY && b1y < minY) ||
          (a1y > maxY && b1y > maxY) ||
          (a1x < minX && b1x < minX) ||
          (a1x > maxX && b1x > maxX);
      if (outside == false) {
        if (includeBoundary) {
          if (lineCrossesLineWithBoundary(a1x, a1y, b1x, b1y, a2x, a2y, b2x, b2y)) {
            return true;
          }
        } else {
          if (lineCrossesLine(a1x, a1y, b1x, b1y, a2x, a2y, b2x, b2y)) {
            return true;
          }
        }
      }
      if (left != null && left.crossesLine(minX, maxX, minY, maxY, a2x, a2y, b2x, b2y, includeBoundary)) {
        return true;
      }
      if (right != null && maxY >= low && right.crossesLine(minX, maxX, minY, maxY, a2x, a2y, b2x, b2y, includeBoundary)) {
        return true;
      }
    }
    return false;
  }

  /**
   * Creates an edge interval tree from a set of geometry vertices.
   * @return root node of the tree.
   */
  static EdgeTree createTree(double[] x, double[] y) {
    EdgeTree edges[] = new EdgeTree[x.length - 1];
    for (int i = 1; i < x.length; i++) {
      double x1 = x[i-1];
      double y1 = y[i-1];
      double x2 = x[i];
      double y2 = y[i];
      edges[i - 1] = new EdgeTree(x1, y1, x2, y2, Math.min(y1, y2), Math.max(y1, y2));
    }
    // sort the edges then build a balanced tree from them
    Arrays.sort(edges, (left, right) -> {
      int ret = Double.compare(left.low, right.low);
      if (ret == 0) {
        ret = Double.compare(left.max, right.max);
      }
      return ret;
    });
    return createTree(edges, 0, edges.length - 1);
  }

  /** Creates tree from sorted edges (with range low and high inclusive) */
  private static EdgeTree createTree(EdgeTree edges[], int low, int high) {
    if (low > high) {
      return null;
    }
    // add midpoint
    int mid = (low + high) >>> 1;
    EdgeTree newNode = edges[mid];
    // add children
    newNode.left = createTree(edges, low, mid - 1);
    newNode.right = createTree(edges, mid + 1, high);
    // pull up max values to this node
    if (newNode.left != null) {
      newNode.max = Math.max(newNode.max, newNode.left.max);
    }
    if (newNode.right != null) {
      newNode.max = Math.max(newNode.max, newNode.right.max);
    }
    return newNode;
  }
}