Repository: williamfiset/algorithms
Issue: Cut polygon additional points

The [cut polygon](https://github.com/williamfiset/Algorithms/blob/master/Geometry/ConvexPolygonCutWithLineSegment.java) snippet seems to provide additional points when a cut operation is performed which probably shouldn't be there. 

For example, when the following runs the additional point (2,2) appears out of nowhere.

```java
    Pt[] squarePolygon = {new Pt(0, 0), new Pt(0, 4), new Pt(4, 0), new Pt(4, 4)};
    Pt p1 = new Pt(-1, -1);
    Pt p2 = new Pt(5, 5);

    Pt[] poly1 = cut(squarePolygon, p1, p2);
    Pt[] poly2 = cut(squarePolygon, p2, p1);

    System.out.println("First polygon:");
    for (Pt pt : poly1) System.out.println(pt);
    // Prints:
    // First polygon:
    // (4.0,4.0)
    // (0.0,0.0)
    // (0.0,4.0)
    // (2.0,2.0) <-- Probably should not be here?
    
    System.out.println("\\nSecond polygon:");
    for (Pt pt : poly2) System.out.println(pt);
    // Second polygon:
    // (4.0,4.0)
    // (0.0,0.0)
    // (2.0,2.0) <-- Probably should not be here?
    // (4.0,0.0)
```

@FinnLidbetter assigning you since made this snippet right? Perhaps you can offer some insight.

Changed files:
com/williamfiset/algorithms/geometry/ConvexPolygonCutWithLineSegment.java

diff --git a/com/williamfiset/algorithms/geometry/ConvexPolygonCutWithLineSegment.java b/com/williamfiset/algorithms/geometry/ConvexPolygonCutWithLineSegment.java
index cc75a61..df72ad7 100644
--- a/com/williamfiset/algorithms/geometry/ConvexPolygonCutWithLineSegment.java
+++ b/com/williamfiset/algorithms/geometry/ConvexPolygonCutWithLineSegment.java
@@ -1,13 +1,14 @@
 /**
- * This algorithm cuts a convex polygon with a line segment and returns the two resulting pieces.
+ * This algorithm cuts a ordered convex polygon with a line segment and returns the two resulting pieces.
  *
- * <p>Time Complexity: O(n)
+ * <p>Time Complexity: O(nlogn)
  *
  * @author Finn Lidbetter
  */
 package com.williamfiset.algorithms.geometry;
 
 import java.util.*;
+import java.lang.*; 
 
 public class ConvexPolygonCutWithLineSegment {
 
@@ -27,6 +28,29 @@ public class ConvexPolygonCutWithLineSegment {
       return "(" + x + "," + y + ")";
     }
   }
+  
+  
+  //sorts the points in CW direction.
+  public static List<Pt> sortCW(List<Pt> poly){
+      
+      int l = poly.size();
+      double centroidX = 0;
+      double centroidY = 0;
+      for(int i = 0; i<l; i++){
+          centroidX+= poly.get(i).x;
+          centroidY+= poly.get(i).y;
+      }
+      centroidX = centroidX/l;
+      centroidY = centroidY/l;
+      Pt center = new Pt(centroidX, centroidY);
+      
+      Collections.sort(poly, (a, b) -> {
+        double a1 = (Math.toDegrees(Math.atan2(a.x - center.x, a.y - center.y)) + 360) % 360;
+        double a2 = (Math.toDegrees(Math.atan2(b.x - center.x, b.y - center.y)) + 360) % 360;
+        return (int) (a1 - a2);
+    });
+    return poly;
+  }
 
   // Cuts a convex polygon by a specified line and returns one part
   // of the polygon (swapping the endpoints p1 and p2 of the line
@@ -61,14 +85,38 @@ public class ConvexPolygonCutWithLineSegment {
     double cross = bx * cy - by * cx;
     return cross < -EPS ? -1 : cross > EPS ? 1 : 0;
   }
+  
+  //takes Pt[] as an argument and returns List<Pt>
+  public static List<Pt> makeList(Pt[] squarePolygon){
+    List<Pt> list = new ArrayList<Pt>();
+    for (int i=0; i<squarePolygon.length; i++){
+        list.add(squarePolygon[i]);
+    }
+    return list;
+  }
+  
+  //takes List<Pt> as an argument and returns Pt[]
+  public static Pt[] makeArray(List<Pt> list){
+      int l = list.size();
+      Pt[] temp = new Pt[l];
+      for (int i=0; i<l; i++){
+        temp[i] = list.get(i);
+    }
+    return temp;
+  }
 
   // Example usage
   public static void main(String[] args) {
-
-    Pt[] squarePolygon = {new Pt(0, 0), new Pt(0, 4), new Pt(4, 0), new Pt(4, 4)};
+    
+    Pt[] squarePolygon = {new Pt(0, 0), new Pt(0, 4), new Pt(4, 0), new Pt(4, 4), new Pt(0, 2)};
     Pt p1 = new Pt(-1, -1);
     Pt p2 = new Pt(5, 5);
-
+    
+    int l = squarePolygon.length;
+    List list = makeList(squarePolygon);
+    list = sortCW(list);
+    squarePolygon = makeArray(list);
+    
     Pt[] poly1 = cut(squarePolygon, p1, p2);
     Pt[] poly2 = cut(squarePolygon, p2, p1);
 
@@ -76,18 +124,18 @@ public class ConvexPolygonCutWithLineSegment {
     for (Pt pt : poly1) System.out.println(pt);
     // Prints:
     // First polygon:
+    // (0.0,4.0)
     // (4.0,4.0)
     // (0.0,0.0)
-    // (0.0,4.0)
-    // (2.0,2.0) <-- Probably should not be here?
+    // (0.0,2.0)
 
     System.out.println("\\nSecond polygon:");
     for (Pt pt : poly2) System.out.println(pt);
+    //Prints:
     // Second polygon:
     // (4.0,4.0)
-    // (0.0,0.0)
-    // (2.0,2.0) <-- Probably should not be here?
     // (4.0,0.0)
+    // (0.0,0.0)
 
   }
 }