Instantly share code, notes, and snippets.

# KvanTTT/PolygonTriangulator.cs Created Oct 8, 2012

Short solution for splitting concave polygon on convex polygons or triangles with other utils (SelfIntersection checking).
 using System.Collections.Generic; using System.Drawing; public class PolygonTriangulator { /// /// Calculate list of convex polygons or triangles. /// /// Input polygon without self-intersections (it can be checked with SelfIntersection(). /// true: splitting on triangles; false: splitting on convex polygons. /// public static List> Triangulate(List Polygon, bool triangulate = false) { var result = new List>(); var tempPolygon = new List(Polygon); var convPolygon = new List(); int begin_ind = 0; int cur_ind; int begin_ind1; int N = Polygon.Count; int Range; if (Square(tempPolygon) < 0) tempPolygon.Reverse(); while (N >= 3) { while ((PMSquare(tempPolygon[begin_ind], tempPolygon[(begin_ind + 1) % N], tempPolygon[(begin_ind + 2) % N]) < 0) || (Intersect(tempPolygon, begin_ind, (begin_ind + 1) % N, (begin_ind + 2) % N) == true)) { begin_ind++; begin_ind %= N; } cur_ind = (begin_ind + 1) % N; convPolygon.Add(tempPolygon[begin_ind]); convPolygon.Add(tempPolygon[cur_ind]); convPolygon.Add(tempPolygon[(begin_ind + 2) % N]); if (triangulate == false) { begin_ind1 = cur_ind; while ((PMSquare(tempPolygon[cur_ind], tempPolygon[(cur_ind + 1) % N], tempPolygon[(cur_ind + 2) % N]) > 0) && ((cur_ind + 2) % N != begin_ind)) { if ((Intersect(tempPolygon, begin_ind, (cur_ind + 1) % N, (cur_ind + 2) % N) == true) || (PMSquare(tempPolygon[begin_ind], tempPolygon[(begin_ind + 1) % N], tempPolygon[(cur_ind + 2) % N]) < 0)) break; convPolygon.Add(tempPolygon[(cur_ind + 2) % N]); cur_ind++; cur_ind %= N; } } Range = cur_ind - begin_ind; if (Range > 0) { tempPolygon.RemoveRange(begin_ind + 1, Range); } else { tempPolygon.RemoveRange(begin_ind + 1, N - begin_ind - 1); tempPolygon.RemoveRange(0, cur_ind + 1); } N = tempPolygon.Count; begin_ind++; begin_ind %= N; result.Add(convPolygon); } return result; } public static int SelfIntersection(List polygon) { if (polygon.Count < 3) return 0; int High = polygon.Count - 1; PointF O = new PointF(); int i; for (i = 0; i < High; i++) { for (int j = i + 2; j < High; j++) { if (LineIntersect(polygon[i], polygon[i + 1], polygon[j], polygon[j + 1], ref O) == 1) return 1; } } for (i = 1; i < High - 1; i++) if (LineIntersect(polygon[i], polygon[i + 1], polygon[High], polygon[0], ref O) == 1) return 1; return -1; } public static float Square(List polygon) { float S = 0; if (polygon.Count >= 3) { for (int i = 0; i < polygon.Count - 1; i++) S += PMSquare((PointF)polygon[i], (PointF)polygon[i + 1]); S += PMSquare((PointF)polygon[polygon.Count - 1], (PointF)polygon[0]); } return S; } public int IsConvex(List Polygon) { if (Polygon.Count >= 3) { if (Square(Polygon) > 0) { for (int i = 0; i < Polygon.Count - 2; i++) if (PMSquare(Polygon[i], Polygon[i + 1], Polygon[i + 2]) < 0) return -1; if (PMSquare(Polygon[Polygon.Count - 2], Polygon[Polygon.Count - 1], Polygon[0]) < 0) return -1; if (PMSquare(Polygon[Polygon.Count - 1], Polygon[0], Polygon[1]) < 0) return -1; } else { for (int i = 0; i < Polygon.Count - 2; i++) if (PMSquare(Polygon[i], Polygon[i + 1], Polygon[i + 2]) > 0) return -1; if (PMSquare(Polygon[Polygon.Count - 2], Polygon[Polygon.Count - 1], Polygon[0]) > 0) return -1; if (PMSquare(Polygon[Polygon.Count - 1], Polygon[0], Polygon[1]) > 0) return -1; } return 1; } return 0; } static bool Intersect(List polygon, int vertex1Ind, int vertex2Ind, int vertex3Ind) { float s1, s2, s3; for (int i = 0; i < polygon.Count; i++) { if ((i == vertex1Ind) || (i == vertex2Ind) || (i == vertex3Ind)) continue; s1 = PMSquare(polygon[vertex1Ind], polygon[vertex2Ind], polygon[i]); s2 = PMSquare(polygon[vertex2Ind], polygon[vertex3Ind], polygon[i]); if (((s1 < 0) && (s2 > 0)) || ((s1 > 0) && (s2 < 0))) continue; s3 = PMSquare(polygon[vertex3Ind], polygon[vertex1Ind], polygon[i]); if (((s3 >= 0) && (s2 >= 0)) || ((s3 <= 0) && (s2 <= 0))) return true; } return false; } static float PMSquare(PointF p1, PointF p2) { return (p2.X * p1.Y - p1.X * p2.Y); } static float PMSquare(PointF p1, PointF p2, PointF p3) { return (p3.X - p1.X) * (p2.Y - p1.Y) - (p2.X - p1.X) * (p3.Y - p1.Y); } static int LineIntersect(PointF A1, PointF A2, PointF B1, PointF B2, ref PointF O) { float a1 = A2.Y - A1.Y; float b1 = A1.X - A2.X; float d1 = -a1 * A1.X - b1 * A1.Y; float a2 = B2.Y - B1.Y; float b2 = B1.X - B2.X; float d2 = -a2 * B1.X - b2 * B1.Y; float t = a2 * b1 - a1 * b2; if (t == 0) return -1; O.Y = (a1 * d2 - a2 * d1) / t; O.X = (b2 * d1 - b1 * d2) / t; if (A1.X > A2.X) { if ((O.X < A2.X) || (O.X > A1.X)) return 0; } else { if ((O.X < A1.X) || (O.X > A2.X)) return 0; } if (A1.Y > A2.Y) { if ((O.Y < A2.Y) || (O.Y > A1.Y)) return 0; } else { if ((O.Y < A1.Y) || (O.Y > A2.Y)) return 0; } if (B1.X > B2.X) { if ((O.X < B2.X) || (O.X > B1.X)) return 0; } else { if ((O.X < B1.X) || (O.X > B2.X)) return 0; } if (B1.Y > B2.Y) { if ((O.Y < B2.Y) || (O.Y > B1.Y)) return 0; } else { if ((O.Y < B1.Y) || (O.Y > B2.Y)) return 0; } return 1; } }

### crba233 commented Aug 19, 2017 • edited

 Just a heads up, in the function "Triangulate" you'll want to add a `convPolygon = new List();` at the beginning of the first while loop.