Bézier curves/Intersections: Difference between revisions

(* One might be curious why "t@ype" instead of "type". The answer is:

the notation "type" is restricted to types that take up the same

space as a C void-pointer, which includes ATS pointers, "boxed"

types, etc. A "t@ype" can take up any amount of space, and so

includes any type there is (except for linear types, which is a

whole other subject). For instance, "int", "double", unboxed

records, unboxed tuples, and so on. *)

fun {a, b : t@ype} (* A polymorphic template function. *)

list_any (pred : (a, b) -<cloref1> bool,

obj : a,

lst : List0 b)

: bool =

(* Does pred(obj, item) return true for any list item? Here the

<cloref1> notation means that pred is a CLOSURE of the ordinary

garbage-collected kind, such as functions tend implicitly to be

in Lisps, MLs, Haskell, etc. *)

case+ lst of

| NIL => false

| hd :: tl =>

if pred (obj, hd) then

true

else

list_any (pred, obj, tl)

(px : @(double, double, double),

py : @(double, double, double),

qx : @(double, double, double),

qy : @(double, double, double),

tol : double,

spacing : double)

: List0 double =

within_spacing (t_candidate : double,

t_in_list : double)

:<cloref1> bool =

abs (t_candidate - t_in_list) < spacing

fun

loop {n : nat}

: List0 double =

case+ workload of

| NIL => params

| hd :: tl =>

let

val portionx = spower_portion_degree2 (px, hd)

and portiony = spower_portion_degree2 (py, hd)

in

if flat_enough (portionx, portiony, tol) then

let

val @(portionx0, _, portionx2) = portionx

and @(portiony0, _, portiony2) = portiony

val @(root0, root1) =

solve_linear_quadratic (@(portionx0, portionx2),

@(portiony0, portiony2),

qx, qy)

in

if 0.0 <= root0 && root0 <= 1.0 &&

~list_any (within_spacing, root0, params) then

begin

if 0.0 <= root1 && root1 <= 1.0 &&

~list_any (within_spacing, root1, params) then

loop (root0 :: root1 :: params, n + 2, tl)

else

loop (root0 :: params, n + 1, tl)

end

else if 0.0 <= root1 && root1 <= 1.0 &&

~list_any (within_spacing, root1, params) then

loop (root1 :: params, n + 1, tl)

else

loop (params, n, tl)

end

else

let

val @(t0, t1) = hd

val tmiddle = (0.5 * t0) + (0.5 * t1)

val job1 = @(t0, tmiddle)

and job2 = @(tmiddle, t1)

in

loop (params, n, job1 :: job2 :: tl)

end

end

val spacing = 0.0000001 (* Min. spacing between parameters. *)

val t_list = find_intersection_parameters (px, py, qx, qy,

tol, spacing)

(* For no particular reason, sort the intersections so they go

from top to bottom. *)

val t_list = list_vt2t (list_vt_reverse (list_mergesort t_list))

val () = println! ("From top to bottom:")

<pre>From top to bottom:

(-0.854982, 1.345016)

(0.881023, 1.118975)</pre>