summaryrefslogtreecommitdiff
path: root/src/vector/Polygons.zig
diff options
context:
space:
mode:
Diffstat (limited to 'src/vector/Polygons.zig')
-rw-r--r--src/vector/Polygons.zig59
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();