/*
    * 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
    *
    *      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 org.apache.commons.geometry.euclidean.threed;
  
  import java.util.ArrayList;
  import java.util.Iterator;
  import java.util.List;
  
  import org.apache.commons.geometry.core.RegionLocation;
  import org.apache.commons.geometry.core.partitioning.Hyperplane;
  import org.apache.commons.geometry.core.partitioning.HyperplaneLocation;
  import org.apache.commons.geometry.core.partitioning.Split;
  import org.apache.commons.geometry.euclidean.internal.Vectors;
  import org.apache.commons.geometry.euclidean.threed.line.Lines3D;
  import org.apache.commons.geometry.euclidean.twod.ConvexArea;
  import org.apache.commons.geometry.euclidean.twod.Vector2D;
  import org.apache.commons.numbers.core.Precision;
  
  /** Abstract base class for {@link ConvexPolygon3D} implementations.
   */
  abstract class AbstractConvexPolygon3D extends AbstractPlaneSubset implements ConvexPolygon3D {
  
      /** Plane containing the convex polygon. */
      private final Plane plane;
  
      /** Simple constructor.
       * @param plane the plane containing the convex polygon
       */
      AbstractConvexPolygon3D(final Plane plane) {
          this.plane = plane;
      }
  
      /** {@inheritDoc} */
      @Override
      public Plane getPlane() {
          return plane;
      }
  
      /** {@inheritDoc}
       *
       *  <p>This method always returns {@code false}.</p>
       */
      @Override
      public boolean isFull() {
          return false;
      }
  
      /** {@inheritDoc}
       *
       *  <p>This method always returns {@code false}.</p>
       */
      @Override
      public boolean isEmpty() {
          return false;
      }
  
      /** {@inheritDoc} */
      @Override
      public double getSize() {
          // see http://geomalgorithms.com/a01-_area.html#3D-Planar-Polygons
          final List<Vector3D> vertices = getVertices();
  
          double crossSumX = 0.0;
          double crossSumY = 0.0;
          double crossSumZ = 0.0;
  
          Vector3D prevPt = vertices.get(vertices.size() - 1);
          Vector3D cross;
          for (final Vector3D curPt : vertices) {
              cross = prevPt.cross(curPt);
  
              crossSumX += cross.getX();
              crossSumY += cross.getY();
              crossSumZ += cross.getZ();
  
              prevPt = curPt;
          }
  
          return 0.5 * plane.getNormal().dot(Vector3D.of(crossSumX, crossSumY, crossSumZ));
      }
  
      /** {@inheritDoc} */
      @Override
      public Vector3D getCentroid() {
          final List<Vector3D> vertices = getVertices();
 
         double areaSum = 0.0;
         double scaledCentroidSumX = 0.0;
         double scaledCentroidSumY = 0.0;
         double scaledCentroidSumZ = 0.0;
 
         final Iterator<Vector3D> it = vertices.iterator();
 
         final Vector3D startPt = it.next();
 
         Vector3D prevPt = it.next();
         Vector3D curPt;
 
         Vector3D prevVec = startPt.vectorTo(prevPt);
         Vector3D curVec;
 
         double triArea;
         Vector3D triCentroid;
         while (it.hasNext()) {
             curPt = it.next();
             curVec = startPt.vectorTo(curPt);
 
             triArea = 0.5 * prevVec.cross(curVec).norm();
             triCentroid = Vector3D.centroid(startPt, prevPt, curPt);
 
             areaSum += triArea;
 
             scaledCentroidSumX += triArea * triCentroid.getX();
             scaledCentroidSumY += triArea * triCentroid.getY();
             scaledCentroidSumZ += triArea * triCentroid.getZ();
 
             prevPt = curPt;
             prevVec = curVec;
         }
 
         if (areaSum > 0) {
             final double scale = 1 / areaSum;
             return Vector3D.of(
                         scale * scaledCentroidSumX,
                         scale * scaledCentroidSumY,
                         scale * scaledCentroidSumZ
                     );
         }
 
         // zero area, which means that the points are all linear; return the point midway between the
         // min and max points
         final Vector3D min = Vector3D.min(vertices);
         final Vector3D max = Vector3D.max(vertices);
 
         return min.lerp(max, 0.5);
     }
 
     /** {@inheritDoc} */
     @Override
     public Bounds3D getBounds() {
         return Bounds3D.from(getVertices());
     }
 
     /** {@inheritDoc} */
     @Override
     public RegionLocation classify(final Vector3D pt) {
         if (plane.contains(pt)) {
             final List<Vector3D> vertices = getVertices();
             final Precision.DoubleEquivalence precision = plane.getPrecision();
 
             final Vector3D normal = plane.getNormal();
             Vector3D edgeVec;
             Vector3D edgePlusVec;
             Vector3D testVec;
 
             Vector3D offsetVec;
             double offsetSign;
             double offset;
             int cmp;
 
             boolean onBoundary = false;
 
             Vector3D startVertex = vertices.get(vertices.size() - 1);
             for (final Vector3D nextVertex : vertices) {
 
                 edgeVec = startVertex.vectorTo(nextVertex);
                 edgePlusVec = edgeVec.cross(normal);
 
                 testVec = startVertex.vectorTo(pt);
 
                 offsetVec = testVec.reject(edgeVec);
                 offsetSign = Math.signum(offsetVec.dot(edgePlusVec));
                 offset = offsetSign * offsetVec.norm();
 
                 cmp = precision.compare(offset, 0.0);
                 if (cmp > 0) {
                     // the point is on the plus side (outside) of a boundary
                     return RegionLocation.OUTSIDE;
                 } else if (cmp == 0) {
                     onBoundary = true;
                 }
 
                 startVertex = nextVertex;
             }
 
             if (onBoundary) {
                 // the point is not on the outside of any boundaries and is directly on at least one
                 return RegionLocation.BOUNDARY;
             }
 
             // the point is on the inside of all boundaries
             return RegionLocation.INSIDE;
         }
 
         // the point is not on the plane
         return RegionLocation.OUTSIDE;
     }
 
     /** {@inheritDoc} */
     @Override
     public Vector3D closest(final Vector3D pt) {
         final Vector3D normal = plane.getNormal();
         final Precision.DoubleEquivalence precision = plane.getPrecision();
 
         final List<Vector3D> vertices = getVertices();
 
         final Vector3D projPt = plane.project(pt);
 
         Vector3D edgeVec;
         Vector3D edgePlusVec;
         Vector3D testVec;
 
         Vector3D offsetVec;
         double offsetSign;
         double offset;
         int cmp;
 
         Vector3D boundaryVec;
         double boundaryPointT;
         Vector3D boundaryPoint;
         double boundaryPointDistSq;
 
         double closestBoundaryPointDistSq = Double.POSITIVE_INFINITY;
         Vector3D closestBoundaryPoint = null;
 
         Vector3D startVertex = vertices.get(vertices.size() - 1);
         for (final Vector3D nextVertex : vertices) {
 
             edgeVec = startVertex.vectorTo(nextVertex);
             edgePlusVec = edgeVec.cross(normal);
 
             testVec = startVertex.vectorTo(projPt);
 
             offsetVec = testVec.reject(edgeVec);
             offsetSign = Math.signum(offsetVec.dot(edgePlusVec));
             offset = offsetSign * offsetVec.norm();
 
             cmp = precision.compare(offset, 0.0);
             if (cmp >= 0) {
                 // the point is on directly on the boundary or on its plus side; project the point onto the
                 // boundary, taking care to restrict the point to the actual extent of the boundary,
                 // and select the point with the shortest distance
                 boundaryVec = testVec.subtract(offsetVec);
                 boundaryPointT =
                         Math.signum(boundaryVec.dot(edgeVec)) * (boundaryVec.norm() / Vectors.checkedNorm(edgeVec));
                 boundaryPointT = Math.max(0, Math.min(1, boundaryPointT));
 
                 boundaryPoint = startVertex.lerp(nextVertex, boundaryPointT);
 
                 boundaryPointDistSq = boundaryPoint.distanceSq(projPt);
                 if (boundaryPointDistSq < closestBoundaryPointDistSq) {
                     closestBoundaryPointDistSq = boundaryPointDistSq;
                     closestBoundaryPoint = boundaryPoint;
                 }
             }
 
             startVertex = nextVertex;
         }
 
         if (closestBoundaryPoint != null) {
             // the point is on the outside of the polygon; return the closest point on the boundary
             return closestBoundaryPoint;
         }
 
         // the projected point is on the inside of all boundaries and therefore on the inside of the subset
         return projPt;
     }
 
     /** {@inheritDoc} */
     @Override
     public PlaneConvexSubset.Embedded getEmbedded() {
         final EmbeddingPlane embeddingPlane = plane.getEmbedding();
         final List<Vector2D> subspaceVertices = embeddingPlane.toSubspace(getVertices());
         final ConvexArea area = ConvexArea.convexPolygonFromVertices(subspaceVertices,
                 embeddingPlane.getPrecision());
 
         return new EmbeddedAreaPlaneConvexSubset(embeddingPlane, area);
     }
 
     /** {@inheritDoc} */
     @Override
     public Split<PlaneConvexSubset> split(final Hyperplane<Vector3D> splitter) {
         final Plane splitterPlane = (Plane) splitter;
         final List<Vector3D> vertices = getVertices();
 
         final int size = vertices.size();
 
         int minusPlusTransitionIdx = -1;
         Vector3D minusPlusInsertVertex = null;
 
         int plusMinusTransitionIdx = -1;
         Vector3D plusMinusInsertVertex = null;
 
         int transitionCount = 0;
 
         Vector3D curVertex;
         HyperplaneLocation curLoc;
 
         int lastSideIdx = -1;
         Vector3D lastSideVertex = null;
         HyperplaneLocation lastSideLoc = null;
 
         int lastBoundaryIdx = -1;
 
         for (int i = 0; i <= size || transitionCount == 1; ++i) {
 
             curVertex = vertices.get(i % size);
             curLoc = splitter.classify(curVertex);
 
             if (lastSideLoc == HyperplaneLocation.MINUS && curLoc == HyperplaneLocation.PLUS) {
                 // transitioned from minus side to plus side
                 minusPlusTransitionIdx = Math.max(lastSideIdx, lastBoundaryIdx);
                 ++transitionCount;
 
                 if (lastBoundaryIdx < 0) {
                     // no shared boundary point; compute a new vertex
                     minusPlusInsertVertex = splitterPlane.intersection(
                             Lines3D.fromPoints(lastSideVertex, curVertex, splitterPlane.getPrecision()));
                 }
             } else if (lastSideLoc == HyperplaneLocation.PLUS && curLoc == HyperplaneLocation.MINUS) {
                 // transitioned from plus side to minus side
                 plusMinusTransitionIdx = Math.max(lastSideIdx, lastBoundaryIdx);
                 ++transitionCount;
 
                 if (lastBoundaryIdx < 0) {
                     // no shared boundary point; compute a new vertex
                     plusMinusInsertVertex = splitterPlane.intersection(
                             Lines3D.fromPoints(lastSideVertex, curVertex, splitterPlane.getPrecision()));
                 }
             }
 
             if (curLoc == HyperplaneLocation.ON) {
                 lastBoundaryIdx = i;
             } else {
                 lastBoundaryIdx = -1;
 
                 lastSideIdx = i;
                 lastSideVertex = curVertex;
                 lastSideLoc = curLoc;
             }
         }
 
         if (minusPlusTransitionIdx > -1 && plusMinusTransitionIdx > -1) {
             // we've split; compute the vertex list for each side
             final List<Vector3D> minusVertices =  buildPolygonSplitVertexList(
                     plusMinusTransitionIdx, plusMinusInsertVertex,
                     minusPlusTransitionIdx, minusPlusInsertVertex, vertices);
             final List<Vector3D> plusVertices = buildPolygonSplitVertexList(
                     minusPlusTransitionIdx, minusPlusInsertVertex,
                     plusMinusTransitionIdx, plusMinusInsertVertex, vertices);
 
             // delegate back to the Planes factory methods to determine the concrete types
             // for each side of the split
             return new Split<>(
                     Planes.fromConvexPlanarVertices(plane, minusVertices),
                     Planes.fromConvexPlanarVertices(plane, plusVertices));
 
         } else if (lastSideLoc == HyperplaneLocation.PLUS) {
             // we lie entirely on the plus side of the splitter
             return new Split<>(null, this);
         } else if (lastSideLoc == HyperplaneLocation.MINUS) {
             // we lie entirely on the minus side of the splitter
             return new Split<>(this, null);
         }
 
         // we lie entirely on the splitter
         return new Split<>(null, null);
     }
 
     /** Internal method for building a vertex list for one side of a split result. The method is
      * designed to make the fewest allocations possible.
      * @param enterIdx the index of the vertex from {@code vertices} immediately before the polygon transitioned
      *      to being fully entered into this side of the split result. If no point from {@code vertices} lay
      *      directly on the splitting plane while entering this side and a new vertex had to be computed for the
      *      split result, then this index will be the last vertex on the opposite side of the split. If a vertex
      *      did lie directly on the splitting plane, then this index will point to that vertex.
      * @param newEnterPt the newly-computed point to be added as the first vertex in the split result; may
      *      be null if no such point exists
      * @param exitIdx the index of the vertex from {@code vertices} immediately before the polygon transitioned
      *      to being fully exited from this side of the split result. If no point from {@code vertices} lay
      *      directly on the splitting plane while exiting this side and a new vertex had to be computed for the
      *      split result, then this index will be the last vertex on the this side of the split. If a vertex did
      *      lie directly on the splitting plane, then this index will point to that vertex.
      * @param newExitPt the newly-computed point to be added as the last vertex in the split result; may
      *      be null if no such point exists
      * @param vertices the original list of vertices that this split result originated from; this list is
      *      not modified by this operation
      * @return the list of vertices for the split result
      */
     private List<Vector3D> buildPolygonSplitVertexList(final int enterIdx, final Vector3D newEnterPt,
             final int exitIdx, final Vector3D newExitPt, final List<? extends Vector3D> vertices) {
 
         final int size = vertices.size();
 
         final boolean hasNewEnterPt = newEnterPt != null;
         final boolean hasNewExitPt = newExitPt != null;
 
         final int startIdx = (hasNewEnterPt ? enterIdx + 1 : enterIdx) % size;
         final int endIdx = exitIdx % size;
 
         final boolean hasWrappedIndices = endIdx < startIdx;
 
         final int resultSize = (hasWrappedIndices ? endIdx + size : endIdx) - startIdx + 1;
         final List<Vector3D> result = new ArrayList<>(resultSize);
 
         if (hasNewEnterPt) {
             result.add(newEnterPt);
         }
 
         if (hasWrappedIndices) {
             result.addAll(vertices.subList(startIdx, size));
             result.addAll(vertices.subList(0, endIdx + 1));
         } else {
             result.addAll(vertices.subList(startIdx, endIdx + 1));
         }
 
         if (hasNewExitPt) {
             result.add(newExitPt);
         }
 
         return result;
     }
 
     /** {@inheritDoc} */
     @Override
     public String toString() {
         final StringBuilder sb = new StringBuilder();
         sb.append(getClass().getSimpleName())
             .append("[normal= ")
             .append(getPlane().getNormal())
             .append(", vertices= ")
             .append(getVertices())
             .append(']');
 
         return sb.toString();
     }
 }