//Apply a polygon clipper operation on subject vertices using cut vertices
    public static List<Vector2[]> ClipPoly(Vector2[] subject, Vector2[] cut, ClipType operation)
    {
        List<Vector2[]> cutPolygons = new List<Vector2[]>();

        Paths subj = new Paths(1);
        subj.Add(Vector2ToIntList(subject));

        Paths clip = new Paths(1);
        clip.Add(Vector2ToIntList(cut));

        Paths solution = new Paths();

        Clipper c = new Clipper();
        c.AddPaths(subj, PolyType.ptSubject, true);
        c.AddPaths(clip, PolyType.ptClip, true);

        c.Execute(operation,solution,
              PolyFillType.pftEvenOdd, PolyFillType.pftEvenOdd);

        /*
        for(int i = 0; i<solution.Count; i++){
        if( Mathf.Abs((float)Clipper.Area(solution[i])) > ignoreArea){
            cutPolygons.Add( IntListToVector2( solution[i] ));
        }
        }
        */
        return IntListsToVector2(solution);
    }

    public static List<List<Vector2>> clip(List<Vector2> boundary, List<Vector2> region)
    {
        Polygons boundaryPoly = createPolygons(boundary);
        Polygons regionPoly = createPolygons(region);

        //clip triangular polygon against the boundary polygon
        Polygons result = new Polygons();
        Clipper c = new Clipper();
        c.AddPaths(regionPoly, PolyType.ptClip, true);
        c.AddPaths(boundaryPoly, PolyType.ptSubject, true);
        c.Execute(ClipType.ctIntersection, result, PolyFillType.pftEvenOdd, PolyFillType.pftEvenOdd);

        List<List<Vector2>> clippedPolygons = new List<List<Vector2>>();

        foreach (Polygon poly in result)
        {
            List<Vector2> clippedPoly = new List<Vector2>();
            foreach (IntPoint p in poly)
            {
                clippedPoly.Add(new Vector2(p.X, p.Y) / multiplier);
            }
            clippedPolygons.Add(clippedPoly);

        }
        return clippedPolygons;
    }

    public static XYPolygon GetIntersection(XYPolygon pol1, XYPolygon pol2)
    {



      List<List<IntPoint>> subj = new List<List<IntPoint>>();
  subj.Add(new List<IntPoint>(pol1.Points.Count));
      foreach(var p in pol1.Points)
        subj[0].Add(new IntPoint(p.X, p.Y));


      List<List<IntPoint>> clip = new List<List<IntPoint>>();
      clip.Add(new List<IntPoint>(pol2.Points.Count));
  foreach (var p in pol2.Points)
    clip[0].Add(new IntPoint(p.X, p.Y));


  List<List<IntPoint>> solution = new List<List<IntPoint>>();

	Clipper c = new Clipper();
	c.AddPaths(subj, PolyType.ptSubject, true);
	c.AddPaths(clip, PolyType.ptClip, true);
	c.Execute(ClipType.ctIntersection, solution, 
	  PolyFillType.pftEvenOdd, PolyFillType.pftEvenOdd);

  XYPolygon ToReturn = new XYPolygon();
  if (solution.Count > 0) 
  foreach (var p in solution[0])
    ToReturn.Points.Add(new XYPoint(p.X,p.Y));

          return ToReturn;
    }

 public List<List<IntPoint>> Run (List<List<IntPoint>> subject, double scale)
 {
   var c = ToClipper (scale, clip);
   var clipper = new Clipper ();
   clipper.AddPaths (subject, PolyType.ptSubject, subjectClosed);
   clipper.AddPaths (c, PolyType.ptClip, true);
   var solution = new List<List<IntPoint>> ();
   clipper.Execute (type, solution, subjectFill, clipFill);
   return solution;
 }

        public void DoCircleClipping(Vector2 pos, float radius)
        {
            List<VertexPosition[]> shape_old = shape;
            bool isCleared = false;
            int sc = 0;
            for (sc = 0; sc < shape_old.Count; sc++)
            {
                ClippingPolygons subj = new ClippingPolygons(1);
                subj.Add(new ClippingPolygon(shape_old[sc].Length));
                foreach (VertexPosition point in shape_old[sc])
                {
                    subj[0].Add(new IntPoint((int)((point.Position.X) * accuracy), (int)((point.Position.Y) * accuracy)));
                }

                ClippingPolygons clip = new ClippingPolygons(1);
                clip.Add(new ClippingPolygon());
                for (int alpha = 0; alpha < 360; alpha += 10)
                {
                    clip[0].Add(new IntPoint((int)(((Math.Sin((alpha) * Math.PI / 180.0) * radius) + pos.X) * accuracy), (int)(((Math.Cos((alpha) * Math.PI / 180.0) * radius) + pos.Y) * accuracy)));
                    //log.Log(pos.ToString());
                }

                ClippingPolygons solution = new ClippingPolygons();

                Clipper c = new Clipper();
                c.AddPolygons(subj, PolyType.ptSubject);
                c.AddPolygons(clip, PolyType.ptClip);

                if (c.Execute(ClipType.ctDifference, solution, PolyFillType.pftEvenOdd, PolyFillType.pftEvenOdd))
                {
                    if (!isCleared)
                    {
                        shape = new List<VertexPosition[]>();
                        drawer.Clear();
                        isCleared = true;
                    }

                    for (int f = 0; f < solution.Count; f++)
                    {

                        shape.Add(new VertexPosition[solution[f].Count]);
                        drawer.Add(new ChunkDrawer(ref log));

                        for (int i = 0; i < solution[f].Count; i++)
                        {

                            shape[shape.Count-1][i] = new VertexPosition(solution[f][i].X / accuracy, solution[f][i].Y / accuracy, 0);
                        }
                        drawer[shape.Count-1].BufferVertices(shape[shape.Count - 1]);
                    }

                }
            }
        }

    List<IntPoint> GetArea(Mesh mesh)
    {
        int[] triangles = mesh.triangles;
        Vector3[] vertices = mesh.vertices;

        List<Vector2> list = new List<Vector2>();

        //Debug.Log("ver count: " + vertices.Length + " triangle: " + triangles.Length);

        float y = float.MinValue;
        for(int i=0; i < triangles.Length; i = i+3){
            Vector3 p0 = vertices[triangles[i]];
            Vector3 p1 = vertices[triangles[i+1]];
            Vector3 p2 = vertices[triangles[i+2]];

            if(Approximately(p0.y, p1.y) && Approximately(p0.y, p2.y)){
                //Debug.Log(string.Format("({0}, {1}, {2})", p0, p1, p2));

                if(y == float.MinValue){
                    y = p0.y;
                }

                if(Approximately(p0.y, y)){
                    list.Add(new Vector2(p0.x, p0.z));
                    list.Add(new Vector2(p1.x, p1.z));
                    list.Add(new Vector2(p2.x, p2.z));
                }
            }
        }

        //Debug.Log("list: " + list.Count);

        List<List<IntPoint>> paths = new List<List<IntPoint>>();
        for(int i=0; i < list.Count; i = i+3){
            List<IntPoint> path = new List<IntPoint>();

            for(int j=0; j < 3; j++){
                path.Add(new IntPoint(list[i+j].x * clipScalling, list[i+j].y * clipScalling));
            }

            paths.Add(path);
        }

        Clipper clipper = new Clipper();

        List<List<IntPoint>> solution = new List<List<IntPoint>>();
        clipper.AddPaths(paths, PolyType.ptSubject, true);
        clipper.Execute(ClipType.ctUnion, solution);

        if(solution.Count > 0){
            return solution[0];
        }

        return null;
    }

 public double RelativeAreaDiff (List<List<IntPoint>> actual, List<List<IntPoint>>expected)
 {
   var expectedArea = expected.Sum (path => Clipper.Area (path));
   var difference = new List<List<IntPoint>> ();
   var clipper = new Clipper ();
   clipper.AddPaths (actual, PolyType.ptSubject, true);
   clipper.AddPaths (expected, PolyType.ptClip, true);
   clipper.Execute (ClipType.ctXor, difference, PolyFillType.pftEvenOdd, PolyFillType.pftEvenOdd);
   var differenceArea = difference.Sum (path => Clipper.Area (path));
   return Math.Abs (differenceArea) / Math.Abs (expectedArea);
 }

 // perform xor
 public static Paths ClipperXor(this Polygon clip, Polygon subject)
 {
     var subj = new Paths();
     subj.Add(subject.ToClipperPath());
     var clp = new Paths();
     clp.Add(clip.ToClipperPath());
     var result = new Paths();
     var c = new Clipper();
     c.Execute(ClipType.ctXor, result, PolyFillType.pftPositive, PolyFillType.pftPositive);
     return result;
 }

        /// <summary>
        /// Checks if polygons are intersecting
        /// </summary>
        /// <param name="p1">Subject polygon</param>
        /// <param name="p2">Clip polygon(s)</param>
        /// <returns>true if intersects</returns>
        public static bool IsIntersects(Paths p1, params Paths[] p2)
        {
            Clipper c = new Clipper();
            Paths solution = new Paths();
            c.AddPaths(p1, PolyType.ptSubject, true);

            for(int i = 0; i < p2.Length; i++)
                c.AddPaths(p2[i], PolyType.ptClip, true);

            c.Execute(ClipType.ctIntersection, solution, PolyFillType.pftEvenOdd, PolyFillType.pftEvenOdd);

            return solution.Count != 0;
        }

    public static Vector3[] MeshDifference(Vector3[] mesh1, Vector3[] mesh2)
    {
        List<IntPoint> subj = MeshToPath3D(mesh1);
        List<IntPoint> clip = MeshToPath3D(mesh2);
        List<List<IntPoint>> solution = new List<List<IntPoint>>();

        Clipper c = new Clipper();
        c.AddPath(subj, PolyType.ptSubject, true);
        c.AddPath(clip, PolyType.ptClip, true);
        c.Execute(ClipType.ctDifference, solution,
          PolyFillType.pftEvenOdd, PolyFillType.pftEvenOdd);

        return PathToMesh3D(solution[0]);
    }

 // perform union on a list of polygons
 public static Paths ClipperUnion(this List<Polygon> polygons)
 {
     var subj = new Paths(polygons.Count);
     var clip = new Paths(polygons.Count);
     foreach (var polygon in polygons)
     {
         subj.Add(polygon.ToClipperPath());
         clip.Add(polygon.ToClipperPath());
     }
     var solution = new Paths();
     var c = new Clipper();
     c.AddPaths(subj, PolyType.ptSubject, true);
     c.AddPaths(clip, PolyType.ptClip, true);
     c.Execute(ClipType.ctUnion, solution, PolyFillType.pftPositive, PolyFillType.pftPositive);
     return solution;
 }

 public static List<List<IntPoint>> ClipPolygons(List<Polygon> polygons)
 {
     var subj = new List<List<IntPoint>>(polygons.Count);
     var clip = new List<List<IntPoint>>(polygons.Count);
     foreach (var polygon in polygons)
     {
         subj.Add(polygon.ToClipperPath());
         clip.Add(polygon.ToClipperPath());
     }
     var solution = new List<List<IntPoint>>();
     var c = new Clipper();
     c.AddPaths(subj, PolyType.ptSubject, true);
     c.AddPaths(clip, PolyType.ptClip, true);
     c.Execute(ClipType.ctUnion, solution, PolyFillType.pftPositive, PolyFillType.pftEvenOdd);
     return solution;
 }

        public static List<Vector2> Add(this Shape shape, Shape secondShape, Action<Shape> completed)
        {
            List<Vector2> points = new List<Vector2>();

            Clipper c = new Clipper();

            List<List<IntPoint>> subj = new List<List<IntPoint>>();
            List<List<IntPoint>> clip = new List<List<IntPoint>>();
            List<List<IntPoint>> solution = new List<List<IntPoint>>();
            List<IntPoint> p1 = new List<IntPoint>();
            List<IntPoint> p2 = new List<IntPoint>();
            int i = 0, l = shape.Points.Length;
            Vector2 pos = shape.BuiltGameObject.transform.position;
            for(;i<l;++i)
            {
                IntPoint ip = new IntPoint(shape.Points[i].x + pos.x,shape.Points[i].y + pos.y);
                p1.Add(ip);
            }
            p1.Add(p1[0]);

            pos = secondShape.BuiltGameObject.transform.position;
            i = 0; l = secondShape.Points.Length;
            for(;i<l;++i)
            {
                IntPoint ip = new IntPoint(secondShape.Points[i].x + pos.x,secondShape.Points[i].y + pos.y);
                p2.Add(ip);
            }
            p2.Add(p2[0]);

            subj.Add(p1);
            clip.Add(p2);

            c.AddPaths(subj,PolyType.ptSubject,true);
            c.AddPaths(clip,PolyType.ptClip,true);
            c.Execute(ClipType.ctUnion,solution);

            i = 0; l = solution[0].Count;
            for(;i<l;++i)
            {
                float x = System.Convert.ToSingle(solution[0][i].X);
                float y = System.Convert.ToSingle(solution[0][i].Y);
                points.Add(new Vector2(x,y));
            }

            Mesh2D.Instance.ReBuild(shape.BuiltGameObject,points,completed,shape.Col);
            return points;
        }

        public List<Polygon> Clip(Polygon p1, Polygon p2, OpType operation)
        {
            List<IntPoint> pol1 = new List<IntPoint>();
            List<IntPoint> pol2 = new List<IntPoint>();
            List<List<IntPoint>> res = new List<List<IntPoint>>();

            foreach (Point point in p1.Points) {
                pol1.Add(new IntPoint(point.X, point.Y));
            }
            foreach (Point point in p2.Points) {
                pol2.Add(new IntPoint(point.X, point.Y));
            }

            Clipper clipper = new Clipper();
            clipper.AddPolygon(pol1, PolyType.ptSubject);
            clipper.AddPolygon(pol2, PolyType.ptClip);

            switch (operation) {
                case OpType.Difference:
                    clipper.Execute(ClipType.ctDifference, res);
                    break;
                case OpType.Intersection:
                    clipper.Execute(ClipType.ctIntersection, res);
                    break;
                case OpType.Union:
                    clipper.Execute(ClipType.ctUnion, res);
                    break;
                case OpType.Xor:
                    clipper.Execute(ClipType.ctXor, res);
                    break;
            }
            List<Polygon> ret = new List<Polygon>();

            foreach (var poly in res) {
                Polygon pol = new Polygon() { Points = new List<Point>() };

                foreach (var poi in poly) {
                    pol.Points.Add(new Point() { X = poi.X, Y = poi.Y });
                }

                ret.Add(pol);
            }
            return ret;
        }

		private PathStorage CombinePaths(IVertexSource a, IVertexSource b, ClipType clipType)
		{
			List<List<IntPoint>> aPolys = VertexSourceToClipperPolygons.CreatePolygons(a);
			List<List<IntPoint>> bPolys = VertexSourceToClipperPolygons.CreatePolygons(b);

			Clipper clipper = new Clipper();

			clipper.AddPaths(aPolys, PolyType.ptSubject, true);
			clipper.AddPaths(bPolys, PolyType.ptClip, true);

			List<List<IntPoint>> intersectedPolys = new List<List<IntPoint>>();
			clipper.Execute(clipType, intersectedPolys);

			PathStorage output = VertexSourceToClipperPolygons.CreatePathStorage(intersectedPolys);

			output.Add(0, 0, ShapePath.FlagsAndCommand.CommandStop);

			return output;
		}

        public void DoCircleClipping(Vector2 pos, float radius)
        {
            ClippingPolygons subj = new ClippingPolygons(1);
            subj.Add(new ClippingPolygon(shape.Length));
            foreach(VertexPosition point in shape){
                subj[0].Add(new IntPoint((int)((point.Position.X) * accuracy), (int)((point.Position.Y) * accuracy)));
            }

            ClippingPolygons clip = new ClippingPolygons(1);
            clip.Add(new ClippingPolygon());
            for (int alpha = 0; alpha < 360; alpha += 10)
            {
                clip[0].Add(new IntPoint((int)(((Math.Sin((alpha) * Math.PI / 180.0) * radius)+pos.X) * accuracy), (int)(((Math.Cos((alpha) * Math.PI / 180.0) * radius)+pos.Y) * accuracy)));
                //log.Log(pos.ToString());
            }

            ClippingPolygons solution = new ClippingPolygons();

            Clipper c = new Clipper();
            c.AddPolygons(subj, PolyType.ptSubject);
            c.AddPolygons(clip, PolyType.ptClip);

            if (c.Execute(ClipType.ctDifference, solution, PolyFillType.pftEvenOdd, PolyFillType.pftEvenOdd))
            {

                for (int f = 0; f < solution.Count; f++)
                {
                    if (f == 0)
                    {
                        shape = new VertexPosition[solution[f].Count];
                        for (int i = 0; i < solution[f].Count; i++)
                        {

                            shape[i] = new VertexPosition(solution[f][i].X / accuracy, solution[f][i].Y / accuracy, 0);
                        }
                    }

                }
            }
            BufferVertices(ref shape);
        }

        public void Clip(double x0, double x1, double y0, double y1)
        {
            var p00 = new Point3d(x0, y0, 0.0);
            var p01 = new Point3d(x0, y1, 0.0);
            var p11 = new Point3d(x1, y1, 0.0);
            var p10 = new Point3d(x1, y0, 0.0);

            var clip = new[] { p00, p10, p11, p01, p00 }.ToPolygon(Plane.WorldXY, Unit);

            var clipper = new Clipper();

            clipper.AddPaths(Polygons, PolyType.ptSubject, true);
            clipper.AddPath(clip, PolyType.ptClip, true);

            var solution = new List<List<IntPoint>>();

            clipper.Execute(ClipType.ctIntersection, solution, PolyFillType.pftEvenOdd, PolyFillType.pftNonZero);

            Polygons = solution;
            Curves = Polygons.ToCurves(Plane, Unit);
        }

		public static void GenerateLinePaths(Polygons polygonToInfill, ref Polygons infillLinesToPrint, int lineSpacing, int infillExtendIntoPerimeter_um, double rotation, long rotationOffset = 0)
		{
			if (polygonToInfill.Count > 0)
			{
				Polygons outlines = polygonToInfill.Offset(infillExtendIntoPerimeter_um);
				if (outlines.Count > 0)
				{
					PointMatrix matrix = new PointMatrix(-(rotation + 90)); // we are rotating the part so we rotate by the negative so the lines go the way we expect

					outlines.ApplyMatrix(matrix);

					Aabb boundary = new Aabb(outlines);

					boundary.min.X = ((boundary.min.X / lineSpacing) - 1) * lineSpacing - rotationOffset;
					int xLineCount = (int)((boundary.max.X - boundary.min.X + (lineSpacing - 1)) / lineSpacing);
					Polygons unclipedPatern = new Polygons();

					long firstX = boundary.min.X / lineSpacing * lineSpacing;
					for (int lineIndex = 0; lineIndex < xLineCount; lineIndex++)
					{
						Polygon line = new Polygon();
						line.Add(new IntPoint(firstX + lineIndex * lineSpacing, boundary.min.Y));
						line.Add(new IntPoint(firstX + lineIndex * lineSpacing, boundary.max.Y));
						unclipedPatern.Add(line);
					}

					PolyTree ret = new PolyTree();
					Clipper clipper = new Clipper();
					clipper.AddPaths(unclipedPatern, PolyType.ptSubject, false);
					clipper.AddPaths(outlines, PolyType.ptClip, true);
					clipper.Execute(ClipType.ctIntersection, ret, PolyFillType.pftPositive, PolyFillType.pftEvenOdd);

					Polygons newSegments = Clipper.OpenPathsFromPolyTree(ret);
					PointMatrix inversematrix = new PointMatrix((rotation + 90));
					newSegments.ApplyMatrix(inversematrix);

					infillLinesToPrint.AddRange(newSegments);
				}
			}
		}

        public JsonResult GetBySponsor(ObjectId id)
        {
            var spots = Context.SponsorSpots.GetSpotsBySponsors(id);

            Clipper clipper = new Clipper();
            var polygons = new List<List<IntPoint>>();
            var scale = 100000000.0;

            foreach (var spot in spots)
            {
                var polygon = new List<IntPoint>();

                foreach (var coord in spot.SpotShape)
                {
                    polygon.Add(new IntPoint(coord.Longitude * scale, coord.Latitude * scale));
                }
                polygons.Add(polygon);
            }

            var solution = new List<List<IntPoint>>();

            clipper.AddPaths(polygons, PolyType.ptSubject, true);
            clipper.Execute(ClipType.ctUnion, solution,
                PolyFillType.pftNonZero, PolyFillType.pftNonZero);

            var results = new List<Spot>();

            foreach (var shape in solution)
            {
                var resultShape = new Spot();
                foreach (var item in shape)
                {
                    resultShape.SpotShape.Add(new Coordinate { Latitude = item.Y / scale, Longitude = item.X / scale });
                }
                results.Add(resultShape);
            }

            return Json(new { success = true, results = results }, JsonRequestBehavior.AllowGet);
        }

		private PathStorage CombinePaths(IVertexSource a, IVertexSource b, ClipType clipType)
		{
			List<List<IntPoint>> aPolys = CreatePolygons(a);
			List<List<IntPoint>> bPolys = CreatePolygons(b);

			Clipper clipper = new Clipper();

			clipper.AddPaths(aPolys, PolyType.ptSubject, true);
			clipper.AddPaths(bPolys, PolyType.ptClip, true);

			List<List<IntPoint>> intersectedPolys = new List<List<IntPoint>>();
			clipper.Execute(clipType, intersectedPolys);

			PathStorage output = new PathStorage();

			foreach (List<IntPoint> polygon in intersectedPolys)
			{
				bool first = true;
				foreach (IntPoint point in polygon)
				{
					if (first)
					{
						output.Add(point.X / 1000.0, point.Y / 1000.0, ShapePath.FlagsAndCommand.CommandMoveTo);
						first = false;
					}
					else
					{
						output.Add(point.X / 1000.0, point.Y / 1000.0, ShapePath.FlagsAndCommand.CommandLineTo);
					}
				}

				output.ClosePolygon();
			}

			output.Add(0, 0, ShapePath.FlagsAndCommand.CommandStop);

			return output;
		}