001//The MIT License (MIT) 002// 003//Copyright (c) 2015 Johannes Diemke 004// 005//Permission is hereby granted, free of charge, to any person obtaining a copy 006//of this software and associated documentation files (the "Software"), to deal 007//in the Software without restriction, including without limitation the rights 008//to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 009//copies of the Software, and to permit persons to whom the Software is 010//furnished to do so, subject to the following conditions: 011// 012//The above copyright notice and this permission notice shall be included in all 013//copies or substantial portions of the Software. 014// 015//THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 016//IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 017//FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 018//AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 019//LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 020//OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 021//SOFTWARE. 022 023package squidpony.squidmath; 024 025import java.io.Serializable; 026import java.util.ArrayList; 027import java.util.Comparator; 028import java.util.ListIterator; 029 030/** 031 * A Java implementation of both a 2D Delaunay triangulation algorithm and a Voronoi polygon data structure. 032 * This is a port of <a href="https://github.com/jdiemke/delaunay-triangulator">Johannes Diemke's code</a>, with 033 * <a href="http://www-cs-students.stanford.edu/~amitp/game-programming/polygon-map-generation/#graphs">modifications 034 * suggested by Amit Patel to consolidate the triangles with a barycentric dual mesh</a>. 035 * @author Johannes Diemke 036 * @author Tommy Ettinger 037 */ 038public class Voronoi implements Serializable { 039 private static final long serialVersionUID = 1L; 040 041 private OrderedSet<CoordDouble> pointSet; 042 private TriangleSoup triangleSoup; 043 private ArrayList<Polygon> polygonSoup; 044 045 /** 046 * Constructs a triangulator instance but does not insert any points; you should add points to 047 * {@link #getPointSet()} before running {@link #triangulate()}. 048 */ 049 public Voronoi() { 050 this.pointSet = new OrderedSet<>(256); 051 this.triangleSoup = new TriangleSoup(); 052 } 053 054 /** 055 * Constructs a new triangulator instance using the specified point set. 056 * 057 * @param pointSet The point set to be triangulated 058 */ 059 public Voronoi(OrderedSet<CoordDouble> pointSet) { 060 this.pointSet = pointSet; 061 this.triangleSoup = new TriangleSoup(); 062 } 063 064 /** 065 * This method generates a Delaunay triangulation from the specified point 066 * set. 067 */ 068 public ArrayList<Triangle> triangulate() { 069 int numPoints; 070 if (pointSet == null || (numPoints = pointSet.size()) < 3) { 071 throw new IllegalArgumentException("Less than three points in point set."); 072 } 073 triangleSoup = new TriangleSoup(); 074 075 /* 076 * In order for the in circumcircle test to not consider the vertices of 077 * the super triangle we have to start out with a big triangle 078 * containing the whole point set. We have to scale the super triangle 079 * to be very large. Otherwise the triangulation is not convex. 080 */ 081 double maxOfAnyCoordinate = 0.0; 082 083 for (int i = 0; i < numPoints; i++) { 084 final CoordDouble pt = pointSet.getAt(i); 085 maxOfAnyCoordinate = Math.max(Math.max(pt.x, pt.y), maxOfAnyCoordinate); 086 } 087 088 maxOfAnyCoordinate *= 48.0; 089 090 CoordDouble p1 = new CoordDouble(0.0, maxOfAnyCoordinate); 091 CoordDouble p2 = new CoordDouble(maxOfAnyCoordinate, 0.0); 092 CoordDouble p3 = new CoordDouble(-maxOfAnyCoordinate, -maxOfAnyCoordinate); 093 094 Triangle superTriangle = new Triangle(p1, p2, p3); 095 096 triangleSoup.add(superTriangle); 097 098 for (int i = 0; i < pointSet.size(); i++) { 099 Triangle triangle = triangleSoup.findContainingTriangle(pointSet.getAt(i)); 100 101 if (triangle == null) { 102 /* 103 * If no containing triangle exists, then the vertex is not 104 * inside a triangle (this can also happen due to numerical 105 * errors) and lies on an edge. In order to find this edge we 106 * search all edges of the triangle soup and select the one 107 * which is nearest to the point we try to add. This edge is 108 * removed and four new edges are added. 109 */ 110 Edge edge = triangleSoup.findNearestEdge(pointSet.getAt(i)); 111 112 Triangle first = triangleSoup.findOneTriangleSharing(edge); 113 Triangle second = triangleSoup.findNeighbor(first, edge); 114 115 CoordDouble firstNonEdgeVertex = first.getNonEdgeVertex(edge); 116 CoordDouble secondNonEdgeVertex = second.getNonEdgeVertex(edge); 117 CoordDouble p = pointSet.getAt(i); 118 119 triangleSoup.remove(first); 120 triangleSoup.remove(second); 121 122 Triangle triangle1 = new Triangle(edge.a, firstNonEdgeVertex, p); 123 Triangle triangle2 = new Triangle(edge.b, firstNonEdgeVertex, p); 124 Triangle triangle3 = new Triangle(edge.a, secondNonEdgeVertex, p); 125 Triangle triangle4 = new Triangle(edge.b, secondNonEdgeVertex, p); 126 127 triangleSoup.add(triangle1); 128 triangleSoup.add(triangle2); 129 triangleSoup.add(triangle3); 130 triangleSoup.add(triangle4); 131 132 legalizeEdge(triangle1, edge.a, firstNonEdgeVertex, p); 133 legalizeEdge(triangle2, edge.b, firstNonEdgeVertex, p); 134 legalizeEdge(triangle3, edge.a, secondNonEdgeVertex, p); 135 legalizeEdge(triangle4, edge.b, secondNonEdgeVertex, p); 136 } else { 137 /* 138 * The vertex is inside a triangle. 139 */ 140 CoordDouble a = triangle.a; 141 CoordDouble b = triangle.b; 142 CoordDouble c = triangle.c; 143 CoordDouble p = pointSet.getAt(i); 144 145 triangleSoup.remove(triangle); 146 147 Triangle first = new Triangle(a, b, p); 148 Triangle second = new Triangle(b, c, p); 149 Triangle third = new Triangle(c, a, p); 150 151 triangleSoup.add(first); 152 triangleSoup.add(second); 153 triangleSoup.add(third); 154 155 legalizeEdge(first, a, b, p); 156 legalizeEdge(second, b, c, p); 157 legalizeEdge(third, c, a, p); 158 } 159 } 160 161 /* 162 * Remove all triangles that contain vertices of the super triangle. 163 */ 164 triangleSoup.removeTrianglesUsing(superTriangle.a); 165 triangleSoup.removeTrianglesUsing(superTriangle.b); 166 triangleSoup.removeTrianglesUsing(superTriangle.c); 167 return triangleSoup.getTriangles(); 168 } 169 170 public ArrayList<Polygon> polygonize() 171 { 172 triangulate(); 173 polygonSoup = new ArrayList<>(triangleSoup.triangleSoup.size()); 174 ArrayList<CoordDouble> vs = new ArrayList<>(16); 175 Triangle next; 176 CoordDouble n; 177 for(Triangle tri : triangleSoup.triangleSoup) { 178 vs.clear(); 179 vs.add(tri.centroid); 180 next = triangleSoup.findNeighbor(tri, tri.a, tri.b); 181 if (next != null) { 182 n = next.getNonEdgeVertex(tri.a, tri.b); 183 while (next != tri) { 184 vs.add(next.centroid); 185 next = triangleSoup.findNeighbor(next, tri.a, n); 186 if (next == null) 187 break; 188 n = next.getNonEdgeVertex(tri.a, n); 189 } 190 if (vs.size() >= 3) 191 polygonSoup.add(new Polygon(vs.toArray(new CoordDouble[0]))); 192 } 193 vs.clear(); 194 vs.add(tri.centroid); 195 next = triangleSoup.findNeighbor(tri, tri.b, tri.c); 196 if (next != null) { 197 n = next.getNonEdgeVertex(tri.b, tri.c); 198 while (next != tri) { 199 vs.add(next.centroid); 200 next = triangleSoup.findNeighbor(next, tri.b, n); 201 if (next == null) 202 break; 203 n = next.getNonEdgeVertex(tri.b, n); 204 } 205 if (vs.size() >= 3) 206 polygonSoup.add(new Polygon(vs.toArray(new CoordDouble[0]))); 207 } 208 vs.clear(); 209 vs.add(tri.centroid); 210 next = triangleSoup.findNeighbor(tri, tri.c, tri.a); 211 if (next != null) { 212 n = next.getNonEdgeVertex(tri.c, tri.a); 213 while (next != tri) { 214 vs.add(next.centroid); 215 next = triangleSoup.findNeighbor(next, tri.c, n); 216 if (next == null) 217 break; 218 n = next.getNonEdgeVertex(tri.c, n); 219 } 220 if (vs.size() >= 3) 221 polygonSoup.add(new Polygon(vs.toArray(new CoordDouble[0]))); 222 } 223 } 224 return polygonSoup; 225 } 226 227 /** 228 * This method legalizes edges by recursively flipping all illegal edges. 229 * 230 * @param triangle 231 * The triangle 232 * @param ea 233 * The "a" point on the edge to be legalized 234 * @param eb 235 * The "b" point on the edge to be legalized 236 * @param newVertex 237 * The new vertex 238 */ 239 private void legalizeEdge(Triangle triangle, CoordDouble ea, CoordDouble eb, CoordDouble newVertex) { 240 Triangle neighborTriangle = triangleSoup.findNeighbor(triangle, ea, eb); 241 242 /* 243 If the triangle has a neighbor, then legalize the edge 244 */ 245 if (neighborTriangle != null) { 246 if (neighborTriangle.isPointInCircumcircle(newVertex)) { 247 triangleSoup.remove(triangle); 248 triangleSoup.remove(neighborTriangle); 249 250 CoordDouble noneEdgeVertex = neighborTriangle.getNonEdgeVertex(ea, eb); 251 252 Triangle firstTriangle = new Triangle(noneEdgeVertex, ea, newVertex); 253 Triangle secondTriangle = new Triangle(noneEdgeVertex, eb, newVertex); 254 255 triangleSoup.add(firstTriangle); 256 triangleSoup.add(secondTriangle); 257 258 legalizeEdge(firstTriangle, noneEdgeVertex, ea, newVertex); 259 legalizeEdge(secondTriangle, noneEdgeVertex, eb, newVertex); 260 } 261 } 262 } 263 264 /** 265 * Creates a random permutation of the specified point set. Based on the 266 * implementation of the Delaunay algorithm, this can speed up the 267 * computation. 268 */ 269 public void shuffle(IRNG rng) { 270 pointSet.shuffle(rng); 271 } 272 273 /** 274 * Shuffles the point set using a custom permutation sequence. 275 * 276 * @param permutation 277 * The permutation used to shuffle the point set 278 */ 279 public void reorder(int[] permutation) { 280 pointSet.reorder(permutation); 281 } 282 283 /** 284 * Returns the point set in form of a vector of 2D vectors. 285 * 286 * @return Returns the points set. 287 */ 288 public OrderedSet<CoordDouble> getPointSet() { 289 return pointSet; 290 } 291 292 /** 293 * Returns the triangles of the triangulation in form of a list of 2D 294 * triangles. 295 * 296 * @return Returns the triangles of the triangulation. 297 */ 298 public ArrayList<Triangle> getTriangles() { 299 return triangleSoup.getTriangles(); 300 } 301 302 public static class Edge implements Serializable 303 { 304 private static final long serialVersionUID = 1L; 305 306 public CoordDouble a; 307 public CoordDouble b; 308 309 public Edge() 310 { 311 a = new CoordDouble(0.0, 0.0); 312 b = new CoordDouble(0.0, 1.0); 313 } 314 public Edge(CoordDouble a, CoordDouble b) 315 { 316 this.a = a; 317 this.b = b; 318 } 319 public Edge(double ax, double ay, double bx, double by) 320 { 321 a = new CoordDouble(ax, ay); 322 b = new CoordDouble(bx, by); 323 } 324 } 325 326 public static class Triangle implements Serializable 327 { 328 private static final long serialVersionUID = 1L; 329 330 public CoordDouble a; 331 public CoordDouble b; 332 public CoordDouble c; 333 public CoordDouble centroid; 334 335 /** 336 * Constructor of the 2D triangle class used to create a new triangle 337 * instance from three 2D vectors describing the triangle's vertices. 338 * 339 * @param a 340 * The first vertex of the triangle 341 * @param b 342 * The second vertex of the triangle 343 * @param c 344 * The third vertex of the triangle 345 */ 346 public Triangle(CoordDouble a, CoordDouble b, CoordDouble c) { 347 this.a = a; 348 this.b = b; 349 this.c = c; 350 centroid = new CoordDouble((a.x + b.x + c.x) / 3.0, (a.y + b.y + c.y) / 3.0); 351 } 352 353 /** 354 * Tests if a 2D point lies inside this 2D triangle. See Real-Time Collision 355 * Detection, chap. 5, p. 206. 356 * 357 * @param point 358 * The point to be tested 359 * @return Returns true iff the point lies inside this 2D triangle 360 */ 361 public boolean contains(CoordDouble point) { 362 double px = point.x - a.x; 363 double py = point.y - a.y; 364 double sx = b.x - a.x; 365 double sy = b.y - a.y; 366 double pab = py * sx - px * sy;//point.sub(a).cross(b.sub(a)); 367 px = point.x - b.x; 368 py = point.y - b.y; 369 sx = c.x - b.x; 370 sy = c.y - b.y; 371 double pbc = py * sx - px * sy;//point.sub(b).cross(c.sub(b)); 372 373 if (!hasSameSign(pab, pbc)) { 374 return false; 375 } 376 377 px = point.x - c.x; 378 py = point.y - c.y; 379 sx = a.x - c.x; 380 sy = a.y - c.y; 381 double pca = py * sx - px * sy;//point.sub(c).cross(a.sub(c)); 382 383 return hasSameSign(pab, pca); 384 385 } 386 387 /** 388 * Tests if a given point lies in the circumcircle of this triangle. Let the 389 * triangle ABC appear in counterclockwise (CCW) order. Then when det > 390 * 0, the point lies inside the circumcircle through the three points a, b 391 * and c. If instead det < 0, the point lies outside the circumcircle. 392 * When det = 0, the four points are cocircular. If the triangle is oriented 393 * clockwise (CW) the result is reversed. See Real-Time Collision Detection, 394 * chap. 3, p. 34. 395 * 396 * @param point 397 * The point to be tested 398 * @return Returns true iff the point lies inside the circumcircle through 399 * the three points a, b, and c of the triangle 400 */ 401 public boolean isPointInCircumcircle(CoordDouble point) { 402 double a11 = a.x - point.x; 403 double a21 = b.x - point.x; 404 double a31 = c.x - point.x; 405 406 double a12 = a.y - point.y; 407 double a22 = b.y - point.y; 408 double a32 = c.y - point.y; 409 410 double a13 = (a.x - point.x) * (a.x - point.x) + (a.y - point.y) * (a.y - point.y); 411 double a23 = (b.x - point.x) * (b.x - point.x) + (b.y - point.y) * (b.y - point.y); 412 double a33 = (c.x - point.x) * (c.x - point.x) + (c.y - point.y) * (c.y - point.y); 413 414 double det = a11 * a22 * a33 + a12 * a23 * a31 + a13 * a21 * a32 - a13 * a22 * a31 - a12 * a21 * a33 415 - a11 * a23 * a32; 416 417 if (isOrientedCCW()) { 418 return det > 0.0; 419 } 420 421 return det < 0.0; 422 } 423 424 /** 425 * Test if this triangle is oriented counterclockwise (CCW). Let A, B and C 426 * be three 2D points. If det > 0, C lies to the left of the directed 427 * line AB. Equivalently the triangle ABC is oriented counterclockwise. When 428 * det < 0, C lies to the right of the directed line AB, and the triangle 429 * ABC is oriented clockwise. When det = 0, the three points are colinear. 430 * See Real-Time Collision Detection, chap. 3, p. 32 431 * 432 * @return Returns true iff the triangle ABC is oriented counterclockwise 433 * (CCW) 434 */ 435 public boolean isOrientedCCW() { 436 double a11 = a.x - c.x; 437 double a21 = b.x - c.x; 438 439 double a12 = a.y - c.y; 440 double a22 = b.y - c.y; 441 442 double det = a11 * a22 - a12 * a21; 443 444 return det > 0.0; 445 } 446 447 /** 448 * Returns true if this triangle contains the given edge. 449 * 450 * @param edge 451 * The edge to be tested 452 * @return Returns true if this triangle contains the edge 453 */ 454 public boolean isNeighbor(Edge edge) { 455 return (a == edge.a || b == edge.a || c == edge.a) && (a == edge.b || b == edge.b || c == edge.b); 456 } 457 public boolean isNeighbor(CoordDouble ea, CoordDouble eb) { 458 return (a == ea || b == ea || c == ea) && (a == eb || b == eb || c == eb); 459 } 460 461 /** 462 * Returns the vertex of this triangle that is not part of the given edge. 463 * 464 * @param edge 465 * The edge 466 * @return The vertex of this triangle that is not part of the edge 467 */ 468 public CoordDouble getNonEdgeVertex(Edge edge) { 469 if (a != edge.a && a != edge.b) { 470 return a; 471 } else if (b != edge.a && b != edge.b) { 472 return b; 473 } else if (c != edge.a && c != edge.b) { 474 return c; 475 } 476 477 return null; 478 } 479 public CoordDouble getNonEdgeVertex(CoordDouble ea, CoordDouble eb) { 480 if (a != ea && a != eb) { 481 return a; 482 } else if (b != ea && b != eb) { 483 return b; 484 } else if (c != ea && c != eb) { 485 return c; 486 } 487 488 return null; 489 } 490 491 /** 492 * Returns true if the given vertex is one of the vertices describing this 493 * triangle. 494 * 495 * @param vertex 496 * The vertex to be tested 497 * @return Returns true if the Vertex is one of the vertices describing this 498 * triangle 499 */ 500 public boolean hasVertex(CoordDouble vertex) { 501 return a == vertex || b == vertex || c == vertex; 502 } 503 504 /** 505 * Computes the closest point on the given edge to the specified point. 506 * 507 * @param edge 508 * The edge on which we search the closest point to the specified 509 * point 510 * @param point 511 * The point to which we search the closest point on the edge 512 * @return The closest point on the given edge to the specified point 513 */ 514 CoordDouble computeClosestPoint(Edge edge, CoordDouble point) { 515 //CoordDouble ab = edge.b.sub(edge.a); 516 double abx = edge.b.x = edge.a.x; 517 double aby = edge.b.y = edge.a.y; 518 double t = ((point.x - edge.a.x) * abx + (point.y - edge.a.y) * aby) / (abx * abx + aby * aby); 519 //double t = point.sub(edge.a).dot(ab) / ab.dot(ab); 520 521 if (t < 0.0d) { 522 t = 0.0d; 523 } else if (t > 1.0d) { 524 t = 1.0d; 525 } 526 return new CoordDouble(edge.a.x + abx * t, edge.a.y + aby * t); 527// return edge.a.add(ab.mult(t)); 528 } 529 530 /** 531 * Tests if the two arguments have the same sign. 532 * 533 * @param a 534 * The first floating point argument 535 * @param b 536 * The second floating point argument 537 * @return Returns true iff both arguments have the same sign 538 */ 539 private boolean hasSameSign(double a, double b) { 540 return (a == 0.0 && b == 0.0) || ((a > 0.0) == (b > 0.0)); 541 } 542 543 @Override 544 public String toString() { 545 return "Triangle[" + a + ", " + b + ", " + c + "]"; 546 } 547 } 548 public static class Polygon implements Serializable { 549 private static final long serialVersionUID = 1L; 550 public CoordDouble centroid; 551 public final CoordDouble[] vertices; 552 553 public Polygon(CoordDouble... vertices) { 554 this.vertices = vertices == null || vertices.length < 3 555 ? new CoordDouble[] {new CoordDouble(), new CoordDouble(), new CoordDouble()} 556 : vertices; 557 this.centroid = new CoordDouble(this.vertices[0]); 558 for (int i = 1; i < this.vertices.length; i++) { 559 this.centroid.add(this.vertices[i]); 560 } 561 this.centroid.divide(this.vertices.length, this.vertices.length); 562 } 563 564 } 565 private static final Comparator<Double> doubleComparator = new Comparator<Double>() { 566 @Override 567 public int compare(Double o1, Double o2) { 568 return o1.compareTo(o2); 569 } 570 }; 571 572 /** 573 * Triangle soup class implementation. 574 * 575 * @author Johannes Diemke 576 */ 577 static class TriangleSoup { 578 579 ArrayList<Triangle> triangleSoup; 580 581 /** 582 * Constructor of the triangle soup class used to create a new triangle soup 583 * instance. 584 */ 585 public TriangleSoup() { 586 this.triangleSoup = new ArrayList<>(); 587 } 588 589 /** 590 * Adds a triangle to this triangle soup. 591 * 592 * @param triangle 593 * The triangle to be added to this triangle soup 594 */ 595 public void add(Triangle triangle) { 596 this.triangleSoup.add(triangle); 597 } 598 599 /** 600 * Removes a triangle from this triangle soup. 601 * 602 * @param triangle 603 * The triangle to be removed from this triangle soup 604 */ 605 public void remove(Triangle triangle) { 606 this.triangleSoup.remove(triangle); 607 } 608 609 /** 610 * Returns the triangles from this triangle soup. 611 * 612 * @return The triangles from this triangle soup 613 */ 614 public ArrayList<Triangle> getTriangles() { 615 return this.triangleSoup; 616 } 617 618 /** 619 * Returns the triangle from this triangle soup that contains the specified 620 * point or null if no triangle from the triangle soup contains the point. 621 * 622 * @param point 623 * The point 624 * @return Returns the triangle from this triangle soup that contains the 625 * specified point or null 626 */ 627 public Triangle findContainingTriangle(CoordDouble point) { 628 for (Triangle triangle : triangleSoup) { 629 if (triangle.contains(point)) { 630 return triangle; 631 } 632 } 633 return null; 634 } 635 636 /** 637 * Returns the neighbor triangle of the specified triangle sharing the same 638 * edge as specified. If no neighbor sharing the same edge exists null is 639 * returned. 640 * 641 * @param triangle 642 * The triangle 643 * @param edge 644 * The edge 645 * @return The triangle's neighbor triangle sharing the same edge or null if 646 * no triangle exists 647 */ 648 public Triangle findNeighbor(Triangle triangle, Edge edge) { 649 for (Triangle triangleFromSoup : triangleSoup) { 650 if (triangleFromSoup.isNeighbor(edge) && triangleFromSoup != triangle) { 651 return triangleFromSoup; 652 } 653 } 654 return null; 655 } 656 public Triangle findNeighbor(Triangle triangle, CoordDouble ea, CoordDouble eb) { 657 for (Triangle triangleFromSoup : triangleSoup) { 658 if (triangleFromSoup.isNeighbor(ea, eb) && triangleFromSoup != triangle) { 659 return triangleFromSoup; 660 } 661 } 662 return null; 663 } 664 665 /** 666 * Returns one of the possible triangles sharing the specified edge. Based 667 * on the ordering of the triangles in this triangle soup the returned 668 * triangle may differ. To find the other triangle that shares this edge use 669 * the {@link #findNeighbor(Triangle, Edge)} method. 670 * 671 * @param edge 672 * The edge 673 * @return Returns one triangle that shares the specified edge 674 */ 675 public Triangle findOneTriangleSharing(Edge edge) { 676 for (Triangle triangle : triangleSoup) { 677 if (triangle.isNeighbor(edge)) { 678 return triangle; 679 } 680 } 681 return null; 682 } 683 684 /** 685 * Returns the edge from the triangle soup nearest to the specified point. 686 * 687 * @param point 688 * The point 689 * @return The edge from the triangle soup nearest to the specified point 690 */ 691 public Edge findNearestEdge(CoordDouble point) { 692// List<EdgeDistancePack> edgeList = new ArrayList<EdgeDistancePack>(); 693 694 OrderedMap<Edge, Double> edges = new OrderedMap<>(triangleSoup.size()); 695 for (Triangle triangle : triangleSoup) { 696 Edge ab = new Edge(triangle.a, triangle.b); 697 Edge bc = new Edge(triangle.b, triangle.c); 698 Edge ca = new Edge(triangle.c, triangle.a); 699 double abd = triangle.computeClosestPoint(ab, point).subtract(point).lengthSq(); 700 double bcd = triangle.computeClosestPoint(bc, point).subtract(point).lengthSq(); 701 double cad = triangle.computeClosestPoint(ca, point).subtract(point).lengthSq(); 702 703 if(abd <= bcd && abd <= cad) 704 edges.put(ab, abd); 705 else if(bcd <= abd && bcd <= cad) 706 edges.put(bc, bcd); 707 else 708 edges.put(ca, cad); 709 } 710 edges.sortByValue(doubleComparator); 711 return edges.keyAt(0); 712 } 713 714 /** 715 * Removes all triangles from this triangle soup that contain the specified 716 * vertex. 717 * 718 * @param vertex 719 * The vertex 720 */ 721 public void removeTrianglesUsing(CoordDouble vertex) { 722 ListIterator<Triangle> li = triangleSoup.listIterator(); 723 while (li.hasNext()) 724 { 725 Triangle triangle = li.next(); 726 if(triangle.hasVertex(vertex)) 727 li.remove(); 728 } 729 } 730 731 } 732}