diff options
Diffstat (limited to 'src/vector/Polygons.zig')
| -rw-r--r-- | src/vector/Polygons.zig | 59 |
1 files changed, 58 insertions, 1 deletions
diff --git a/src/vector/Polygons.zig b/src/vector/Polygons.zig index c0ed335..c64db3d 100644 --- a/src/vector/Polygons.zig +++ b/src/vector/Polygons.zig @@ -4,7 +4,7 @@ //! the same way, so the nonzero rule unions them. const Polygons = @This(); const std = @import("std"); -const geom = @import("geom.zig"); +const geom = @import("math"); const Drawing = @import("Drawing.zig"); const Vec = geom.Vec; const Affine = geom.Affine; @@ -97,6 +97,44 @@ pub fn bounds(p: *const Polygons) geom.Bounds { return b; } +/// Whether `pts`, as a closed contour, is a convex polygon going around once: +/// every turn the same way (straight runs and repeated points allowed), and +/// the edge direction's x flips sign at most twice, which rules out +/// spirals. Its fan from any point then covers each inside point once and +/// nothing outside, under either fill rule. Exact: the slightest reflex +/// turn says no. +pub fn convex(pts: []const Vec) bool { + var turn: f32 = 0; + var flips: u32 = 0; + var first: ?Vec = null; + var prev: Vec = undefined; + var first_sign: f32 = 0; + var last_sign: f32 = 0; + for (0..pts.len) |i| { + const e = pts[(i + 1) % pts.len] - pts[i]; + if (e[0] == 0 and e[1] == 0) continue; + if (first == null) first = e else if (!turns(prev, e, &turn)) return false; + prev = e; + if (e[0] != 0) { + const sign = std.math.sign(e[0]); + if (first_sign == 0) first_sign = sign else if (sign != last_sign) flips += 1; + last_sign = sign; + } + } + if (!turns(prev, first orelse return false, &turn)) return false; + if (last_sign != first_sign) flips += 1; + return turn != 0 and flips <= 2; +} + +/// Whether the corner from edge `a` to edge `b` turns the way `turn` (the +/// first nonzero cross product so far) does, or goes straight on. +fn turns(a: Vec, b: Vec, turn: *f32) bool { + const cross = geom.cross(a, b); + if (cross == 0) return geom.dot(a, b) > 0; + if (turn.* == 0) turn.* = cross; + return (cross > 0) == (turn.* > 0); +} + /// Iterates contours as point slices. pub fn iterator(p: *const Polygons) Iterator { return .{ .p = p }; @@ -368,6 +406,25 @@ fn truncate(list: *std.ArrayList(Vec), len: f32) []const Vec { return pts; } +test "convex contours" { + const square = [_]Vec{ .{ 0, 0 }, .{ 10, 0 }, .{ 10, 10 }, .{ 0, 10 } }; + try std.testing.expect(convex(&square)); + // Either orientation, repeated points, a closing point equal to the + // first, straight runs. + try std.testing.expect(convex(&.{ .{ 0, 10 }, .{ 10, 10 }, .{ 10, 0 }, .{ 0, 0 } })); + try std.testing.expect(convex(&.{ .{ 0, 0 }, .{ 5, 0 }, .{ 5, 0 }, .{ 10, 0 }, .{ 10, 10 }, .{ 0, 10 }, .{ 0, 0 } })); + // A reflex corner (an L), a bow tie, a pentagram, a square wound twice, + // a line and a point. + try std.testing.expect(!convex(&.{ .{ 0, 0 }, .{ 10, 0 }, .{ 10, 5 }, .{ 5, 5 }, .{ 5, 10 }, .{ 0, 10 } })); + try std.testing.expect(!convex(&.{ .{ 0, 0 }, .{ 10, 10 }, .{ 10, 0 }, .{ 0, 10 } })); + var star: [5]Vec = undefined; + for (&star, 0..) |*q, i| q.* = geom.unit(@as(f32, @floatFromInt(i * 2)) * std.math.tau / 5) * geom.splat(10); + try std.testing.expect(!convex(&star)); + try std.testing.expect(!convex(&(square ++ square))); + try std.testing.expect(!convex(&.{ .{ 0, 0 }, .{ 10, 0 }, .{ 20, 0 } })); + try std.testing.expect(!convex(&.{ .{ 1, 1 }, .{ 1, 1 }, .{ 1, 1 } })); +} + test "a square stroke is four quads and four miters, all wound one way" { var p: Polygons = .init(std.testing.allocator); defer p.deinit(); |
