@Test public void testBuildDelaunayTriangle() { List<DelaunayTriangle> triangles = new ArrayList<>(); triangles.add(new DelaunayTriangle(new Vector3(250, -5000), new Vector3(-5000, 400), new Vector3(5000, 400))); List<Vector3> vectors = new ArrayList<>(); for (int i = 0; i < 10; i++) { vectors.add(new Vector3(MathUtil.random(500), MathUtil.random(400))); } vectors.sort((o1, o2) -> { if (o1.x > o2.x) { return 1; } else if (o1.x < o2.x) { return -1; } return 0; }); DelaunayTriangle.buildDelaunayTriangle(triangles, vectors); vectors.forEach(v->System.err.println(v.toString())); triangles.forEach(triangle -> System.out.println(triangle.toString())); }
public static List<DelaunayTriangle> buildDelaunayTriangle(List<DelaunayTriangle> triangles, List<Vector3> vector3s) { for (int i = 0; i < vector3s.size(); i++) { Vector3 vector3 = vector3s.get(i); List<DelaunayTriangle> tempTriangles = new ArrayList<>(); tempTriangles.addAll(triangles); List<DelaunayTriangle> influenedTriangles = new ArrayList<DelaunayTriangle>(); List<DelaunayTriangle> newTriangles = new ArrayList<DelaunayTriangle>(); List<TriangleEdge> commonEdges = new ArrayList<TriangleEdge>(); for (int j = 0; j < tempTriangles.size(); j++) { DelaunayTriangle tempTriangle = tempTriangles.get(j); double lengthToCenter = Vector3.dst(tempTriangle.center, vector3); if (lengthToCenter < tempTriangle.radius) { influenedTriangles.add(tempTriangle); triangles.remove(tempTriangle); } } for (int k = 0; k < influenedTriangles.size(); k++) { DelaunayTriangle delaunayTriangle = influenedTriangles.get(k); newTriangles.add(new DelaunayTriangle(delaunayTriangle.a, delaunayTriangle.b, vector3)); newTriangles.add(new DelaunayTriangle(delaunayTriangle.a, delaunayTriangle.c, vector3)); newTriangles.add(new DelaunayTriangle(delaunayTriangle.b, delaunayTriangle.c, vector3)); } if (influenedTriangles.size() > 1) { commonEdges = findCommonEdges(influenedTriangles); } if (commonEdges.size() > 0) { remmoveTrianglesByEdges(newTriangles, commonEdges); } LOP(newTriangles); triangles.addAll(newTriangles); } return triangles; }
DelaunayTriangle extends Triangle { public static List<DelaunayTriangle> buildDelaunayTriangle(List<DelaunayTriangle> triangles, List<Vector3> vector3s) { for (int i = 0; i < vector3s.size(); i++) { Vector3 vector3 = vector3s.get(i); List<DelaunayTriangle> tempTriangles = new ArrayList<>(); tempTriangles.addAll(triangles); List<DelaunayTriangle> influenedTriangles = new ArrayList<DelaunayTriangle>(); List<DelaunayTriangle> newTriangles = new ArrayList<DelaunayTriangle>(); List<TriangleEdge> commonEdges = new ArrayList<TriangleEdge>(); for (int j = 0; j < tempTriangles.size(); j++) { DelaunayTriangle tempTriangle = tempTriangles.get(j); double lengthToCenter = Vector3.dst(tempTriangle.center, vector3); if (lengthToCenter < tempTriangle.radius) { influenedTriangles.add(tempTriangle); triangles.remove(tempTriangle); } } for (int k = 0; k < influenedTriangles.size(); k++) { DelaunayTriangle delaunayTriangle = influenedTriangles.get(k); newTriangles.add(new DelaunayTriangle(delaunayTriangle.a, delaunayTriangle.b, vector3)); newTriangles.add(new DelaunayTriangle(delaunayTriangle.a, delaunayTriangle.c, vector3)); newTriangles.add(new DelaunayTriangle(delaunayTriangle.b, delaunayTriangle.c, vector3)); } if (influenedTriangles.size() > 1) { commonEdges = findCommonEdges(influenedTriangles); } if (commonEdges.size() > 0) { remmoveTrianglesByEdges(newTriangles, commonEdges); } LOP(newTriangles); triangles.addAll(newTriangles); } return triangles; } }
DelaunayTriangle extends Triangle { public static List<DelaunayTriangle> buildDelaunayTriangle(List<DelaunayTriangle> triangles, List<Vector3> vector3s) { for (int i = 0; i < vector3s.size(); i++) { Vector3 vector3 = vector3s.get(i); List<DelaunayTriangle> tempTriangles = new ArrayList<>(); tempTriangles.addAll(triangles); List<DelaunayTriangle> influenedTriangles = new ArrayList<DelaunayTriangle>(); List<DelaunayTriangle> newTriangles = new ArrayList<DelaunayTriangle>(); List<TriangleEdge> commonEdges = new ArrayList<TriangleEdge>(); for (int j = 0; j < tempTriangles.size(); j++) { DelaunayTriangle tempTriangle = tempTriangles.get(j); double lengthToCenter = Vector3.dst(tempTriangle.center, vector3); if (lengthToCenter < tempTriangle.radius) { influenedTriangles.add(tempTriangle); triangles.remove(tempTriangle); } } for (int k = 0; k < influenedTriangles.size(); k++) { DelaunayTriangle delaunayTriangle = influenedTriangles.get(k); newTriangles.add(new DelaunayTriangle(delaunayTriangle.a, delaunayTriangle.b, vector3)); newTriangles.add(new DelaunayTriangle(delaunayTriangle.a, delaunayTriangle.c, vector3)); newTriangles.add(new DelaunayTriangle(delaunayTriangle.b, delaunayTriangle.c, vector3)); } if (influenedTriangles.size() > 1) { commonEdges = findCommonEdges(influenedTriangles); } if (commonEdges.size() > 0) { remmoveTrianglesByEdges(newTriangles, commonEdges); } LOP(newTriangles); triangles.addAll(newTriangles); } return triangles; } DelaunayTriangle(Vector3 a, Vector3 b, Vector3 c); }
DelaunayTriangle extends Triangle { public static List<DelaunayTriangle> buildDelaunayTriangle(List<DelaunayTriangle> triangles, List<Vector3> vector3s) { for (int i = 0; i < vector3s.size(); i++) { Vector3 vector3 = vector3s.get(i); List<DelaunayTriangle> tempTriangles = new ArrayList<>(); tempTriangles.addAll(triangles); List<DelaunayTriangle> influenedTriangles = new ArrayList<DelaunayTriangle>(); List<DelaunayTriangle> newTriangles = new ArrayList<DelaunayTriangle>(); List<TriangleEdge> commonEdges = new ArrayList<TriangleEdge>(); for (int j = 0; j < tempTriangles.size(); j++) { DelaunayTriangle tempTriangle = tempTriangles.get(j); double lengthToCenter = Vector3.dst(tempTriangle.center, vector3); if (lengthToCenter < tempTriangle.radius) { influenedTriangles.add(tempTriangle); triangles.remove(tempTriangle); } } for (int k = 0; k < influenedTriangles.size(); k++) { DelaunayTriangle delaunayTriangle = influenedTriangles.get(k); newTriangles.add(new DelaunayTriangle(delaunayTriangle.a, delaunayTriangle.b, vector3)); newTriangles.add(new DelaunayTriangle(delaunayTriangle.a, delaunayTriangle.c, vector3)); newTriangles.add(new DelaunayTriangle(delaunayTriangle.b, delaunayTriangle.c, vector3)); } if (influenedTriangles.size() > 1) { commonEdges = findCommonEdges(influenedTriangles); } if (commonEdges.size() > 0) { remmoveTrianglesByEdges(newTriangles, commonEdges); } LOP(newTriangles); triangles.addAll(newTriangles); } return triangles; } DelaunayTriangle(Vector3 a, Vector3 b, Vector3 c); static List<DelaunayTriangle> buildDelaunayTriangle(List<DelaunayTriangle> triangles,
			List<Vector3> vector3s); static List<DelaunayTriangle> LOP(List<DelaunayTriangle> newTriList); static boolean isEdgeOnTriangle(DelaunayTriangle triangle, TriangleEdge edge); static List<TriangleEdge> findCommonEdges(List<DelaunayTriangle> influenedTriangles); static TriangleEdge findCommonEdge(DelaunayTriangle triangle1, DelaunayTriangle triangle2); static boolean isInCircle(DelaunayTriangle triangle, Vector3 vector3); Set<TriangleEdge> getEdgesOfTriangles(List<DelaunayTriangle> triangles); }
DelaunayTriangle extends Triangle { public static List<DelaunayTriangle> buildDelaunayTriangle(List<DelaunayTriangle> triangles, List<Vector3> vector3s) { for (int i = 0; i < vector3s.size(); i++) { Vector3 vector3 = vector3s.get(i); List<DelaunayTriangle> tempTriangles = new ArrayList<>(); tempTriangles.addAll(triangles); List<DelaunayTriangle> influenedTriangles = new ArrayList<DelaunayTriangle>(); List<DelaunayTriangle> newTriangles = new ArrayList<DelaunayTriangle>(); List<TriangleEdge> commonEdges = new ArrayList<TriangleEdge>(); for (int j = 0; j < tempTriangles.size(); j++) { DelaunayTriangle tempTriangle = tempTriangles.get(j); double lengthToCenter = Vector3.dst(tempTriangle.center, vector3); if (lengthToCenter < tempTriangle.radius) { influenedTriangles.add(tempTriangle); triangles.remove(tempTriangle); } } for (int k = 0; k < influenedTriangles.size(); k++) { DelaunayTriangle delaunayTriangle = influenedTriangles.get(k); newTriangles.add(new DelaunayTriangle(delaunayTriangle.a, delaunayTriangle.b, vector3)); newTriangles.add(new DelaunayTriangle(delaunayTriangle.a, delaunayTriangle.c, vector3)); newTriangles.add(new DelaunayTriangle(delaunayTriangle.b, delaunayTriangle.c, vector3)); } if (influenedTriangles.size() > 1) { commonEdges = findCommonEdges(influenedTriangles); } if (commonEdges.size() > 0) { remmoveTrianglesByEdges(newTriangles, commonEdges); } LOP(newTriangles); triangles.addAll(newTriangles); } return triangles; } DelaunayTriangle(Vector3 a, Vector3 b, Vector3 c); static List<DelaunayTriangle> buildDelaunayTriangle(List<DelaunayTriangle> triangles,
			List<Vector3> vector3s); static List<DelaunayTriangle> LOP(List<DelaunayTriangle> newTriList); static boolean isEdgeOnTriangle(DelaunayTriangle triangle, TriangleEdge edge); static List<TriangleEdge> findCommonEdges(List<DelaunayTriangle> influenedTriangles); static TriangleEdge findCommonEdge(DelaunayTriangle triangle1, DelaunayTriangle triangle2); static boolean isInCircle(DelaunayTriangle triangle, Vector3 vector3); Set<TriangleEdge> getEdgesOfTriangles(List<DelaunayTriangle> triangles); public float radius; public List<DelaunayTriangle> neighborTriangles; }