nknize commented on a change in pull request #771: LUCENE-8620: Update
Tessellator logic to label if triangle edges belongs to the original polygon
URL: https://github.com/apache/lucene-solr/pull/771#discussion_r321718707
##########
File path: lucene/sandbox/src/java/org/apache/lucene/geo/Tessellator.java
##########
@@ -590,14 +601,123 @@ private static final boolean splitEarcut(Object
polygon, final Node start, final
return false;
}
+ /** Computes if edge defined by a and b overlaps with a polygon edge **/
+ private static boolean edgeFromPolygon(final Node a, final Node b, final
boolean isMorton) {
+ if (isMorton) {
+ return mortonEdgeFromPolygon(a, b);
+ }
+ Node next = a;
+ do {
+ if (pointInLine(next, next.next, a) && pointInLine(next, next.next, b)) {
+ return next.nextEdgeFromPolygon;
+ }
+ if (pointInLine(next, next.previous, a) && pointInLine(next,
next.previous, b)) {
+ return next.previous.nextEdgeFromPolygon;
+ }
+ next = next.next;
+ } while(next != a);
+ return false;
+ }
+
+ /** Uses morton code for speed to determine whether or not and edge defined
by a and b overlaps with a polygon edge */
+ private static final boolean mortonEdgeFromPolygon(final Node a, final Node
b) {
+ // edge bbox (flip the bits so negative encoded values are < positive
encoded values)
+ final int minTX = StrictMath.min(a.x, b.x) ^ 0x80000000;
+ final int minTY = StrictMath.min(a.y, b.y) ^ 0x80000000;
+ final int maxTX = StrictMath.max(a.x, b.x) ^ 0x80000000;
+ final int maxTY = StrictMath.max(a.y, b.y) ^ 0x80000000;
+
+ // z-order range for the current edge;
+ final long minZ = BitUtil.interleave(minTX, minTY);
+ final long maxZ = BitUtil.interleave(maxTX, maxTY);
+
+ // now make sure we don't have other points inside the potential ear;
+
+ // look for points inside edge in both directions
+ Node p = a.previousZ;
+ Node n = a.nextZ;
+ while (p != null && Long.compareUnsigned(p.morton, minZ) >= 0
+ && n != null && Long.compareUnsigned(n.morton, maxZ) <= 0) {
+ if (pointInLine(p, p.next, a) && pointInLine(p, p.next, b)) {
+ return p.nextEdgeFromPolygon;
+ }
+ if (pointInLine(p, p.previous, a) && pointInLine(p, p.previous, b)) {
+ return p.previous.nextEdgeFromPolygon;
+ }
+
+ p = p.previousZ;
+
+ if (pointInLine(n, n.next, a) && pointInLine(n, n.next, b)) {
+ return n.nextEdgeFromPolygon;
+ }
+ if (pointInLine(n, n.previous, a) && pointInLine(n, n.previous, b)) {
+ return n.previous.nextEdgeFromPolygon;
+ }
+
+ n = n.nextZ;
+ }
+
+ // first look for points inside the edge in decreasing z-order
+ while (p != null && Long.compareUnsigned(p.morton, minZ) >= 0) {
+ if (pointInLine(p, p.next, a) && pointInLine(p, p.next, b)) {
+ return p.nextEdgeFromPolygon;
+ }
+ if (pointInLine(p, p.previous, a) && pointInLine(p, p.previous, b)) {
+ return p.previous.nextEdgeFromPolygon;
+ }
+ p = p.previousZ;
+ }
+ // then look for points in increasing z-order
+ while (n != null &&
+ Long.compareUnsigned(n.morton, maxZ) <= 0) {
+ if (pointInLine(n, n.next, a) && pointInLine(n, n.next, b)) {
+ return n.nextEdgeFromPolygon;
+ }
+ if (pointInLine(n, n.previous, a) && pointInLine(n, n.previous, b)) {
+ return n.previous.nextEdgeFromPolygon;
+ }
+ n = n.nextZ;
+ }
+ return false;
+ }
+
+ private static boolean pointInLine(final Node a, final Node b, final Node
point) {
+ return pointInLine(a, b, point.getX(), point.getY());
+ }
+
+ private static boolean pointInLine(final Node a, final Node b, final double
lon, final double lat) {
+ final double dxc = lon - a.getX();
+ final double dyc = lat - a.getY();
+
+ final double dxl = b.getX() - a.getX();
+ final double dyl = b.getY() - a.getY();
+
+ if (dxc * dyl - dyc * dxl == 0) {
+ if (Math.abs(dxl) >= Math.abs(dyl)) {
+ return dxl > 0 ?
+ a.getX() <= lon && lon <= b.getX() :
+ b.getX() <= lon && lon <= a.getX();
+ } else {
+ return dyl > 0 ?
+ a.getY() <= lat && lat <= b.getY() :
+ b.getY() <= lat && lat <= a.getY();
+ }
+ }
+ return false;
+ }
+
+
+ /** Links two polygon vertices using a bridge. **/ /** Links
two polygon vert
Review comment:
dangling comment?
----------------------------------------------------------------
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:
[email protected]
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
