001/*******************************************************************************
002 * This software is provided as a supplement to the authors' textbooks on digital
003 * image processing published by Springer-Verlag in various languages and editions.
004 * Permission to use and distribute this software is granted under the BSD 2-Clause
005 * "Simplified" License (see http://opensource.org/licenses/BSD-2-Clause).
006 * Copyright (c) 2006-2023 Wilhelm Burger, Mark J. Burge. All rights reserved.
007 * Visit https://imagingbook.com for additional details.
008 ******************************************************************************/
009
010package imagingbook.common.geometry.delaunay.guibas;
011
012import imagingbook.common.geometry.basic.Pnt2d;
013import imagingbook.common.geometry.delaunay.DelaunayTriangulation;
014import imagingbook.common.geometry.delaunay.Triangle;
015
016import java.util.ArrayList;
017import java.util.Collection;
018import java.util.Collections;
019import java.util.LinkedList;
020import java.util.List;
021
022/**
023 * <p>
024 * This is an implementation of the triangulation algorithm described in [1].
025 * </p>
026 * <p>
027 * [1] L. J. Guibas, D. E. Knuth, and M. Sharir" "Randomized incremental construction of Delaunay and Voronoi diagrams",
028 * Algorithmica, 7, pp. 381--413 (1992).
029 * </p>
030 *
031 * @author WB
032 */
033public class TriangulationGuibas implements DelaunayTriangulation {
034
035        private final List<Pnt2d> points;
036        private final List<Triangle2D> triangles;
037        private final Triangle2D outerTriangle;
038
039        /**
040         * Constructor. 
041         * @param points the point set to be triangulated
042         * @param shuffle set {@code true} to randomly shuffle the input points
043         */
044        public TriangulationGuibas(Collection<? extends Pnt2d> points, boolean shuffle) {
045                // TODO: change to point array or iterable!
046                if (points == null || points.size() < 3) {
047                        throw new IllegalArgumentException("Point set must contain at least 3 points.");
048                }
049                this.points = new ArrayList<Pnt2d>(points);
050                if (shuffle) {
051                        Collections.shuffle(this.points);
052                }
053                this.outerTriangle = new Triangle2D(DelaunayTriangulation.makeOuterTriangle(points));
054                this.triangles = new ArrayList<>();
055                triangulate();
056        }
057
058        /**
059         * Constructor. Supplied points are inserted without shuffling, i.e., in their original order.
060         *
061         * @param points the point set to be triangulated
062         */
063        public TriangulationGuibas(Collection<? extends Pnt2d> points) {
064                this(points, false);
065        }
066        
067        // -----------------------------------------------------------------------------
068        
069        @Override
070        public int size() {
071                return triangles.size();
072        }
073        
074        @Override
075        public List<Triangle> getTriangles() {
076                return Collections.unmodifiableList(triangles);
077        }
078        
079        @Override
080        public List<Pnt2d> getPoints() {
081                return points;
082        }
083        
084        // -----------------------------------------------------------------------------
085
086        private void triangulate() {
087                triangles.add(outerTriangle);
088                
089                for (Pnt2d pnt : points) {
090                        Triangle2D triangle = this.findContainingTriangle(pnt);
091
092                        if (triangle == null) { // pnt is outside of any triangle
093                                /* If no containing triangle exists, then the vertex is not inside a triangle
094                                 * (this can also happen due to numerical errors) and lies on an edge. In order
095                                 * to find this edge we search all edges of the triangle soup and select the one
096                                 * which is nearest to the point we try to add. This edge is removed and four
097                                 * new edges are added.
098                                 */
099                                Edge2D edge = this.findNearestEdge(pnt);
100
101                                Triangle2D tr1 = this.findOneTriangleSharing(edge);
102                                Triangle2D tr2 = this.findNeighbour(tr1, edge);
103
104                                Pnt2d noneEdgeVertex1 = tr1.getOppositeVertex(edge);
105                                Pnt2d noneEdgeVertex2 = tr2.getOppositeVertex(edge);
106
107                                triangles.remove(tr1);
108                                triangles.remove(tr2);
109
110                                Triangle2D triangle1 = new Triangle2D(edge.a, noneEdgeVertex1, pnt);
111                                Triangle2D triangle2 = new Triangle2D(edge.b, noneEdgeVertex1, pnt);
112                                Triangle2D triangle3 = new Triangle2D(edge.a, noneEdgeVertex2, pnt);
113                                Triangle2D triangle4 = new Triangle2D(edge.b, noneEdgeVertex2, pnt);
114
115                                triangles.add(triangle1);
116                                triangles.add(triangle2);
117                                triangles.add(triangle3);
118                                triangles.add(triangle4);
119
120
121                                legalizeEdge(triangle1, new Edge2D(edge.a, noneEdgeVertex1), pnt);
122                                legalizeEdge(triangle2, new Edge2D(edge.b, noneEdgeVertex1), pnt);
123                                legalizeEdge(triangle3, new Edge2D(edge.a, noneEdgeVertex2), pnt);
124                                legalizeEdge(triangle4, new Edge2D(edge.b, noneEdgeVertex2), pnt);
125                        } 
126                        else { // pnt is inside the triangle <a,b,c>.
127                                Pnt2d a = triangle.a;
128                                Pnt2d b = triangle.b;
129                                Pnt2d c = triangle.c;
130
131                                triangles.remove(triangle);
132
133                                Triangle2D triangle1 = new Triangle2D(a, b, pnt);
134                                Triangle2D triangle2 = new Triangle2D(b, c, pnt);
135                                Triangle2D triangle3 = new Triangle2D(c, a, pnt);
136
137                                triangles.add(triangle1);
138                                triangles.add(triangle2);
139                                triangles.add(triangle3);
140
141                                legalizeEdge(triangle1, new Edge2D(a, b), pnt);
142                                legalizeEdge(triangle2, new Edge2D(b, c), pnt);
143                                legalizeEdge(triangle3, new Edge2D(c, a), pnt);
144                        }
145                }
146
147                // Remove all triangles containing any vertex of the super triangle:
148                this.removeTrianglesUsing(outerTriangle.a);
149                this.removeTrianglesUsing(outerTriangle.b);
150                this.removeTrianglesUsing(outerTriangle.c);
151        }
152
153        /**
154         * This method legalizes edges by recursively flipping all illegal edges.
155         * 
156         * @param triangle  the triangle
157         * @param edge      the edge to be legalized
158         * @param newVertex the new vertex
159         */
160        private void legalizeEdge(Triangle2D triangle, Edge2D edge, Pnt2d newVertex) {
161                Triangle2D neighbourTriangle = this.findNeighbour(triangle, edge);
162                // If the triangle has a neighbor, then legalize the edge
163                if (neighbourTriangle != null) {
164                        if (neighbourTriangle.isPointInCircumCircle(newVertex)) {
165                                triangles.remove(triangle);
166                                triangles.remove(neighbourTriangle);
167
168                                Pnt2d noneEdgeVertex = neighbourTriangle.getOppositeVertex(edge);
169
170                                Triangle2D triangle1 = new Triangle2D(noneEdgeVertex, edge.a, newVertex);
171                                Triangle2D triangle2 = new Triangle2D(noneEdgeVertex, edge.b, newVertex);
172
173                                triangles.add(triangle1);
174                                triangles.add(triangle2);
175
176                                legalizeEdge(triangle1, new Edge2D(noneEdgeVertex, edge.a), newVertex);
177                                legalizeEdge(triangle2, new Edge2D(noneEdgeVertex, edge.b), newVertex);
178                        }
179                }
180        }
181        
182        // triangle-related methods ---------------------------
183
184        /**
185         * Returns the triangle that contains the specified point or null if no such triangle exists.
186         *
187         * @param point the query point
188         * @return the containing triangle or {@code null} if none was found
189         */
190        public Triangle2D findContainingTriangle(Pnt2d point) {
191                for (Triangle2D triangle : triangles) {
192                        if (triangle.containsPoint(point)) {
193                                return triangle;
194                        }
195                }
196                return null;
197        }
198
199        /**
200         * Returns the neighboring triangle of the specified triangle sharing the same edge as specified. If no neighbor
201         * sharing the same edge exists {@code null} is returned. NOTE: Searching over ALL triangles seems to be
202         * unnecessarily expensive!
203         *
204         * @param tri1 the triangle
205         * @param edge the edge
206         * @return the triangle's neighboring triangle sharing the same edge or {@code null} if no such triangle exists
207         */
208        public Triangle2D findNeighbour(Triangle2D tri1, Edge2D edge) {
209                for (Triangle2D tri2 : triangles) {
210                        if (tri2.containsEdge(edge) && tri2 != tri1) {
211                                return tri2;
212                        }
213                }
214                return null;
215        }
216
217        /**
218         * Returns one of the possible triangles sharing the specified edge. Based on the ordering of the triangles in this
219         * triangle soup the returned triangle may differ. To find the other triangle that shares this edge use the
220         * {@code findNeighbour(Triangle2D triangle, Edge2D edge)} method.
221         *
222         * @param edge the edge
223         * @return the triangle that shares the specified edge or {@code null} if none exists
224         */
225        public Triangle2D findOneTriangleSharing(Edge2D edge) {
226                for (Triangle2D triangle : triangles) {
227                        if (triangle.containsEdge(edge)) {
228                                return triangle;
229                        }
230                }
231                return null;
232        }
233        
234        /**
235         * Returns the triangle edge nearest to the specified point.
236         * 
237         * @param point the query point
238         * @return the triangle edge nearest to the specified point
239         */
240        public Edge2D findNearestEdge(Pnt2d point) {
241                Edge2D minEdge = null;
242                double minDist = Double.POSITIVE_INFINITY;
243                for (Triangle2D tri : triangles) {
244                        Edge2D.Distance ed = tri.findMinEdgeDistance(point);
245                        double dist = ed.getDistance();
246                        if (dist < minDist) {
247                                minDist = dist;
248                                minEdge = ed.getEdge();
249                        }
250                }
251                return minEdge;
252        }
253
254        /**
255         * Removes all triangles that contain the specified corner point.
256         * @param point the corner point
257         */
258        public void removeTrianglesUsing(Pnt2d point) {
259                List<Triangle2D> trianglesToBeRemoved = new LinkedList<>();
260                for (Triangle2D triangle : triangles) {
261                        if (triangle.hasVertex(point)) {
262                                trianglesToBeRemoved.add(triangle);
263                        }
264                }
265                triangles.removeAll(trianglesToBeRemoved);
266        }
267}