package org.newdawn.slick.geom;
   
   import javax.annotation.Nonnull;
   import javax.annotation.Nullable;
   import java.util.ArrayList;
   import java.util.List;
   
   /**
    * A set of utilities to play with geometry
   * 
   * @author kevin
   */
  class GeomUtil {
      /** The tolerance for determining changes and steps */
      private static final float EPSILON = 0.0001f;
      /** The tolerance for determining direction change */
      private static final float EDGE_SCALE = 1f;
      /** The maximum number of points returned by an operation - prevents full lockups */
      private static final int MAX_POINTS = 10000;
      /** The listener to notify of operations */
      private GeomUtilListener listener;
  
      /**
       * Subtract one shape from another - note this is experimental and doesn't
       * currently handle islands
       *
       * @param target The target to be subtracted from
       * @param missing The shape to subtract
       * @return The newly created shapes
       */
      @Nonnull
      public Shape[] subtract(Shape target, Shape missing) {
          target = target.transform(new Transform());
          missing = missing.transform(new Transform());
  
          int count = 0;
          for (int i=0;i<target.getPointCount();i++) {
              if (missing.contains(target.getPoint(i)[0], target.getPoint(i)[1])) {
                  count++;
              }
          }
  
          if (count == target.getPointCount()) {
              return new Shape[0];
          }
  
          if (!target.intersects(missing)) {
              return new Shape[] {target};
          }
  
          int found = 0;
          for (int i=0;i<missing.getPointCount();i++) {
              if (target.contains(missing.getPoint(i)[0], missing.getPoint(i)[1])) {
                  if (!onPath(target, missing.getPoint(i)[0], missing.getPoint(i)[1])) {
                      found++;
                  }
              }
          }
          for (int i=0;i<target.getPointCount();i++) {
              if (missing.contains(target.getPoint(i)[0], target.getPoint(i)[1])) {
                  if (!onPath(missing, target.getPoint(i)[0], target.getPoint(i)[1]))
                  {
                      found++;
                  }
              }
          }
  
          if (found < 1) {
              return new Shape[] {target};
          }
  
          return combine(target, missing, true);
      }
  
      /**
       * Check if the given point is on the path
       *
       * @param path The path to check
       * @param x The x coordinate of the point to check
       * @param y The y coordiante of teh point to check
       * @return True if the point is on the path
       */
      private boolean onPath(@Nonnull Shape path, float x, float y) {
          for (int i=0;i<path.getPointCount()+1;i++) {
              int n = rationalPoint(path, i+1);
              Line line = getLine(path, rationalPoint(path, i), n);
              if (line.distance(new Vector2f(x,y)) < EPSILON*100) {
                  return true;
              }
          }
  
          return false;
      }
  
      /**
       * Set the listener to be notified of geometry based operations
       *
       * @param listener The listener to be notified of geometry based operations
       */
     public void setListener(GeomUtilListener listener) {
         this.listener = listener;
     }
 
     /**
      * Join to shapes together. Note that the shapes must be touching
      * for this method to work.
      *
      * @param target The target shape to union with
      * @param other The additional shape to union
      * @return The newly created shapes
      */
     @Nonnull
     public Shape[] union(Shape target, Shape other) {
         target = target.transform(new Transform());
         other = other.transform(new Transform());
 
         if (!target.intersects(other)) {
             return new Shape[] {target, other};
         }
 
         // handle the case where intersects is true but really we're talking
         // about edge points
         boolean touches = false;
         int buttCount = 0;
         for (int i=0;i<target.getPointCount();i++) {
             if (other.contains(target.getPoint(i)[0], target.getPoint(i)[1])) {
                 if (!other.hasVertex(target.getPoint(i)[0], target.getPoint(i)[1])) {
                     touches = true;
                     break;
                 }
             }
             if (other.hasVertex(target.getPoint(i)[0], target.getPoint(i)[1])) {
                 buttCount++;
             }
         }
         for (int i=0;i<other.getPointCount();i++) {
             if (target.contains(other.getPoint(i)[0], other.getPoint(i)[1])) {
                 if (!target.hasVertex(other.getPoint(i)[0], other.getPoint(i)[1])) {
                     touches = true;
                     break;
                 }
             }
         }
 
         if ((!touches) && (buttCount < 2)) {
             return new Shape[] {target, other};
         }
 
         // so they are definitely touching, consider the union
         return combine(target, other, false);
     }
 
     /**
      * Perform the combination
      *
      * @param target The target shape we're updating
      * @param other The other shape in the operation
      * @param subtract True if it's a subtract operation, otherwise it's union
      * @return The set of shapes produced
      */
     @Nonnull
     private Shape[] combine(@Nonnull Shape target, @Nonnull Shape other, boolean subtract) {
         if (subtract) {
             List<Shape> shapes = new ArrayList<>();
             List<Vector2f> used = new ArrayList<>();
 
             // remove any points that are contianed in the shape we're removing, these
             // are implicitly used
             for (int i=0;i<target.getPointCount();i++) {
                 float[] point = target.getPoint(i);
                 if (other.contains(point[0], point[1])) {
                     used.add(new Vector2f(point[0], point[1]));
                     if (listener != null) {
                         listener.pointExcluded(point[0], point[1]);
                     }
                 }
             }
 
             for (int i=0;i<target.getPointCount();i++) {
                 float[] point = target.getPoint(i);
                 Vector2f pt = new Vector2f(point[0], point[1]);
 
                 if (!used.contains(pt)) {
                     Shape result = combineSingle(target, other, true, i);
                     shapes.add(result);
                     for (int j=0;j<result.getPointCount();j++) {
                         float[] kpoint = result.getPoint(j);
                         Vector2f kpt = new Vector2f(kpoint[0], kpoint[1]);
                         used.add(kpt);
                     }
                 }
             }
 
             return (Shape[]) shapes.toArray();
         } else {
             for (int i=0;i<target.getPointCount();i++) {
                 if (!other.contains(target.getPoint(i)[0], target.getPoint(i)[1])) {
                     if (!other.hasVertex(target.getPoint(i)[0], target.getPoint(i)[1])) {
                         Shape shape = combineSingle(target, other, false, i);
                         return new Shape[] {shape};
                     }
                 }
             }
 
             return new Shape[] {other};
         }
     }
 
     /**
      * Combine two shapes
      *
      * @param target The target shape
      * @param missing The second shape to apply
      * @param subtract True if we should subtract missing from target, otherwise union
      * @param start The point to start at
      * @return The newly created shape
      */
     @Nonnull
     private Shape combineSingle(Shape target, Shape missing, boolean subtract, int start) {
         Shape current = target;
         Shape other = missing;
         int point = start;
         int dir = 1;
 
         Polygon poly = new Polygon();
         boolean first = true;
 
         int loop = 0;
 
         // while we've not reached the same point
         float px = current.getPoint(point)[0];
         float py = current.getPoint(point)[1];
 
         while (!poly.hasVertex(px, py) || (first) || (current != target)) {
             first = false;
             loop++;
             if (loop > MAX_POINTS) {
                 break;
             }
 
             // add the current point to the result shape
             poly.addPoint(px,py);
             if (listener != null) {
                 listener.pointUsed(px,py);
             }
 
             // if the line between the current point and the next one intersect the
             // other shape work out where on the other shape and start traversing it's
             // path instead
             Line line = getLine(current, px, py, rationalPoint(current, point+dir));
             HitResult hit = intersect(other, line);
 
             if (hit != null) {
                 Line hitLine = hit.line;
                 Vector2f pt = hit.pt;
                 px = pt.x;
                 py = pt.y;
 
                 if (listener != null) {
                     listener.pointIntersected(px,py);
                 }
 
                 if (other.hasVertex(px, py)) {
                     point = other.indexOf(pt.x,pt.y);
                     dir = 1;
                     px = pt.x;
                     py = pt.y;
 
                     Shape temp = current;
                     current = other;
                     other = temp;
                     continue;
                 }
 
                 float dx = hitLine.getDX() / hitLine.length();
                 float dy = hitLine.getDY() / hitLine.length();
                 dx *= EDGE_SCALE;
                 dy *= EDGE_SCALE;
 
                 if (current.contains(pt.x + dx, pt.y + dy)) {
                     // the point is the next one, we need to take the first and traverse
                     // the path backwards
                     if (subtract) {
                         if (current == missing) {
                             point = hit.p2;
                             dir = -1;
                         } else {
                             point = hit.p1;
                             dir = 1;
                         }
                     } else {
                         if (current == target) {
                             point = hit.p2;
                             dir = -1;
                         } else {
                             point = hit.p2;
                             dir = -1;
                         }
                     }
 
                     // swap the shapes over, we'll traverse the other one
                     Shape temp = current;
                     current = other;
                     other = temp;
                 } else if (current.contains(pt.x - dx, pt.y - dy)) {
                     if (subtract) {
                         if (current == target) {
                             point = hit.p2;
                             dir = -1;
                         } else {
                             point = hit.p1;
                             dir = 1;
                         }
                     } else {
                         if (current == missing) {
                             point = hit.p1;
                             dir = 1;
                         } else {
                             point = hit.p1;
                             dir = 1;
                         }
                     }
 
                     // swap the shapes over, we'll traverse the other one
                     Shape temp = current;
                     current = other;
                     other = temp;
                 } else {
                     // give up
                     if (subtract) {
                         break;
                     } else {
                         point = hit.p1;
                         dir = 1;
                         Shape temp = current;
                         current = other;
                         other = temp;
 
                         point = rationalPoint(current, point+dir);
                         px = current.getPoint(point)[0];
                         py = current.getPoint(point)[1];
                     }
                 }
             } else {
                 // otherwise just move to the next point in the current shape
                 point = rationalPoint(current, point+dir);
                 px = current.getPoint(point)[0];
                 py = current.getPoint(point)[1];
             }
         }
 
         poly.addPoint(px,py);
         if (listener != null) {
             listener.pointUsed(px,py);
         }
 
         return poly;
     }
 
     /**
      * Intersect a line with a shape
      *
      * @param shape The shape to compare
      * @param line The line to intersect against the shape
      * @return The result describing the intersection or null if none
      */
     @Nullable
     HitResult intersect(@Nonnull Shape shape, @Nonnull Line line) {
         float distance = Float.MAX_VALUE;
         HitResult hit = null;
 
         for (int i=0;i<shape.getPointCount();i++) {
             int next = rationalPoint(shape, i+1);
             Line local = getLine(shape, i, next);
 
             Vector2f pt = line.intersect(local, true);
             if (pt != null) {
                 float newDis = pt.distance(line.getStart());
                 if ((newDis < distance) && (newDis > EPSILON)) {
                     hit = new HitResult();
                     hit.pt = pt;
                     hit.line = local;
                     hit.p1 = i;
                     hit.p2 = next;
                     distance = newDis;
                 }
             }
         }
 
         return hit;
     }
 
     /**
      * Rationalise a point in terms of a given shape
      *
      * @param shape The shape
      * @param p The index of the point
      * @return The index that is rational for the shape
      */
     private static int rationalPoint(@Nonnull Shape shape, int p) {
         while (p < 0) {
             p += shape.getPointCount();
         }
         while (p >= shape.getPointCount()) {
             p -=  shape.getPointCount();
         }
 
         return p;
     }
 
     /**
      * Get a line between two points in a shape
      *
      * @param shape The shape
      * @param s The index of the start point
      * @param e The index of the end point
      * @return The line between the two points
      */
     @Nonnull
     Line getLine(@Nonnull Shape shape, int s, int e) {
         float[] start = shape.getPoint(s);
         float[] end = shape.getPoint(e);
 
         Line line = new Line(start[0],start[1],end[0],end[1]);
         return line;
     }
 
     /**
      * Get a line between two points in a shape
      *
      * @param shape The shape
      * @param sx The x coordinate of the start point
      * @param sy The y coordinate of the start point
      * @param e The index of the end point
      * @return The line between the two points
      */
     @Nonnull
     Line getLine(@Nonnull Shape shape, float sx, float sy, int e) {
         float[] end = shape.getPoint(e);
 
         Line line = new Line(sx,sy,end[0],end[1]);
         return line;
     }
 
     /**
      * A lightweigtht description of a intersection between a shape and
      * line.
      */
     public class HitResult {
         /** The line on the target shape that intersected */
         public Line line;
         /** The index of the first point on the target shape that forms the line */
         public int p1;
         /** The index of the second point on the target shape that forms the line */
         public int p2;
         /** The position of the intersection */
         @Nullable
         public Vector2f pt;
     }
 }