1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
let clockwise_sign ?(eps = Util.epsilon) (ps : V2.t array) =
let len = Array.length ps
and sum = ref 0. in
for i = 0 to len - 1 do
let p1 = ps.(Util.index_wrap ~len i)
and p2 = ps.(Util.index_wrap ~len (i + 1)) in
sum := !sum +. V2.((x p1 -. x p2) *. (y p1 +. y p2))
done;
if Math.approx ~eps !sum 0. then 0. else Float.(of_int @@ compare !sum 0.)
let is_clockwise ps = Float.equal 1. (clockwise_sign ps)
let self_intersections ?(eps = Util.epsilon) ?(closed = false) path =
let len = Array.length path in
if len < 3
then []
else (
let intersects = ref []
and w = Util.index_wrap ~len in
for i = 0 to len - if closed then 3 else 4 do
let l1 = V2.{ a = path.(i); b = path.(i + 1) } in
let seg_normal =
let d = V2.sub l1.b l1.a in
V2.(normalize (v (-.y d) (x d)))
in
let ref_v = V2.dot path.(i) seg_normal
and last_signal = ref 0
and start = i + 2 in
for j = 0 to len - start - if closed then 1 else 2 do
let v = V2.dot path.(j + start) seg_normal -. ref_v in
if Float.abs v >= eps
then (
let signal = Int.of_float @@ Math.sign v in
if signal * !last_signal <= 0
then (
let l2 = V2.{ a = path.(j + start); b = path.(w (j + start + 1)) } in
let intersect =
V2.line_intersection ~eps ~bounds1:(true, true) ~bounds2:(true, true) l1 l2
in
Option.iter (fun p -> intersects := p :: !intersects) intersect );
last_signal := signal )
done
done;
!intersects )
let is_simple ?eps ?(closed = false) path =
let len = Array.length path in
if len < 3
then true
else (
let reversal = ref false
and i = ref 0
and last = len - if closed then 1 else 2 in
while (not !reversal) && !i < last do
let v1 = V2.sub path.(!i + 1) path.(!i)
and v2 = V2.sub path.(Util.index_wrap ~len (!i + 2)) path.(!i + 1) in
reversal := Math.approx V2.(dot v1 v2 /. norm v1 /. norm v2) (-1.);
incr i
done;
if !reversal then false else List.length (self_intersections ?eps path) = 0 )