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.basic.PntUtils;
014import imagingbook.common.geometry.line.AlgebraicLine;
015import imagingbook.common.geometry.shape.ShapeProducer;
016import imagingbook.common.util.ArrayUtils;
017
018import java.awt.Shape;
019import java.awt.geom.Path2D;
020import java.util.Arrays;
021
022import static imagingbook.common.math.Arithmetic.isZero;
023import static imagingbook.common.math.Arithmetic.radius;
024import static imagingbook.common.math.Arithmetic.sqr;
025import static imagingbook.common.math.Matrix.add;
026import static imagingbook.common.math.Matrix.makeDoubleVector;
027import static imagingbook.common.math.Matrix.multiply;
028import static java.lang.Math.sqrt;
029
030/**
031 * <p>
032 * Represents a major axis-aligned bounding box of a 2D point set. At least one point is required to set up a bounding
033 * box. If the direction vector is undefined (e.g., in the case of a single input point), the unit vector in x-direction
034 * is assumed. See Sec. 8.6.4 (Alg. 8.6) of [1] for details.
035 * </p>
036 * <p>
037 * [1] W. Burger, M.J. Burge, <em>Digital Image Processing &ndash; An Algorithmic Introduction</em>, 3rd ed, Springer
038 * (2022).
039 * </p>
040 *
041 * @author WB
042 * @version 2022/11/01
043 */
044public class AxisAlignedBoundingBox implements ShapeProducer {
045        
046        private final Pnt2d centroid;   // centroid of the point set
047        private final double[] dir;             // orientation vector
048        private final Pnt2d[] corners;  // corner points of the bounding box
049        private final AlgebraicLine[] boundinglines;
050
051        /**
052         * Constructor, creates a {@link AxisAlignedBoundingBox} instance from an {@link Iterable} over {@link Pnt2d}. At
053         * least one distinct point is required.
054         *
055         * @param points an iterator over 2D points
056         */
057        public AxisAlignedBoundingBox(Iterable<Pnt2d> points) {
058                if (!points.iterator().hasNext()) {
059                        throw new IllegalArgumentException("empty point sequence, at least one input point required");
060                }
061                this.centroid = PntUtils.centroid(points); //makeCentroid();    
062                this.dir = makeOrientationVector(points);
063                this.corners = makeBox(points);
064                this.boundinglines = makeBoundingLines();
065        }
066
067        /**
068         * Constructor, creates a {@link AxisAlignedBoundingBox} instance from an array of {@link Pnt2d} points. At least
069         * one distinct point is required.
070         *
071         * @param points an array of 2D points
072         */
073        public AxisAlignedBoundingBox(Pnt2d[] points) {
074                this(() -> ArrayUtils.getIterator(points));
075        }
076
077        /**
078         * Returns the orientation vector of this bounding box (pointing in the direction of its major axis).
079         *
080         * @return the orientation vector of this bounding box
081         */
082        public double[] getOrientationVector() {
083                return dir;
084        }
085
086        /**
087         * Returns an array of four {@link AlgebraicLine} instances which coincide with the outline of the bounding box. The
088         * lines can be used to determine if a given point is inside the box or not (see {@link #contains(Pnt2d, double)}).
089         *
090         * @return an array of bounding lines
091         */
092        public AlgebraicLine[] getBoundingLines() {
093                return this.boundinglines;
094        }
095        
096        /**
097         * Returns an array holding the 4 corner points of the bounding box.
098         * 
099         * @return as described above
100         */
101        public Pnt2d[] getVertices() {
102                return this.corners;
103        }
104
105        /**
106         * Calculates the major axis-aligned bounding box of the supplied region, as a sequence of four point coordinates
107         * (p0, p1, p2, p3).
108         *
109         * @return the region's bounding box as a sequence of the 4 corner coordinates (p0, p1, p2, p3)
110         */
111        private Pnt2d[] makeBox(Iterable<Pnt2d> points) {
112                //double theta = getOrientationAngle(points);
113                
114                double[] xy = this.dir;
115                if (xy == null) {       // regin's orientation is undefined
116                        return null;
117                }
118                        
119                double xa = xy[0]; // = Math.cos(theta);
120                double ya = xy[1]; // = Math.sin(theta);
121                double[] ea = {xa,  ya};
122                double[] eb = {ya, -xa};
123                
124                double amin = Double.POSITIVE_INFINITY;
125                double amax = Double.NEGATIVE_INFINITY;
126                double bmin = Double.POSITIVE_INFINITY;
127                double bmax = Double.NEGATIVE_INFINITY;
128                
129                for (Pnt2d p : points) {
130                        double u = p.getX();
131                        double v = p.getY();
132                        double a = u * xa + v * ya;     // project (u,v) on the major axis vector
133                        double b = u * ya - v * xa;     // project (u,v) on perpendicular vector
134                        amin = Math.min(a, amin);
135                        amax = Math.max(a, amax);
136                        bmin = Math.min(b, bmin);
137                        bmax = Math.max(b, bmax);
138                }
139                
140                Pnt2d[] corners = new Pnt2d[4];
141                corners[0] = PntDouble.from(add(multiply(amin, ea), multiply(bmin, eb)));
142                corners[1] = PntDouble.from(add(multiply(amin, ea), multiply(bmax, eb)));
143                corners[2] = PntDouble.from(add(multiply(amax, ea), multiply(bmax, eb)));
144                corners[3] = PntDouble.from(add(multiply(amax, ea), multiply(bmin, eb)));
145                return corners;
146        }
147
148        private double[] makeOrientationVector(Iterable<Pnt2d> points) {
149                double mu20 = 0;
150                double mu02 = 0;
151                double mu11 = 0;
152                double xc = centroid.getX();
153                double yc = centroid.getY();
154                
155                for (Pnt2d p : points) {
156                        double dx = p.getX() - xc;
157                        double dy = p.getY() - yc;
158                        mu20 = mu20 + dx * dx;
159                        mu02 = mu02 + dy * dy;
160                        mu11 = mu11 + dx * dy;
161                }
162                
163                double A = 2 * mu11;
164                double B = mu20 - mu02;
165                
166                double xTheta = B + sqrt(sqr(A) + sqr(B));
167                double yTheta = A;
168                double d = radius(xTheta, yTheta);
169                
170                return (isZero(d)) ? new double[] {1, 0} : new double[] {xTheta / d, yTheta / d};
171        }
172        
173        // shape-related methods:
174        
175        @Override
176        public Path2D getShape(double scale) {
177                // shape of the actual bounding box
178                Path2D p = new Path2D.Double(Path2D.WIND_NON_ZERO, 4);
179                p.moveTo(corners[0].getX(), corners[0].getY());
180                p.lineTo(corners[1].getX(), corners[1].getY());
181                p.lineTo(corners[2].getX(), corners[2].getY());
182                p.lineTo(corners[3].getX(), corners[3].getY());
183                p.closePath();
184                return p;
185        }
186        
187        @Override
188        public Shape[] getShapes(double scale) {
189                return new Shape[] { 
190                                getShape(scale),                                // primary shape element
191                                this.centroid.getShape(scale)   // additional shape elements
192                                };
193        }
194        
195        private AlgebraicLine[] makeBoundingLines() {
196                double dx = dir[0];
197                double dy = dir[1];
198                return new AlgebraicLine[] {
199                                AlgebraicLine.from(corners[0].toDoubleArray(), makeDoubleVector( dy, -dx)),             // 0 -> 1
200                                AlgebraicLine.from(corners[1].toDoubleArray(), makeDoubleVector( dx,  dy)),             // 1 -> 2
201                                AlgebraicLine.from(corners[2].toDoubleArray(), makeDoubleVector(-dy,  dx)),             // 2 -> 3
202                                AlgebraicLine.from(corners[3].toDoubleArray(), makeDoubleVector(-dx, -dy))
203                                };      // 3 -> 0
204        }
205        
206        public static final double DefaultContainsTolerance = 1e-12;
207
208
209        /**
210         * Checks if this bounding box contains the specified point using the default tolerance. This method is used instead
211         * of {@link Path2D#contains(double, double)} to avoid false results due to roundoff errors.
212         *
213         * @param p some 2D point
214         * @return true if the point is inside the bounding box
215         */
216        public boolean contains(Pnt2d p) {
217                return contains(p, DefaultContainsTolerance);
218        }
219
220        /**
221         * Checks if this bounding box contains the specified point using the specified tolerance. This method is used
222         * instead of {@link Path2D#contains(double, double)} to avoid false results due to roundoff errors.
223         *
224         * @param p some 2D point
225         * @param tolerance positive quantity for being outside
226         * @return true if the point is inside the bounding box
227         */
228        public boolean contains(Pnt2d p, double tolerance) {
229                for (int i = 0; i < 4; i++) {
230                        double dist = boundinglines[i].getSignedDistance(p);
231                        // positive signed distance means that the point is to the left
232                        if (dist + tolerance < 0) {
233                                return false;
234                        }
235                }
236                return true;
237        }
238        
239        @Override
240        public String toString() {
241                return String.format("%s: %s", this.getClass().getSimpleName(), Arrays.toString(this.corners));
242        }
243}