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.guibas;
010
011import imagingbook.common.geometry.basic.Pnt2d;
012import imagingbook.common.geometry.delaunay.Triangle;
013
014import java.util.Arrays;
015
016/**
017 * Represents a 2D triangle, specified by three corner points. Instances of this class are immutable.
018 */
019public class Triangle2D implements Triangle {
020
021        protected final Pnt2d a, b, c;
022        private final boolean isOrientedCCW;
023
024        /**
025         * Constructor of the 2D triangle class used to create a new triangle instance from three 2D vectors describing the
026         * triangle's vertices.
027         *
028         * @param a the first vertex of the triangle
029         * @param b the second vertex of the triangle
030         * @param c the third vertex of the triangle
031         */
032        public Triangle2D(Pnt2d a, Pnt2d b, Pnt2d c) {
033                this.a = a;
034                this.b = b;
035                this.c = c;
036                isOrientedCCW = findIfOrientedCCW();
037        }
038        
039        public Triangle2D(Pnt2d[] points) {
040//              this(new Vector2D(points[0]), new Vector2D(points[1]), new Vector2D(points[2]));
041                this(points[0], points[1], points[2]);
042        }
043
044        /**
045         * Tests if a 2D point lies inside this 2D triangle. See See Christer Ericson, Real-Time Collision Detection, CRC
046         * Press, 2004 (Ch. 5, p. 206).
047         *
048         * @param point the point to be checked
049         * @return {@code true} iff the point lies inside this 2D triangle
050         */
051        public boolean containsPoint(Pnt2d point) {
052                double pab = point.minus(a).cross(b.minus(a));
053                double pbc = point.minus(b).cross(c.minus(b));
054                if (!hasSameSign(pab, pbc)) {
055                        return false;
056                }
057                double pca = point.minus(c).cross(a.minus(c));
058                if (!hasSameSign(pab, pca)) {
059                        return false;
060                }
061                return true;
062        }
063
064        /**
065         * Tests if a given point lies in the circumcircle of this triangle. Let the triangle ABC appear in counterclockwise
066         * (CCW) order. Then when det > 0, the point lies inside the circumcircle through the three points a, b and c. If
067         * instead det < 0, the point lies outside the circumcircle. When det = 0, the four points are cocircular. If the
068         * triangle is oriented clockwise (CW) the result is reversed. See Christer Ericson, Real-Time Collision Detection,
069         * CRC Press, 2004 (Ch. 3, p. 34).
070         *
071         * @param point the point to be checked
072         * @return {@code true} iff the point lies inside the circumcircle through the three points a, b, and c of the
073         * triangle
074         */
075        protected boolean isPointInCircumCircle(Pnt2d point) {
076                final double a11 = a.getX() - point.getX();
077                final double a21 = b.getX() - point.getX();
078                final double a31 = c.getX() - point.getX();
079
080                final double a12 = a.getY() - point.getY();
081                final double a22 = b.getY() - point.getY();
082                final double a32 = c.getY() - point.getY();
083                
084                final double a13 = a11 * a11 + a12 * a12;
085                final double a23 = a21 * a21 + a22 * a22;
086                final double a33 = a31 * a31 + a32 * a32;
087
088                final double det = 
089                                a11 * a22 * a33 + a12 * a23 * a31 + 
090                                a13 * a21 * a32 - a13 * a22 * a31 - 
091                                a12 * a21 * a33 - a11 * a23 * a32;
092
093                return isOrientedCCW ? det > 0.0 : det < 0.0;
094        }
095
096        /**
097         * Tests if a given point lies in the circumcircle of this triangle. Let the triangle ABC appear in counterclockwise
098         * (CCW) order. Then when det &gt; 0, the point lies inside the circumcircle through the three points a, b and c. If
099         * instead det &lt; 0, the point lies outside the circumcircle. When det = 0, the four points are cocircular. If the
100         * triangle is oriented clockwise (CW) the result is reversed. See Christer Ericson, Real-Time Collision Detection,
101         * CRC Press, 2004 (Ch. 3, p. 32). Since triangles are immutable, this property can be pre-calculated.
102         *
103         * @return {@code true} iff the triangle abc is oriented counterclockwise (CCW)
104         */
105        private boolean findIfOrientedCCW() {
106                double a11 = a.getX() - c.getX();
107                double a21 = b.getX() - c.getX();
108                double a12 = a.getY() - c.getY();
109                double a22 = b.getY() - c.getY();
110                double det = a11 * a22 - a12 * a21;
111                return det > 0.0;
112        }
113
114        /**
115         * Test if this triangle is oriented counterclockwise (CCW). This property is pre-calculated.
116         *
117         * @return {@code true} iff the triangle ABC is oriented counterclockwise (CCW)
118         */
119        protected boolean isOrientedCCW() {
120                return isOrientedCCW;
121        }
122
123        /**
124         * Returns {@code true} if this triangle contains the given edge.
125         *
126         * @param edge the edge to be tested
127         * @return {@code true} iff this triangle contains the specified edge
128         */
129        public boolean containsEdge(Edge2D edge) {
130                return (a == edge.a || b == edge.a || c == edge.a) && (a == edge.b || b == edge.b || c == edge.b);
131        }
132
133        /**
134         * Returns the vertex of this triangle opposite to the specified edge.
135         * 
136         * @param edge the edge (which must be contained in this triangle)
137         * @return the triangle vertex opposite to the specified edge
138         */
139        public Pnt2d getOppositeVertex(Edge2D edge) {
140                final Pnt2d p1 = edge.a;
141                final Pnt2d p2 = edge.b;
142                if ((a == p1 && b == p2) || (a == p2 && b == p1)) {
143                        return c;
144                }
145                if ((a == p1 && c == p2) || (a == p2 && c == p1)) {
146                        return b;
147                }
148                if ((b == p1 && c == p2) || (b == p2 && c == p1)) {
149                        return a;
150                } 
151                throw new IllegalArgumentException("Specified edge is not part of this triangle");
152        }
153
154        /**
155         * Checks if the given vertex is amongst the triangle's vertices.
156         * 
157         * @param vertex the vertex to be checked
158         * @return {@code true} if the vertex is one of the corners of this triangle
159         */
160        public boolean hasVertex(Pnt2d vertex) {
161                return (a == vertex || b == vertex || c == vertex);
162        }
163
164        /**
165         * Calculates the minimum distance from the specified point to this triangle. The result is returned as an
166         * {@link Edge2D.Distance} instance, representing the point's distance to the closest edge of this triangle.
167         *
168         * @param point the point to be checked
169         * @return the edge of this triangle that is closest to the specified point
170         */
171        public Edge2D.Distance findMinEdgeDistance(Pnt2d point) {
172                Edge2D.Distance[] distances = {
173                                new Edge2D(a, b).distanceFromPoint(point),
174                                new Edge2D(b, c).distanceFromPoint(point),
175                                new Edge2D(c, a).distanceFromPoint(point)       
176                        };
177                Arrays.sort(distances);
178                return distances[0];
179        }
180
181        /**
182         * Tests if the two arguments have the same sign.
183         * @param a first quantity
184         * @param b second quantity
185         * @return {@code true} iff both arguments have the same sign
186         */
187        private boolean hasSameSign(double a, double b) {
188                return Math.signum(a) == Math.signum(b);
189                //return a * b > 0;
190        }
191
192        @Override
193        public String toString() {
194                return Triangle2D.class.getSimpleName() + "[" + a + ", " + b + ", " + c + "]";
195        }
196
197
198        public Pnt2d[] getPoints() {
199                return new Pnt2d[] {a, b, c};
200        }
201
202}