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.hulls;
010
011import imagingbook.common.geometry.basic.Pnt2d;
012import imagingbook.common.geometry.basic.Pnt2d.PntDouble;
013import imagingbook.common.geometry.line.AlgebraicLine;
014import imagingbook.common.geometry.shape.ShapeProducer;
015import org.apache.commons.math3.geometry.euclidean.twod.Vector2D;
016import org.apache.commons.math3.geometry.euclidean.twod.hull.ConvexHull2D;
017import org.apache.commons.math3.geometry.euclidean.twod.hull.MonotoneChain;
018
019import java.awt.Shape;
020import java.awt.geom.Path2D;
021import java.util.ArrayList;
022import java.util.Arrays;
023import java.util.List;
024
025/**
026 * <p>
027 * This class calculate the convex hull of a 2D point set. It is based on the convex hull implementation provided by the
028 * Apache Commons Math library, in particular classes {@link ConvexHull2D} and {@link MonotoneChain} [1]. See Sec. 8.4.2
029 * of [2] for additional details.
030 * </p>
031 * <p>
032 * [1] <a href="https://commons.apache.org/proper/commons-math/index.html">
033 * https://commons.apache.org/proper/commons-math/index.html</a> <br> [2] W. Burger, M.J. Burge, <em>Digital Image
034 * Processing &ndash; An Algorithmic Introduction</em>, 3rd ed, Springer (2022).
035 * </p>
036 *
037 * @author WB
038 * @version 2022/06/24
039 */
040public class ConvexHull implements ShapeProducer {
041        
042        private final ConvexHull2D hull;
043        private final Pnt2d[] vertices;
044
045        /**
046         * Constructor, creates a {@link ConvexHull} instance from an {@link Iterable} over {@link Pnt2d}. At least one
047         * distinct point is required.
048         *
049         * @param points an iterator over 2D points
050         */
051        public ConvexHull(Iterable<Pnt2d> points) {
052                if (!points.iterator().hasNext()) {
053                        throw new IllegalArgumentException("empty point sequence, at least one input point required");
054                }
055                List<Vector2D> pts = toVector2D(points);
056                this.hull = new MonotoneChain().generate(pts);
057                Vector2D[] vecs = hull.getVertices();
058                this.vertices = new Pnt2d[vecs.length];
059                for (int i = 0; i < vecs.length; i++) {
060                        vertices[i] = PntDouble.from(vecs[i]);
061                }
062        }
063
064        /**
065         * Constructor, creates a {@link AxisAlignedBoundingBox} instance from an array of {@link Pnt2d} points. At least
066         * one distinct point is required.
067         *
068         * @param points an array of 2D points
069         */
070        public ConvexHull(Pnt2d[] points) {
071                this(() -> Arrays.stream(points).iterator());
072        }
073        
074        private static List<Vector2D> toVector2D(Iterable<Pnt2d> points) {
075                List<Vector2D> vecs = new ArrayList<Vector2D>();
076                for (Pnt2d p : points) {
077                        vecs.add(new Vector2D(p.getX(), p.getY()));
078                }
079                return vecs;
080        }
081
082        /**
083         * Returns a sequence of 2D points on the convex hull (in counter-clockwise order).
084         *
085         * @return sequence of 2D points on the convex hull
086         */
087        public Pnt2d[] getVertices() {
088                return this.vertices;
089        }
090        
091//      @Deprecated
092//      public Line2D[] getSegments() {
093//              Segment[] origSegments = hull.getLineSegments();
094//              Line2D[] newSegments = new Line2D.Double[origSegments.length];
095//              for (int i = 0; i < origSegments.length; i++) {
096//                      Segment seg = origSegments[i];
097//                      Vector2D start = seg.getStart();
098//                      Vector2D end = seg.getEnd();
099//                      newSegments[i] = new Line2D.Double(start.getX(), start.getY(), end.getX(), end.getY());
100//              }
101//              return newSegments;
102//      }
103        
104        // --------------------------------------------------------------------
105        
106
107
108        @Override
109        public Shape getShape(double scale) {
110                if (vertices.length < 2) {      // degenerate case (single point)
111                        return vertices[0].getShape(scale);
112                }
113                else {
114                        Path2D path = new Path2D.Double(Path2D.WIND_NON_ZERO, 4);
115                        path.moveTo(vertices[0].getX(), vertices[0].getY());
116                        for (int i = 1; i < vertices.length; i++) {
117                                path.lineTo(vertices[i].getX(), vertices[i].getY());
118                        }
119                        path.closePath();
120                        return path;
121                }
122        }
123        
124        // --------------------------------------------------------------------
125        
126        public static final double DefaultContainsTolerance = 1e-12;
127        
128        public boolean contains(Pnt2d p) {
129                return contains(p, DefaultContainsTolerance);
130        }
131
132        /**
133         * Checks if this convex hull contains the specified point. This method is used instead of
134         * {@link Path2D#contains(double, double)} to avoid false results due to roundoff errors.
135         *
136         * @param p some 2D point
137         * @param tolerance positive quantity for being outside
138         * @return true if the point is inside the hull
139         */
140        public boolean contains(Pnt2d p, double tolerance) {
141                for (int i = 0; i < vertices.length; i++) {
142                        int j = (i + 1) % vertices.length;
143                        AlgebraicLine line = AlgebraicLine.from(vertices[i], vertices[j]);
144                        double dist = line.getSignedDistance(p);
145                        // positive signed distance means that the point is to the left
146                        if (dist + tolerance < 0) {
147                                return false;
148                        }
149                }
150                return true;
151        }
152
153}