/*
    * Licensed to the Apache Software Foundation (ASF) under one or more
    * contributor license agreements.  See the NOTICE file distributed with
    * this work for additional information regarding copyright ownership.
    * The ASF licenses this file to You 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
    *
    *      https://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 org.hipparchus.geometry.euclidean.twod.hull;
  
  import java.io.Serializable;
  
  import org.hipparchus.exception.LocalizedCoreFormats;
  import org.hipparchus.exception.MathIllegalArgumentException;
  import org.hipparchus.geometry.LocalizedGeometryFormats;
  import org.hipparchus.geometry.euclidean.twod.Euclidean2D;
  import org.hipparchus.geometry.euclidean.twod.Line;
  import org.hipparchus.geometry.euclidean.twod.Segment;
  import org.hipparchus.geometry.euclidean.twod.Vector2D;
  import org.hipparchus.geometry.hull.ConvexHull;
  import org.hipparchus.geometry.partitioning.Region;
  import org.hipparchus.geometry.partitioning.RegionFactory;
  import org.hipparchus.util.MathArrays;
  import org.hipparchus.util.Precision;
  
  /**
   * This class represents a convex hull in an two-dimensional euclidean space.
   *
   */
  public class ConvexHull2D implements ConvexHull<Euclidean2D, Vector2D>, Serializable {
  
      /** Serializable UID. */
      private static final long serialVersionUID = 20140129L;
  
      /** Vertices of the hull. */
      private final Vector2D[] vertices;
  
      /** Tolerance threshold used during creation of the hull vertices. */
      private final double tolerance;
  
      /**
       * Line segments of the hull.
       * The array is not serialized and will be created from the vertices on first access.
       */
      private transient Segment[] lineSegments;
  
      /**
       * Simple constructor.
       * @param vertices the vertices of the convex hull, must be ordered
       * @param tolerance tolerance below which points are considered identical
       * @throws MathIllegalArgumentException if the vertices do not form a convex hull
       */
      public ConvexHull2D(final Vector2D[] vertices, final double tolerance)
          throws MathIllegalArgumentException {
  
          // assign tolerance as it will be used by the isConvex method
          this.tolerance = tolerance;
  
          if (!isConvex(vertices)) {
              throw new MathIllegalArgumentException(LocalizedGeometryFormats.NOT_CONVEX);
          }
  
          this.vertices = vertices.clone();
      }
  
      /**
       * Checks whether the given hull vertices form a convex hull.
       * @param hullVertices the hull vertices
       * @return {@code true} if the vertices form a convex hull, {@code false} otherwise
       */
      private boolean isConvex(final Vector2D[] hullVertices) {
          if (hullVertices.length < 3) {
              return true;
          }
  
          int sign = 0;
          for (int i = 0; i < hullVertices.length; i++) {
              final Vector2D p1 = hullVertices[i == 0 ? hullVertices.length - 1 : i - 1];
              final Vector2D p2 = hullVertices[i];
              final Vector2D p3 = hullVertices[i == hullVertices.length - 1 ? 0 : i + 1];
  
              final Vector2D d1 = p2.subtract(p1);
              final Vector2D d2 = p3.subtract(p2);
  
              final double crossProduct = MathArrays.linearCombination(d1.getX(), d2.getY(), -d1.getY(), d2.getX());
              final int cmp = Precision.compareTo(crossProduct, 0.0, tolerance);
              // in case of collinear points the cross product will be zero
              if (cmp != 0.0) {
                  if (sign != 0.0 && cmp != sign) {
                      return false;
                  }
                 sign = cmp;
             }
         }
 
         return true;
     }
 
     /** {@inheritDoc} */
     @Override
     public Vector2D[] getVertices() {
         return vertices.clone();
     }
 
     /**
      * Get the line segments of the convex hull, ordered.
      * @return the line segments of the convex hull
      */
     public Segment[] getLineSegments() {
         return retrieveLineSegments().clone();
     }
 
     /**
      * Retrieve the line segments from the cached array or create them if needed.
      *
      * @return the array of line segments
      */
     private Segment[] retrieveLineSegments() {
         if (lineSegments == null) {
             // construct the line segments - handle special cases of 1 or 2 points
             final int size = vertices.length;
             if (size <= 1) {
                 this.lineSegments = new Segment[0];
             } else if (size == 2) {
                 this.lineSegments = new Segment[1];
                 final Vector2D p1 = vertices[0];
                 final Vector2D p2 = vertices[1];
                 this.lineSegments[0] = new Segment(p1, p2, new Line(p1, p2, tolerance));
             } else {
                 this.lineSegments = new Segment[size];
                 Vector2D firstPoint = null;
                 Vector2D lastPoint = null;
                 int index = 0;
                 for (Vector2D point : vertices) {
                     if (lastPoint == null) {
                         firstPoint = point;
                         lastPoint = point;
                     } else {
                         this.lineSegments[index++] =
                                 new Segment(lastPoint, point, new Line(lastPoint, point, tolerance));
                         lastPoint = point;
                     }
                 }
                 this.lineSegments[index] =
                         new Segment(lastPoint, firstPoint, new Line(lastPoint, firstPoint, tolerance));
             }
         }
         return lineSegments;
     }
 
     /** {@inheritDoc} */
     @Override
     public Region<Euclidean2D> createRegion() throws MathIllegalArgumentException {
         if (vertices.length < 3) {
             throw new MathIllegalArgumentException(LocalizedCoreFormats.INSUFFICIENT_DATA);
         }
         final RegionFactory<Euclidean2D> factory = new RegionFactory<>();
         final Segment[] segments = retrieveLineSegments();
         final Line[] lineArray = new Line[segments.length];
         for (int i = 0; i < segments.length; i++) {
             lineArray[i] = segments[i].getLine();
         }
         return factory.buildConvex(lineArray);
     }
 }