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 ******************************************************************************/
009package imagingbook.common.geometry.delaunay;
010
011import imagingbook.common.geometry.basic.Pnt2d;
012import imagingbook.common.geometry.delaunay.guibas.TriangulationGuibas;
013
014import java.util.Collection;
015import java.util.List;
016
017/**
018 * <p>
019 * Interface specification for implementations of Delaunay triangulations. See {@link TriangulationGuibas} for a
020 * concrete implementation.
021 * </p>
022 *
023 * @author WB
024 * @see TriangulationGuibas
025 */
026public interface DelaunayTriangulation {
027        
028        /**
029         * Returns the number of triangles in this triangulation.
030         * @return the number of triangles
031         */
032        public int size();
033
034        /**
035         * Returns a list of {@link Triangle} instances contained in this triangulation. The list does not contain the
036         * initial outer triangle.
037         *
038         * @return a list of triangles
039         */
040        public List<Triangle> getTriangles();
041
042        /**
043         * Returns a list of 2D vertices contained in this triangulation. The list does not contain the vertices of the
044         * initial (outer) triangle.
045         *
046         * @return a list of points
047         */
048        public List<Pnt2d> getPoints();
049        
050        // utility methods: ----------------------------------------
051
052        /**
053         * Creates a 2D triangle that is sufficiently large to be used as an outer triangle for the Delaunay triangulation
054         * of the given point set.
055         *
056         * @param points the 2D point set
057         * @return a triangle as an array of 3 points
058         */
059        public static Pnt2d[] makeOuterTriangle(Collection<? extends Pnt2d> points) {
060                double xmin = Double.POSITIVE_INFINITY;
061                double xmax = Double.NEGATIVE_INFINITY;
062                double ymin = xmin;
063                double ymax = xmax;
064                
065                for (Pnt2d p : points) {
066                        double x = p.getX();
067                        double y = p.getY();
068                        xmin = Math.min(x, xmin);
069                        xmax = Math.max(x, xmax);
070                        ymin = Math.min(y, ymin);
071                        ymax = Math.max(y, ymax);
072                }
073                return makeOuterTriangle(xmin, xmax, ymin, ymax);
074        }
075
076        /**
077         * Creates a 2D triangle that is sufficiently large to be used as an outer triangle for the Delaunay triangulation
078         * of points inside the given bounding rectangle.
079         *
080         * @param xmin minimum x-coordinate of the bounding rectangle
081         * @param xmax maximum x-coordinate of the bounding rectangle
082         * @param ymin minimum y-coordinate of the bounding rectangle
083         * @param ymax maximum y-coordinate of the bounding rectangle
084         * @return a triangle as an array of 3 points
085         */
086        public static Pnt2d[] makeOuterTriangle(double xmin, double xmax, double ymin, double ymax) {
087                double width = xmax - xmin;
088                double height = ymax - ymin;
089                double diam = Math.max(width,  height);
090                double xc = xmin + width / 2;
091                double yc = ymin + height / 2;
092                double s = 50;
093                return new Pnt2d[] {
094                                Pnt2d.PntDouble.from(xc, yc + s * diam),
095                                Pnt2d.PntDouble.from(xc + s * diam, yc),
096                                Pnt2d.PntDouble.from(xc - s * diam, yc - s * diam)
097                };
098        }
099
100        /**
101         * Creates a 2D triangle that is sufficiently large to be used as an outer triangle for the Delaunay triangulation
102         * of points inside the given bounding rectangle, anchored at (0,0).
103         *
104         * @param width the width of the bounding rectangle
105         * @param height the height of the bounding rectangle
106         * @return a triangle as an array of 3 points
107         */
108        public static Pnt2d[] makeOuterTriangle(double width, double height) {
109                return makeOuterTriangle(0, width, 0, height);
110        }
111
112        /**
113         * Performs Delaunay triangulation on the specified points. Supplied points are inserted without shuffling, i.e., in
114         * their original order.
115         *
116         * @param points the point set to be triangulated
117         * @return a {@link DelaunayTriangulation} instance
118         */
119        public static DelaunayTriangulation from(Collection<? extends Pnt2d> points) {
120                return DelaunayTriangulation.from(points, false);
121        }
122        
123        // static construction methods: -----------------------------------
124
125        /**
126         * Performs Delaunay triangulation on the specified points with (optional) random insertion order.
127         *
128         * @param points the point set to be triangulated
129         * @param shuffle set {@code true} to randomly shuffle the input points
130         * @return a {@link DelaunayTriangulation} instance
131         */
132        public static DelaunayTriangulation from(Collection<? extends Pnt2d> points, boolean shuffle) {
133                return new TriangulationGuibas(points, shuffle);
134        }
135
136}