DelaunayTriangulator { public static List<Triangle> triangulate( List<? extends Point2d> pxyz ) { Collections.sort(pxyz, new XComparator()); float xmin = ((Point2d)pxyz.get(0)).getX(); float ymin = ((Point2d)pxyz.get(0)).getY(); float xmax = xmin; float ymax = ymin; for (Point2d p : pxyz) { if (p.getX() < xmin) xmin = p.getX(); if (p.getX() > xmax) xmax = p.getX(); if (p.getY() < ymin) ymin = p.getY(); if (p.getY() > ymax) ymax = p.getY(); } float dx = xmax - xmin; float dy = ymax - ymin; float dmax = (dx > dy) ? dx : dy; float xmid = (xmax + xmin) / 2.0f; float ymid = (ymax + ymin) / 2.0f; ArrayList<Triangle> triangles = new ArrayList<Triangle>(); HashSet<Triangle> complete = new HashSet<Triangle>(); Triangle superTriangle = new Triangle( new Point2dImpl( xmid - 2.0f * dmax, ymid - dmax ), new Point2dImpl( xmid, ymid + 2.0f * dmax ), new Point2dImpl( xmid + 2.0f * dmax, ymid - dmax ) ); triangles.add(superTriangle); ArrayList<Line2d> edges = new ArrayList<Line2d>(); for (Point2d p : pxyz) { edges.clear(); Circle circle = new Circle(0,0,0); for (int j = triangles.size()-1; j >= 0; j--) { Triangle t = (Triangle)triangles.get(j); if (complete.contains(t)) { continue; } boolean inside = circumCircle( p, t, circle ); if (circle.getX() + circle.getRadius() < p.getX()) { complete.add(t); } if (inside) { edges.add(new Line2d(t.firstVertex(), t.secondVertex())); edges.add(new Line2d(t.secondVertex(), t.thirdVertex())); edges.add(new Line2d(t.thirdVertex(), t.firstVertex())); triangles.remove(j); } } for (int j=0; j<edges.size()-1; j++) { Line2d e1 = edges.get(j); for (int k=j+1; k<edges.size(); k++) { Line2d e2 = edges.get(k); if (e1.begin == e2.end && e1.end == e2.begin) { e1.begin = null; e1.end = null; e2.begin = null; e2.end = null; } if (e1.begin == e2.begin && e1.end == e2.end) { e1.begin = null; e1.end = null; e2.begin = null; e2.end = null; } } } for (int j=0; j < edges.size(); j++) { Line2d e = edges.get(j); if (e.begin == null || e.end == null) { continue; } triangles.add(new Triangle(e.begin, e.end, p)); } } for (int i = triangles.size()-1; i >= 0; i--) { Triangle t = (Triangle)triangles.get(i); if (t.sharesVertex(superTriangle)) { triangles.remove(i); } } return triangles; }  static List<Triangle> triangulate( List<? extends Point2d> pxyz );  }
@Test public void testDelaunaySimple() { Polygon p = new Rectangle( 100f, 100f, 100f, 100f ).asPolygon(); List<Triangle> tris = DelaunayTriangulator.triangulate( p.points ); Assert.assertEquals( 2, tris.size() ); }