1. Eugene Perederey
  2. Triangulator

Source

Triangulator / geometry.ml

open Arithmetic;;

type point3 = {xx: float; yy: float; zz: float};;
type point2 = {x: float; y: float};;
type triangle = point3 * point3 * point3;;
type plane = {aa:float; bb:float; cc:float; dd: float};;

(* line in 2D *)
type line = {k: float; b: float};;
type segment = {e1: point2; e2: point2};;
type updown = Up | Down;;
type side = NoSide
	    | Side of line;;
type trapezoid = Plane
		 | HalfPlane of float*updown
		 | Stripe of float*float*side*side (* top, bottom, left, right *)
;;

(*************** string representations of these types **************)
let string_of_point p = "Point ("^(string_of_float p.x)^"; "^(string_of_float p.y)^")";;
let string_of_line ln = "k="^(string_of_float ln.k)^", b="^(string_of_float ln.b);;
let string_of_segment s = "[e1: "^(string_of_point s.e1)^"; e2: "^(string_of_point s.e2)^"]";;
let string_of_side s = match s with
    NoSide -> "NoSide"
  | Side ln -> "Side k="^(string_of_float ln.k)^", b="^(string_of_float ln.b);;
let string_of_trapezoid tr = match tr with
    Plane -> "Plane"
  | HalfPlane (y, Up) -> "HalfPlane Up, "^(string_of_float y)
  | HalfPlane (y, Down) -> "HalfPlane Down, "^(string_of_float y)
  | Stripe (yt, yb, s1, s2) -> "Stripe ("^(string_of_float yt)^", "^(string_of_float yb)^") Left: "^(string_of_side s1)^" Right: "^(string_of_side s2);;



(***** 3D geometry *******)
let dist3 = fun p1 -> fun p2 -> 
  sqrt ((p1.xx-.p2.xx)**2.0+.(p1.yy-.p2.yy)**2.0+.(p1.zz-.p2.zz)**2.0);;

let get_plane (verts: point3 list) = 
  let p1 = List.nth verts 0 in
  let dists = List.map (fun x -> dist3 p1 x) verts in
    (* take 3 quite distant points and calculate the plane coefficients *)
    {aa=0.0;bb=0.0;cc=0.0;dd=0.0}
;;
let transform_matrix pl = ();;
let apply_transform matrix verts = [{x=0.0;y=0.0}];;
  

(***** 2D geometry *******)
let line_of_segment s = 
  let kk = (s.e1.y-.s.e2.y)/.(s.e1.x-.s.e2.x) in
  let bb = s.e1.y-.kk*.s.e1.x in
  {k=kk; b=bb};;

let find_x (y: float) (ln: line) = (y-.ln.b)/.ln.k;;



type leftright = Left | Right | On;;
(* point p is to the Left|Right|On the line  *)
let left_or_right (ln: line) (p: point2) =
  let xx  = (p.y-.ln.b)/.ln.k in
    if p.x === xx then On
    else if p.x < xx then Left
    else Right;;

let bound_tr (tr: trapezoid) =
  match tr with
      Stripe (_, _, Side _, Side _) -> true
    | _ -> false;;

let triangle_stripe tr = 
  match tr with
      Stripe (yt, yb, Side lln, Side rln) ->
	let lb = find_x yb lln in
	let lt = find_x yt lln in
	let rt = find_x yt rln in
	let rb = find_x yb rln in
	  if lb === rb then
	    (true, Down)
	  else if lt === rt then
	    (true, Up)
	  else (false, Up)
    | _ -> (false, Up)
;;