dkh.geo.polygon source code

1 module dkh.geo.polygon;
2 
3 import dkh.geo.primitive;
4 
5 inout(Point2D!R) at(R)(inout Point2D!R[] pol, size_t i) {
6     return pol[i<pol.length?i:i-pol.length];
7 }
8 
9 //0:P is out 1:P is on line 2:P is in
10 int contains(R)(Point2D!R[] pol, Point2D!R p) {
11     import std.algorithm : swap;
12     int res = -1;
13     foreach (i; 0..pol.length) {
14         auto a = pol.at(i) - p, b = pol.at(i+1) - p;
15         if (ccw(a, b, Point2D!R(0, 0)) == 0) return 1;
16         if (a.y > b.y) swap(a, b);
17         if (a.y <= 0 && 0 < b.y) {
18             if (cross(a, b) < 0) res *= -1;
19         }
20     }
21     return res+1;
22 }
23 
24 unittest {
25     alias P = Point2D!int;
26     P[] pol = [P(0, 0), P(2, 0), P(2, 2), P(0, 2)];
27     assert(contains(pol, P(-1, 0)) == 0);
28     assert(contains(pol, P(0, 0)) == 1);
29     assert(contains(pol, P(1, 1)) == 2);
30 }
31 
32 R area2(R)(Point2D!R[] pol) {
33     R u = 0;
34     foreach (i; 0..pol.length) {
35         auto a = pol.at(i), b = pol.at(i+1);
36         u += cross(a, b);
37     }
38     return u;
39 }
40 
41 unittest {
42     alias P = Point2D!int;
43     P[] pol = [P(0, 0), P(2, 0), P(2, 2), P(0, 2)];
44     assert(area2(pol) == 8);
45 }
46 
47 import dkh.container.stackpayload;
48 
49 Point2D!R[] convex(R)(Point2D!R[] _pol) {
50     import std.algorithm : sort;
51     import std.range : retro, array;
52     auto pol = _pol.dup;
53     pol.sort!((a, b) => robustCmp(a, b) == -1);
54     if (pol.length <= 2) return pol;
55     StackPayload!(Point2D!R) up;
56     foreach (d; pol) {
57         while (up.length >= 2 && ccw(up[$-2], up[$-1], d) == 1) up.removeBack();
58         up ~= d;
59     }
60     StackPayload!(Point2D!R) down;
61     foreach (d; pol) {
62         while (down.length >= 2 && ccw(down[$-2], down[$-1], d) == -1) down.removeBack();
63         down ~= d;
64     }
65     return up.data.retro.array[1..$-1] ~ down.data();
66 }
67 
68 unittest {
69     EPS!double = 1e-9;
70     alias P = Point2D!double;
71     P[] pol = [P(0, 0), P(2, 2), P(1, 1), P(0, 2), P(2, 0)];
72     import std.stdio;
73     assert(pol.convex.length == 4);
74 }