Point in polygon and triangulation
Decide whether a point is inside a room by counting crossings along a ray, handle the awkward cases, and cut any simple polygon into triangles with ear clipping.
Ray casting: count the crossings
var room = new V2[] { new(0, 0), new(8, 0), new(8, 3), new(3, 3), new(3, 6), new(0, 6) }; foreach (var p in new V2[] { new(2, 5), new(5, 5), new(5, 1), new(1, 3) }) Console.WriteLine($"{p}: {(Inside(room, p) ? "inside" : "outside")}"); static bool Inside(V2[] poly, V2 p){ bool inside = false; for (int i = 0, j = poly.Length - 1; i < poly.Length; j = i++) { V2 a = poly[i], b = poly[j]; if ((a.Y > p.Y) != (b.Y > p.Y) && // the edge spans the ray's height p.X < a.X + (p.Y - a.Y) * (b.X - a.X) / (b.Y - a.Y)) // and crosses it to the right of p inside = !inside; } return inside;} readonly record struct V2(double X, double Y){ public static V2 operator +(V2 a, V2 b) => new(a.X + b.X, a.Y + b.Y); public static V2 operator -(V2 a, V2 b) => new(a.X - b.X, a.Y - b.Y); public static V2 operator *(V2 v, double k) => new(v.X * k, v.Y * k); public static double Dot(V2 a, V2 b) => a.X * b.X + a.Y * b.Y; public static double Cross(V2 a, V2 b) => a.X * b.Y - a.Y * b.X; public double Length => Math.Sqrt(X * X + Y * Y); public override string ToString() => $"({X:0.###}, {Y:0.###})";}(2, 5): inside (5, 5): outside (5, 1): inside (1, 3): inside
Ear clipping
var room = new V2[] { new(0, 0), new(8, 0), new(8, 3), new(3, 3), new(3, 6), new(0, 6) }; var tris = EarClip(room);double total = 0;foreach (var (i, j, k) in tris){ double area = V2.Cross(room[j] - room[i], room[k] - room[i]) / 2; total += area; Console.WriteLine($"Triangle {i}-{j}-{k}: area {area}");}Console.WriteLine($"{tris.Count} triangles, total area {total}"); static List<(int, int, int)> EarClip(V2[] p) // p must be counterclockwise{ var idx = Enumerable.Range(0, p.Length).ToList(); var result = new List<(int, int, int)>(); while (idx.Count > 3) { bool clipped = false; for (int k = 0; k < idx.Count && !clipped; k++) { int a = idx[(k + idx.Count - 1) % idx.Count], b = idx[k], c = idx[(k + 1) % idx.Count]; if (V2.Cross(p[b] - p[a], p[c] - p[b]) <= 0) continue; // reflex corner: not an ear if (idx.Any(m => m != a && m != b && m != c && InTriangle(p[m], p[a], p[b], p[c]))) continue; // another corner is in the way result.Add((a, b, c)); idx.RemoveAt(k); clipped = true; } if (!clipped) throw new InvalidOperationException("No ear found: does the boundary cross itself?"); } result.Add((idx[0], idx[1], idx[2])); return result;} static bool InTriangle(V2 q, V2 a, V2 b, V2 c) => V2.Cross(b - a, q - a) >= 0 && V2.Cross(c - b, q - b) >= 0 && V2.Cross(a - c, q - c) >= 0; readonly record struct V2(double X, double Y){ public static V2 operator +(V2 a, V2 b) => new(a.X + b.X, a.Y + b.Y); public static V2 operator -(V2 a, V2 b) => new(a.X - b.X, a.Y - b.Y); public static V2 operator *(V2 v, double k) => new(v.X * k, v.Y * k); public static double Dot(V2 a, V2 b) => a.X * b.X + a.Y * b.Y; public static double Cross(V2 a, V2 b) => a.X * b.Y - a.Y * b.X; public double Length => Math.Sqrt(X * X + Y * Y); public override string ToString() => $"({X:0.###}, {Y:0.###})";}Triangle 0-1-2: area 12 Triangle 0-2-3: area 7.5 Triangle 5-0-3: area 9 Triangle 3-4-5: area 4.5 4 triangles, total area 33
Show a hint
Show the solution
var hex = new V2[6];for (int i = 0; i < 6; i++) hex[i] = new V2(2 * Math.Cos(i * Math.PI / 3), 2 * Math.Sin(i * Math.PI / 3)); double total = 0;for (int i = 1; i < hex.Length - 1; i++) total += V2.Cross(hex[i] - hex[0], hex[i + 1] - hex[0]) / 2; // triangle (0, i, i + 1) Console.WriteLine($"{hex.Length - 2} triangles, area {total:F3}");Console.WriteLine($"Formula: {3 * Math.Sqrt(3) / 2 * 4:F3}"); readonly record struct V2(double X, double Y){ public static V2 operator +(V2 a, V2 b) => new(a.X + b.X, a.Y + b.Y); public static V2 operator -(V2 a, V2 b) => new(a.X - b.X, a.Y - b.Y); public static V2 operator *(V2 v, double k) => new(v.X * k, v.Y * k); public static double Dot(V2 a, V2 b) => a.X * b.X + a.Y * b.Y; public static double Cross(V2 a, V2 b) => a.X * b.Y - a.Y * b.X; public double Length => Math.Sqrt(X * X + Y * Y); public override string ToString() => $"({X:0.###}, {Y:0.###})";}4 triangles, area 10.392 Formula: 10.392
Remember
Cast a ray and count edge crossings: odd means inside, even means outside. The half-open rule (one end strictly above, the other not) makes corners count correctly. Check “on the boundary” separately, with a distance tolerance, before casting the ray. Ear clipping cuts any simple polygon into n − 2 triangles by repeatedly removing a convex, empty corner. Convex polygons can simply be fanned from one corner; large or holed polygons deserve a library.