measure.chull source code

1 module measure.chull;
2 
3 import std.algorithm;
4 import std.algorithm.sorting;
5 import std.stdio;
6 import std.math;
7 
8 import measure.types;
9 import measure.regionprops;
10 
11 /* https://rosettacode.org/wiki/Convex_hull 
12    https://www.gnu.org/licenses/fdl-1.2.html
13 */
14 
15 XYList convexHull(XYList _p) {
16     auto n = _p.xs.length;
17     assert( n >= 3, "Convex hull not possible");
18     
19     Point[] p; p.length = n; foreach(i; 0..n) p[i] = Point(_p.xs[i], _p.ys[i]);
20     p.sort();
21     Point[] h;
22  
23     // lower hull
24     foreach (pt; p) {
25         while (h.length >= 2 && !ccw(h[$-2], h[$-1], pt)) {
26             h.length--;
27         }
28         h ~= pt;
29     }
30  
31     // upper hull
32     auto t = h.length + 1;
33     foreach_reverse (i; 0..(p.length - 1)) {
34         auto pt = p[i];
35         while (h.length >= t && !ccw(h[$-2], h[$-1], pt)) {
36             h.length--;
37         }
38         h ~= pt;
39     }
40  
41     h.length--;
42     
43     XYList xys;
44     foreach(i; 0..h.length)
45     {
46         xys.xs ~= h[i].x;
47         xys.ys ~= h[i].y;
48     }
49     return xys;
50 }
51  
52 /* ccw returns true if the three points make a counter-clockwise turn */
53 auto ccw(Point a, Point b, Point c) @nogc {
54     return ((b.x - a.x) * (c.y - a.y)) > ((b.y - a.y) * (c.x - a.x));
55 }
56