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 2019/06/11 05:01:50 UTC
[lucene-solr] branch master updated: LUCENE-8775: Compute properly
the bridge between a polygon and a hole when sharing a vertex.
This is an automated email from the ASF dual-hosted git repository.
ivera pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/lucene-solr.git
The following commit(s) were added to refs/heads/master by this push:
new 88c5817 LUCENE-8775: Compute properly the bridge between a polygon and a hole when sharing a vertex.
88c5817 is described below
commit 88c5817c01ad3c92380ef432212cae5571713a94
Author: Ignacio Vera <iv...@apache.org>
AuthorDate: Tue Jun 11 07:01:42 2019 +0200
LUCENE-8775: Compute properly the bridge between a polygon and a hole when sharing a vertex.
---
.../java/org/apache/lucene/geo/Tessellator.java | 44 +++++++++++----
.../org/apache/lucene/geo/TestTessellator.java | 65 +++++++++++++++++++++-
2 files changed, 97 insertions(+), 12 deletions(-)
diff --git a/lucene/sandbox/src/java/org/apache/lucene/geo/Tessellator.java b/lucene/sandbox/src/java/org/apache/lucene/geo/Tessellator.java
index 950ebd8..966db6a 100644
--- a/lucene/sandbox/src/java/org/apache/lucene/geo/Tessellator.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/geo/Tessellator.java
@@ -199,8 +199,24 @@ final public class Tessellator {
/** Finds a bridge between vertices that connects a hole with an outer ring, and links it */
private static final void eliminateHole(final Node holeNode, Node outerNode, Polygon hole) {
+ // Attempt to find a common point between the HoleNode and OuterNode.
+ Node next = outerNode;
+ do {
+ if (Rectangle.containsPoint(next.getLat(), next.getLon(), hole.minLat, hole.maxLat, hole.minLon, hole.maxLon)) {
+ Node sharedVertex = getSharedVertex(holeNode, next);
+ if (sharedVertex != null) {
+ // Split the resulting polygon.
+ Node node = splitPolygon(next, sharedVertex);
+ // Filter the split nodes.
+ filterPoints(node, node.next);
+ return;
+ }
+ }
+ next = next.next;
+ } while (next != outerNode);
+
// Attempt to find a logical bridge between the HoleNode and OuterNode.
- outerNode = fetchHoleBridge(holeNode, outerNode, hole);
+ outerNode = fetchHoleBridge(holeNode, outerNode);
// Determine whether a hole bridge could be fetched.
if(outerNode != null) {
@@ -216,7 +232,7 @@ final public class Tessellator {
*
* see: http://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf
**/
- private static final Node fetchHoleBridge(final Node holeNode, final Node outerNode, Polygon hole) {
+ private static final Node fetchHoleBridge(final Node holeNode, final Node outerNode) {
Node p = outerNode;
double qx = Double.NEGATIVE_INFINITY;
final double hx = holeNode.getX();
@@ -226,13 +242,6 @@ final public class Tessellator {
// segment's endpoint with lesser x will be potential connection point
{
do {
- //if vertex of the polygon is a vertex of the hole, just use that point.
- if (Rectangle.containsPoint(p.getLat(), p.getLon(), hole.minLat, hole.maxLat, hole.minLon, hole.maxLon)) {
- Node sharedVertex = getSharedVertex(holeNode, p);
- if (sharedVertex != null) {
- return sharedVertex;
- }
- }
if (hy <= p.getY() && hy >= p.next.getY() && p.next.getY() != p.getY()) {
final double x = p.getX() + (hy - p.getY()) * (p.next.getX() - p.getX()) / (p.next.getY() - p.getY());
if (x <= hx && x > qx) {
@@ -528,9 +537,9 @@ final public class Tessellator {
/** Determines whether a diagonal between two polygon nodes lies within a polygon interior. (This determines the validity of the ray.) **/
private static final boolean isValidDiagonal(final Node a, final Node b) {
- //If points are equal then use it
if (isVertexEquals(a, b)) {
- return true;
+ //If points are equal then use it if they are valid polygons
+ return isCWPolygon(a, b);
}
return a.next.idx != b.idx && a.previous.idx != b.idx
&& isIntersectingPolygon(a, a.getX(), a.getY(), b.getX(), b.getY()) == false
@@ -538,6 +547,19 @@ final public class Tessellator {
&& middleInsert(a, a.getX(), a.getY(), b.getX(), b.getY());
}
+ /** Determine whether the polygon defined between node start and node end is CW */
+ private static boolean isCWPolygon(Node start, Node end) {
+ Node next = start;
+ double windingSum = 0;
+ do {
+ // compute signed area
+ windingSum += area(next.getLon(), next.getLat(), next.next.getLon(), next.next.getLat(), end.getLon(), end.getLat());
+ next = next.next;
+ } while (next.next != end);
+ //The polygon must be CW
+ return (windingSum < 0) ? true : false;
+ }
+
private static final boolean isLocallyInside(final Node a, final Node b) {
double area = area(a.previous.getX(), a.previous.getY(), a.getX(), a.getY(), a.next.getX(), a.next.getY());
if (area == 0) {
diff --git a/lucene/sandbox/src/test/org/apache/lucene/geo/TestTessellator.java b/lucene/sandbox/src/test/org/apache/lucene/geo/TestTessellator.java
index 247a7ed..fcfe1ab 100644
--- a/lucene/sandbox/src/test/org/apache/lucene/geo/TestTessellator.java
+++ b/lucene/sandbox/src/test/org/apache/lucene/geo/TestTessellator.java
@@ -508,9 +508,72 @@ public class TestTessellator extends LuceneTestCase {
checkPolygon(wkt);
}
+ public void testComplexPolygon38() throws Exception {
+ String wkt ="POLYGON((-80.1124643 40.8042035, -80.1124675 40.8044718, -80.1124274 40.8045944, -80.1123667 40.8047618, -80.1123187 40.8048961, -80.1122144 40.8052404, -80.1121822 40.8054597, " +
+ "-80.1126328 40.8055247, -80.11318 40.8057277, -80.1136735 40.8060119, -80.1139935 40.8061, -80.1144689 40.8062548, -80.1147571 40.8065235, -80.115177 40.8068213, -80.1152614 40.8070676, " +
+ "-80.1150468 40.8073031, -80.1149288 40.8075955, -80.1150039 40.8079934, -80.1151026 40.8081061, -80.1152399 40.8081396, -80.1156798 40.8082857, -80.1151843 40.8089253, -80.1156524 40.808904, " +
+ "-80.1162332 40.8091775, -80.1157808 40.8095377, -80.1156441 40.8096134, -80.1155087 40.8096884, -80.1151646 40.8098791, -80.1147561 40.8100954, -80.1147128 40.8101183, -80.1145352 40.8101879, " +
+ "-80.1142434 40.8103022, -80.1137421 40.8105106, -80.1136367 40.8101601, -80.1124244 40.8101033, -80.1121871 40.8099392, -80.1122527 40.8098272, -80.1125317 40.8098231, -80.1126926 40.8093887, " +
+ "-80.1129976 40.808775, -80.1128367 40.8084177, -80.1128685 40.8082688, -80.1129547 40.8078655, -80.1128903 40.8073945, -80.1128903 40.8069722, -80.1130083 40.8067529, -80.1128045 40.8065174, " +
+ "-80.1121608 40.8063794, -80.1115492 40.8062576, -80.111312 40.806182, -80.1111323 40.8063058, -80.1108733 40.8061601, -80.1099828 40.8057866, -80.1095966 40.8057297, -80.1091352 40.805478, " +
+ "-80.1085936 40.8053328, -80.1080731 40.8053967, -80.1077088 40.8055159, -80.1073654 40.8054672, -80.1063779 40.8050719, -80.1057878 40.8048932, -80.1051012 40.8047146, -80.1045237 40.804701, " +
+ "-80.1039834 40.803764, -80.1044145 40.803941, -80.1055089 40.8042334, -80.1063243 40.8044527, -80.1069251 40.8045014, -80.1073717 40.8045757, -80.1076775 40.8047463, -80.1081173 40.8047138, " +
+ "-80.1085143 40.8046813, -80.1088241 40.8049968, -80.1093399 40.8050004, -80.1096931 40.8050455, -80.1101759 40.8050618, -80.1103047 40.8050374, -80.1104549 40.8046232, -80.1106051 40.8041522, " +
+ "-80.1107553 40.8036937, -80.1088178 40.8030618, -80.1088714 40.8029156, -80.1094293 40.8030496, -80.1095751 40.8030051, -80.1091996 40.802599, -80.1089636 40.8023797, -80.1090816 40.8022741, " +
+ "-80.109382 40.8023797, -80.1099399 40.8025746, -80.1103905 40.8028751, -80.1108089 40.8030375, -80.1110557 40.8028914, -80.1114956 40.80307, -80.1119998 40.803338, -80.112429 40.8033299, -80.112665 40.8031512, " +
+ "-80.1121822 40.8029563, -80.1115063 40.8025665, -80.1108411 40.8023391, -80.1105407 40.8018924, -80.1103905 40.8014945, -80.1098648 40.8012996, -80.1092318 40.8009828, -80.1086417 40.8009585, " +
+ "-80.1087597 40.8006417, -80.1096065 40.8007592, -80.1117469 40.8018434, -80.1126175 40.8023287, -80.1138093 40.8032437, -80.1140089 40.8033365, -80.1142363 40.8033396, -80.1146277 40.8032744, " +
+ "-80.1159865 40.8029532, -80.1172922 40.802728, -80.1177849 40.8026481, -80.1179499 40.8014287, -80.1177068 40.8033675, -80.1176231 40.8040661, -80.1175682 40.8044886, -80.1173232 40.8045697, " +
+ "-80.114679 40.804454, -80.1146739 40.8043283, -80.1147726 40.8038162, -80.1139347 40.8040133, -80.1132184 40.8040944, -80.113193 40.8041732, -80.1130709 40.8042723, -80.1128737 40.80424, -80.1124643 40.8042035), " +
+ "(-80.112012 40.8039682, -80.1111747 40.8038305, -80.111237 40.8038512, -80.112012 40.8039682)," +
+ " (-80.1124643 40.8042035, -80.112484 40.804144, -80.1125136 40.8040207, -80.1124643 40.8042035))";
+ checkPolygon(wkt);
+ }
+
+ public void testComplexPolygon39() throws Exception {
+ String wkt ="POLYGON((71.8821959 52.3494653, 71.8824975 52.3494644, 71.8825076 52.3485511, 71.88209 52.3485465, 71.8820828 52.3487054, 71.8822007 52.3487626, 71.8822 52.3488601, 71.8821989 52.3490193, 71.8821959 52.3494653), " +
+ "(71.8823576 52.3489838, 71.882321 52.348962, 71.882357 52.3489395, 71.8823936 52.3489613, 71.8823576 52.3489838), " +
+ "(71.8823569 52.3494143, 71.8823916 52.349435, 71.8823568 52.3494567, 71.8823221 52.349436, 71.8823569 52.3494143), " +
+ "(71.8823569 52.3494143, 71.8823263 52.349396, 71.8823588 52.3493757, 71.8823894 52.3493939, 71.8823569 52.3494143), " +
+ "(71.8823588 52.3493757, 71.8823258 52.349356, 71.8823595 52.349335, 71.8823925 52.3493547, 71.8823588 52.3493757), " +
+ "(71.8823595 52.349335, 71.8823277 52.3493161, 71.8823602 52.3492958, 71.8823919 52.3493147, 71.8823595 52.349335), " +
+ "(71.8823602 52.3492958, 71.8823307 52.3492782, 71.8823595 52.3492602, 71.882389 52.3492778, 71.8823602 52.3492958), " +
+ "(71.8823595 52.3492602, 71.8823307 52.349243, 71.8823611 52.349224, 71.8823899 52.3492412, 71.8823595 52.3492602), " +
+ "(71.8823611 52.349224, 71.8823276 52.3492041, 71.882361 52.3491832, 71.8823944 52.3492031, 71.8823611 52.349224), " +
+ "(71.882361 52.3491832, 71.8823281 52.3491636, 71.8823613 52.3491428, 71.8823942 52.3491624, 71.882361 52.3491832), " +
+ "(71.8823613 52.3491428, 71.8823305 52.3491244, 71.8823618 52.3491048, 71.8823927 52.3491232, 71.8823613 52.3491428), " +
+ "(71.8823618 52.3491048, 71.8823294 52.3490854, 71.8823607 52.3490659, 71.8823931 52.3490852, 71.8823618 52.3491048), " +
+ "(71.8823607 52.3490659, 71.8823285 52.3490467, 71.8823581 52.3490282, 71.8823902 52.3490474, 71.8823607 52.3490659), " +
+ "(71.8823581 52.3490282, 71.8823215 52.3490064, 71.8823576 52.3489838, 71.8823942 52.3490057, 71.8823581 52.3490282))";
+ checkPolygon(wkt);
+ }
+
private void checkPolygon(String wkt) throws Exception {
Polygon polygon = (Polygon) SimpleWKTShapeParser.parse(wkt);
List<Tessellator.Triangle> tessellation = Tessellator.tessellate(polygon);
- assertTrue(tessellation.size() > 0);
+ assertEquals(area(polygon), area(tessellation), 0.0);
+ }
+
+ private double area(Polygon p) {
+ double val = 0;
+ for (int i = 0; i < p.numPoints() - 1; i++) {
+ val += p.getPolyLon(i) * p.getPolyLat(i + 1)
+ - p.getPolyLat(i) * p.getPolyLon(i + 1);
+ }
+ double area = Math.abs(val / 2.);
+ for (Polygon hole : p.getHoles()) {
+ area -= area(hole);
+ }
+ return area;
+ }
+
+ private double area(List<Tessellator.Triangle> triangles) {
+ double area = 0;
+ for (Tessellator.Triangle t : triangles) {
+ double[] lats = new double[] {t.getLat(0), t.getLat(1), t.getLat(2), t.getLat(0)};
+ double[] lons = new double[] {t.getLon(0), t.getLon(1), t.getLon(2), t.getLon(0)};
+ area += area(new Polygon(lats, lons));
+ }
+ return area;
}
}
\ No newline at end of file