1  use <../util/slice.scad>
 2  use <../util/sorted.scad>
 3  
 4  // oa->ob ct_clk : greater than 0
 5  function _convex_hull_impl_dir(o, a, b) = cross(a - o, b - o);
 6  
 7  function _convex_hull_convex_hull_lower_m(chain, p, m) = 
 8      (m < 2 || _convex_hull_impl_dir(chain[m - 2], chain[m - 1], p) > 0) ? m : _convex_hull_convex_hull_lower_m(chain, p, m - 1);
 9  
10  function _convex_hull_lower_chain(points, leng, chain, m, i) =
11      i == leng ? chain : 
12          let(current_m = _convex_hull_convex_hull_lower_m(chain, points[i], m))
13          _convex_hull_lower_chain(
14              points,
15              leng,
16              [each slice(chain, 0, current_m), points[i]],
17              current_m + 1,
18              i + 1
19          );
20              
21  function _convex_hull_upper_m(chain, p, m, t) =
22      (m < t || _convex_hull_impl_dir(chain[m - 2], chain[m - 1], p) > 0) ? m : _convex_hull_upper_m(chain, p, m - 1, t);
23          
24  function _convex_hull_upper_chain(points, chain, m, t, i) =
25      let(current_m = _convex_hull_upper_m(chain, points[i], m, t))
26      i == 2 ? slice(chain, 0, current_m) :
27          _convex_hull_upper_chain(
28              points,
29              [each slice(chain, 0, current_m), points[i]],
30              current_m + 1,
31              t,
32              i - 1
33          );
34  
35  function _convex_hull2(points) = 
36      let(
37          sorted_pts = sorted(points),
38          leng = len(sorted_pts),
39          lwr_ch = _convex_hull_lower_chain(sorted_pts, leng, [], 0, 0),
40          leng_lwr_ch = len(lwr_ch)
41      )
42      _convex_hull_upper_chain(sorted_pts, lwr_ch, leng_lwr_ch, leng_lwr_ch + 1, leng - 2);