/*
    * Copyright (C) 2012 Alberto Irurueta Carro (alberto@irurueta.com)
    *
    * Licensed under the Apache License, Version 2.0 (the "License");
    * you may not use this file except in compliance with the License.
    * You may obtain a copy of the License at
    *
    *         http://www.apache.org/licenses/LICENSE-2.0
    *
   * Unless required by applicable law or agreed to in writing, software
   * distributed under the License is distributed on an "AS IS" BASIS,
   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   * See the License for the specific language governing permissions and
   * limitations under the License.
   */
  package com.irurueta.geometry;
  
  import java.io.Serializable;
  import java.util.ArrayList;
  import java.util.List;
  
  /**
   * This class defines a polygon in 2D space.
   */
  @SuppressWarnings("DuplicatedCode")
  public class Polygon2D implements Serializable {
  
      /**
       * Default threshold value. Thresholds are used to determine whether a point
       * lies inside the polygon or not, or if it's locus or not, etc.
       */
      public static final double DEFAULT_THRESHOLD = 1e-9;
  
      /**
       * Minimum allowed threshold value.
       */
      public static final double MIN_THRESHOLD = 0.0;
  
      /**
       * Minimum number of vertices that a polygon is allowed to have.
       */
      public static final int MIN_VERTICES = 3;
  
      /**
       * Default method for triangulation.
       */
      public static final TriangulatorMethod DEFAULT_TRIANGULATOR_METHOD = TriangulatorMethod.VAN_GOGH_TRIANGULATOR;
  
      /**
       * List containing vertices of this polygon. Each vertex is a 2D point.
       */
      private List<Point2D> vertices;
  
      /**
       * Boolean indicating whether polygon has already been triangulated.
       */
      private boolean triangulated;
  
      /**
       * List containing triangles found after triangulating this polygon.
       * Initially this list will be null until triangulation is done.
       */
      private List<Triangle2D> triangles;
  
      /**
       * Method to do triangulation.
       */
      private TriangulatorMethod triangulatorMethod;
  
      /**
       * Constructor.
       *
       * @param vertices List of vertices forming this polygon.
       * @throws NotEnoughVerticesException Raised if list does not contain enough
       *                                    vertices.
       * @see #MIN_VERTICES
       */
      public Polygon2D(final List<Point2D> vertices) throws NotEnoughVerticesException {
          setVertices(vertices);
          triangulatorMethod = DEFAULT_TRIANGULATOR_METHOD;
      }
  
      /**
       * Returns triangulator method. Triangulator method determines the way a
       * polygon is divided into triangles.
       * If none has been provided DEFAULT_TRIANGULATOR_METHOD will be returned.
       *
       * @return Triangulator method.
       */
      public TriangulatorMethod getTriangulatorMethod() {
          return triangulatorMethod;
      }
  
      /**
       * Sets triangulator method. A triangulator method determines the way a
       * polygon is divided into triangles.
       *
       * @param triangulatorMethod A triangulator method.
       */
     public void setTriangulatorMethod(final TriangulatorMethod triangulatorMethod) {
         this.triangulatorMethod = triangulatorMethod;
     }
 
     /**
      * Returns the list of vertices forming this polygon.
      *
      * @return List of vertices.
      */
     public List<Point2D> getVertices() {
         return vertices;
     }
 
     /**
      * Sets list of vertices forming this polygon.
      *
      * @param vertices List of vertices.
      * @throws NotEnoughVerticesException Raised if provided list does not have
      *                                    enough vertices.
      * @see #MIN_VERTICES
      */
     public final void setVertices(final List<Point2D> vertices) throws NotEnoughVerticesException {
         if (vertices.size() < MIN_VERTICES) {
             throw new NotEnoughVerticesException();
         }
 
         if (vertices instanceof Serializable) {
             this.vertices = vertices;
         } else {
             this.vertices = new ArrayList<>(vertices);
         }
         triangulated = false;
         triangles = null;
     }
 
     /**
      * Determines whether this polygon has already been triangulated.
      * A polygon will only need to be triangulated once, unless the list of
      * vertices is reset.
      *
      * @return True if polygon has already been triangulated, false otherwise.
      */
     public boolean isTriangulated() {
         return triangulated;
     }
 
     /**
      * Returns a list of triangles forming this polygon.
      * This method checks whether this polygon has already been triangulated,
      * if not, it performs triangulation first.
      *
      * @return A list of triangles forming this polygon.
      * @throws TriangulatorException Raised if triangulation was needed and
      *                               failed.
      */
     public List<Triangle2D> getTriangles() throws TriangulatorException {
         if (!isTriangulated()) {
             triangulate();
         }
         return triangles;
     }
 
     /**
      * Returns signed area of this polygon.
      * The sign of the area determines whether vertices of the polygon are
      * provided in clockwise (negative sign) or clockwise (positive sign) order.
      *
      * @return Signed area of this polygon.
      */
     public double getSignedArea() {
         final var iterator = vertices.iterator();
 
         // because there are at least 3
         // vertices
         var prevPoint = iterator.next();
         Point2D curPoint;
         var signedArea = 0.0;
 
         while (iterator.hasNext()) {
             curPoint = iterator.next();
 
             signedArea += prevPoint.getInhomX() * (curPoint.getInhomY() - prevPoint.getInhomY());
             prevPoint = curPoint;
         }
         // on last point, check previous with first
         curPoint = vertices.get(0);
         signedArea += prevPoint.getInhomX() * (curPoint.getInhomY() - prevPoint.getInhomY());
 
         // signed area is half the sum of cross products of consecutive vertices
         return signedArea;
     }
 
     /**
      * Returns area of this polygon.
      *
      * @return Area of this polygon.
      */
     public double getArea() {
         return Math.abs(getSignedArea());
     }
 
     /**
      * Determines whether vertices of this polygon are in clockwise order or
      * in counterclockwise order.
      *
      * @param threshold threshold to determine if vertices are in clockwise
      *                  order. Usually this value is zero.
      * @return True if vertices are in clockwise order, false otherwise.
      */
     public boolean areVerticesClockwise(final double threshold) {
         return getSignedArea() < threshold;
     }
 
     /**
      * Determines whether vertices of this polygon are in clockwise order or in
      * counterclockwise order.
      *
      * @return True if vertices are in clockwise order, false otherwise.
      */
     public boolean areVerticesClockwise() {
         // default threshold to check sign
         return areVerticesClockwise(0.0);
     }
 
 
     /**
      * Returns perimeter of this polygon.
      * The perimeter is computed as the sum of the distances between consecutive
      * pairs of vertices.
      *
      * @return Perimeter of this polygon.
      */
     public double getPerimeter() {
         // iterate over all vertices and compute their distance
         final var iterator = vertices.iterator();
         var prevPoint = iterator.next();
         Point2D point;
         var perimeter = 0.0;
         while (iterator.hasNext()) {
             point = iterator.next();
             perimeter += prevPoint.distanceTo(point);
             prevPoint = point;
         }
         // get distance from last point with first one
         perimeter += prevPoint.distanceTo(vertices.get(0));
         return perimeter;
     }
 
     /**
      * Determines if provided point lies within the region defined by this
      * polygon.
      * Notice that this method is only ensured to work for polygons having no
      * holes or crossing borders. It will safely work on any other polygon,
      * no matter if it is regular, non-regular, convex or concave.
      *
      * @param point Point to be checked.
      * @return True if point lies within the area defined by this polygon, false
      * otherwise.
      * @throws TriangulatorException Raised if triangulation was required but
      *                               failed.
      */
     public boolean isInside(final Point2D point) throws TriangulatorException {
         return isInside(point, DEFAULT_THRESHOLD);
     }
 
     /**
      * Determines if provided point lies within the region defined by this
      * polygon.
      * Notice that this method is only ensured to work for polygons having no
      * holes or crossing borders. It will safely work on any other polygon,
      * no matter if it is regular, non-regular, convex or concave.
      *
      * @param point     Point to be checked.
      * @param threshold Threshold to determine whether point lies inside this
      *                  polygon. Usually this value should be small.
      * @return True if point lies within the area defined by this polygon, false
      * otherwise.
      * @throws IllegalArgumentException Raised if provided threshold is negative.
      * @throws TriangulatorException    Raised if triangulation was required but
      *                                  failed.
      */
     public boolean isInside(final Point2D point, final double threshold) throws TriangulatorException {
         if (threshold < MIN_THRESHOLD) {
             throw new IllegalArgumentException();
         }
 
         for (final var triangle : getTriangles()) {
             if (triangle.isInside(point, threshold)) {
                 return true;
             }
         }
         return false;
     }
 
     /**
      * Returns the center of this polygon.
      * The center is the average point among all the vertices of this polygon.
      * The center is not ensure to lie within the area formed by this polygon.
      *
      * @return Center of this polygon.
      */
     public Point2D getCenter() {
         final var result = Point2D.create();
         center(result);
         return result;
     }
 
     /**
      * Computes the center of this polygon.
      * The center is the average point among all the vertices of this polygon.
      * The center is not ensured to lie within the area formed by this polygon.
      *
      * @param result Instance where the computed center will be stored.
      */
     public void center(final Point2D result) {
         // compute average location of all vertices
         var inhomX = 0.0;
         var inhomY = 0.0;
         final var total = vertices.size();
 
         for (final var point : vertices) {
             inhomX += point.getInhomX() / total;
             inhomY += point.getInhomY() / total;
         }
         result.setInhomogeneousCoordinates(inhomX, inhomY);
     }
 
     /**
      * Determines whether provided point is locus of the borders defined by
      * the vertices of this polygon. A point will be locus if it lies in the
      * line defined by two consecutive vertices up to a certain threshold of
      * error.
      *
      * @param point     Point to be checked.
      * @param threshold Threshold of allowed error. This should usually be a
      *                  small value.
      * @return True if provided point lies in a border of this polygon, false
      * otherwise.
      * @throws IllegalArgumentException Raised if provided threshold is negative.
      */
     public boolean isLocus(final Point2D point, final double threshold) {
         if (threshold < MIN_THRESHOLD) {
             throw new IllegalArgumentException();
         }
 
         final var iterator = vertices.iterator();
         // it's ok because there are at
         // least 3 vertices
         var prevPoint = iterator.next();
         Point2D curPoint;
         while (iterator.hasNext()) {
             curPoint = iterator.next();
             if (point.isBetween(prevPoint, curPoint, threshold)) {
                 return true;
             }
             prevPoint = curPoint;
         }
 
         // check last point with first
         return point.isBetween(prevPoint, vertices.get(0), threshold);
     }
 
     /**
      * Determines whether provided point is locus of the borders defined by the
      * vertices of this polygon. A point will be locus if it lies in the line
      * defined by two consecutive vertices.
      *
      * @param point Point to be checked.
      * @return True if provided point lies in a border of this polygon, false
      * otherwise.
      */
     public boolean isLocus(final Point2D point) {
         return isLocus(point, DEFAULT_THRESHOLD);
     }
 
     /**
      * Returns the shortest distance from provided point to a border of this
      * polygon. Note that borders are segments defined by consecutive vertices.
      *
      * @param point Point to be checked.
      * @return Shortest distance from provided point to this polygon.
      */
     public double getShortestDistance(final Point2D point) {
         // iterate over all vertices and compute their distance
         var iterator = vertices.iterator();
         var prevPoint = iterator.next();
         // to increase accuracy
         prevPoint.normalize();
         Point2D curPoint;
         var bestDist = Double.MAX_VALUE;
         double dist;
         var found = false;
         final var line = new Line2D();
         final var pointInLine = Point2D.create();
 
         while (iterator.hasNext()) {
             curPoint = iterator.next();
             // to increase accuracy
             curPoint.normalize();
 
             // check if point lies in the segment of the boundary of this polygon
             if (point.isBetween(curPoint, prevPoint)) {
                 return 0.0;
             }
 
             line.setParametersFromPairOfPoints(curPoint, prevPoint);
             // to increase accuracy
             line.normalize();
 
             // find the closest point to line
             line.closestPoint(point, pointInLine);
             // to increase accuracy
             pointInLine.normalize();
 
             if (pointInLine.isBetween(curPoint, prevPoint)) {
                 // closest point lies within segment of polygon boundary, so we
                 // keep distance
                 dist = point.distanceTo(pointInLine);
                 if (dist < bestDist) {
                     // a better point has been found
                     bestDist = dist;
                     found = true;
                 }
             }
 
             prevPoint = curPoint;
         }
 
         // try last vertex with first
         // check if point lies in the segment of the boundary of this polygon
         final var first = vertices.get(0);
         if (point.isBetween(prevPoint, first)) {
             return 0.0;
         }
 
         line.setParametersFromPairOfPoints(prevPoint, first);
         // to increase accuracy
         line.normalize();
 
         // find the closest point to line
         line.closestPoint(point, pointInLine);
         // to increase accuracy
         pointInLine.normalize();
 
         if (pointInLine.isBetween(prevPoint, first)) {
             // closest point lies within segment of polygon boundary, so we
             // keep distance
             dist = point.distanceTo(pointInLine);
             if (dist < bestDist) {
                 // a better point has been found
                 bestDist = dist;
                 found = true;
             }
         }
 
         if (!found) {
             // no closest point was found on a segment belonging to polygon
             // boundary, so we search for the closest vertex
             iterator = vertices.iterator();
             while (iterator.hasNext()) {
                 // a better vertex has been found
                 curPoint = iterator.next();
                 dist = point.distanceTo(curPoint);
                 if (dist < bestDist) {
                     bestDist = dist;
                 }
             }
         }
 
         return bestDist;
     }
 
     /**
      * Returns the closest point to provided point that is locus of this
      * polygon (i.e. lies on a border of this polygon).
      *
      * @param point Point to be checked.
      * @return Closest point being locus of this polygon.
      */
     public Point2D getClosestPoint(final Point2D point) {
         final var result = Point2D.create();
         closestPoint(point, result);
         return result;
     }
 
     /**
      * Computes the closes point to provided point that is locus of this
      * polygon (i.e. lies on a border of this polygon).
      *
      * @param point  Point to be checked.
      * @param result Instance where the closest point will be stored.
      */
     public void closestPoint(final Point2D point, final Point2D result) {
         // iterate over all vertices and compute their distance
         var iterator = vertices.iterator();
         var prevPoint = iterator.next();
         // to increase accuracy
         prevPoint.normalize();
 
         Point2D curPoint;
         var bestDist = Double.MAX_VALUE;
         double dist;
         var found = false;
         final var line = new Line2D();
         final var pointInLine = Point2D.create();
 
         while (iterator.hasNext()) {
             curPoint = iterator.next();
             // to increase accuracy
             curPoint.normalize();
 
             // check if point lies in the segment of the boundary of this polygon
             if (point.isBetween(curPoint, prevPoint)) {
                 result.setCoordinates(point);
                 return;
             }
 
             line.setParametersFromPairOfPoints(curPoint, prevPoint);
             // to increase accuracy
             line.normalize();
 
             // find the closest point to line
             line.closestPoint(point, pointInLine);
             // to increase accuracy
             pointInLine.normalize();
 
             if (pointInLine.isBetween(curPoint, prevPoint)) {
                 // closest point lies within segment of polygon boundary, so we
                 // keep distance and point
                 dist = point.distanceTo(pointInLine);
                 if (dist < bestDist) {
                     // a better point has been found
                     bestDist = dist;
                     result.setCoordinates(pointInLine);
                     found = true;
                 }
             }
 
             prevPoint = curPoint;
         }
 
         // try last vertex with first
         // check if point lies in the segment of the boundary of this polygon
         final var first = vertices.get(0);
         if (point.isBetween(prevPoint, first)) {
             result.setCoordinates(point);
             return;
         }
 
         line.setParametersFromPairOfPoints(prevPoint, first);
         // to increase accuracy
         line.normalize();
 
         // find the closest point to line
         line.closestPoint(point, pointInLine);
         // to increase accuracy
         pointInLine.normalize();
 
         if (pointInLine.isBetween(prevPoint, first)) {
             // closest point lies within segment of polygon boundary, so we
             // keep distance
             dist = point.distanceTo(pointInLine);
             if (dist < bestDist) {
                 // a better point has been found
                 bestDist = dist;
                 result.setCoordinates(pointInLine);
                 found = true;
             }
         }
 
         if (!found) {
             // no closest point was found on a segment belonging to polygon
             // boundary, so we search for the closest vertex
             iterator = vertices.iterator();
             while (iterator.hasNext()) {
                 curPoint = iterator.next();
                 dist = point.distanceTo(curPoint);
                 if (dist < bestDist) {
                     // a better vertex has been found
                     bestDist = dist;
                     result.setCoordinates(curPoint);
                 }
             }
         }
     }
 
     /**
      * Triangulates this polygon using this polygon's triangulator method.
      * A polygon only will be triangulated once when required or this method is
      * called.
      * This method will make no action if a polygon is already triangulated
      * unless it's vertices are reset.
      *
      * @throws TriangulatorException Raised if triangulation failed
      * @see #getTriangulatorMethod
      * @see #setTriangulatorMethod(TriangulatorMethod)
      */
     public void triangulate() throws TriangulatorException {
         if (!triangulated) {
             final var triangulator = Triangulator2D.create(triangulatorMethod);
             triangles = triangulator.triangulate(vertices);
             triangulated = true;
         }
     }
 }