// Geometry of lines and arrows: how rough.js curves bound them.
// From element/bounds.ts and element/linearElementEditor.ts.
///|
/// Upstream keeps generated shapes in a cache, and `getElementAbsoluteCoords`
/// changes behaviour with it: with no cached shape it estimates a line's box
/// from its points, with one it uses the real curve. So the coordinates depend
/// on which shapes were generated before, and that history is part of the output.
pub struct ShapeCache {
priv shapes : Map[String, @moon_rough.Drawable]
}
///|
pub fn ShapeCache::new() -> ShapeCache {
{ shapes: Map([]), }
}
///|
/// Keeps the drawable upstream's `ShapeCache.generateElementShape` made for `e`.
/// Later reads use it as it was drawn, not a fresh one made from the points as
/// they are by then.
pub fn ShapeCache::store(
self : ShapeCache,
e : @model.Element,
curve : @moon_rough.Drawable,
) -> Unit {
self.shapes[e.id] = curve
}
///|
fn ShapeCache::get(
self : ShapeCache,
e : @model.Element,
) -> @moon_rough.Drawable? {
self.shapes.get(e.id)
}
///|
fn linear_points(e : @model.Element) -> Array[(Double, Double)] {
match e.kind {
Line(l) | Arrow(l) => l.points
_ => abort("not a linear element")
}
}
///|
/// `generateLinearElementShape`: the curve drawn for a line or arrow, which is
/// also the first drawable of its shape.
///
/// A closed line with a pattern fill is drawn as a polygon, and rough.js's pattern
/// fills rotate the polygon's points in place and back. That leaves rounding noise
/// in upstream's `element.points`, which every later calculation then reads, so
/// the element's points are overwritten the same way.
pub fn generate_curve(e : @model.Element) -> @moon_rough.Drawable {
let points = linear_points(e)
let gen = @moon_rough.generator()
let options = rough_options(e)
if e.roundness is Some(_) {
gen.curve(points, options~)
} else if options.fill is Some(_) {
let work = points.map(fn(p) { @geometry.Point::new(p.0, p.1) })
let drawable = gen.polygon_points(work, options~)
for i, p in work {
points[i] = (p.x, p.y)
}
drawable
} else {
gen.linear_path(points, options~)
}
}
///|
/// `getCurvePathOps`.
pub fn curve_path_ops(d : @moon_rough.Drawable) -> Array[@moon_rough.Op] {
for set in d.sets {
if set.kind is Path {
return set.ops
}
}
if d.sets.length() > 0 {
d.sets[0].ops
} else {
[]
}
}
///|
/// `getBezierValueForT`.
fn bezier_value(
t : Double,
p0 : Double,
p1 : Double,
p2 : Double,
p3 : Double,
) -> Double {
let u = 1.0 - t
@jsnum.cube(u) * p0 +
3.0 * (u * u) * t * p1 +
3.0 * u * (t * t) * p2 +
@jsnum.cube(t) * p3
}
///|
/// `solveQuadratic`: the curve's values at its extrema inside 0..1.
fn extrema(p0 : Double, p1 : Double, p2 : Double, p3 : Double) -> Array[Double] {
let i = p1 - p0
let j = p2 - p1
let k = p3 - p2
let a = 3.0 * i - 6.0 * j + 3.0 * k
let b = 6.0 * j - 6.0 * i
let c = 3.0 * i
let sqrt_part = b * b - 4.0 * a * c
if !(sqrt_part >= 0.0) {
return []
}
let (t1, t2) = if a == 0.0 {
(-c / b, -c / b)
} else {
let root = sqrt_part.sqrt()
((-b + root) / (2.0 * a), (-b - root) / (2.0 * a))
}
let out = []
if t1 >= 0.0 && t1 <= 1.0 {
out.push(bezier_value(t1, p0, p1, p2, p3))
}
if t2 >= 0.0 && t2 <= 1.0 {
out.push(bezier_value(t2, p0, p1, p2, p3))
}
out
}
///|
/// `getMinMaxXYFromCurvePathOps`. Only Bézier ops count, as upstream.
fn curve_ops_bounds(
ops : Array[@moon_rough.Op],
transform : ((Double, Double)) -> (Double, Double),
) -> (Double, Double, Double, Double) {
let mut current = (0.0, 0.0)
let mut min_x = @double.infinity
let mut min_y = @double.infinity
let mut max_x = @double.neg_infinity
let mut max_y = @double.neg_infinity
for op in ops {
match op {
Move(x, y) => current = (x, y)
BCurveTo(x1, y1, x2, y2, x3, y3) => {
let p1 = transform((x1, y1))
let p2 = transform((x2, y2))
let p3 = transform((x3, y3))
let p0 = transform(current)
current = (x3, y3)
let mut lo_x = @jsmath.min(p0.0, p3.0)
let mut hi_x = @jsmath.max(p0.0, p3.0)
for v in extrema(p0.0, p1.0, p2.0, p3.0) {
lo_x = @jsmath.min(lo_x, v)
hi_x = @jsmath.max(hi_x, v)
}
let mut lo_y = @jsmath.min(p0.1, p3.1)
let mut hi_y = @jsmath.max(p0.1, p3.1)
for v in extrema(p0.1, p1.1, p2.1, p3.1) {
lo_y = @jsmath.min(lo_y, v)
hi_y = @jsmath.max(hi_y, v)
}
min_x = @jsmath.min(min_x, lo_x)
min_y = @jsmath.min(min_y, lo_y)
max_x = @jsmath.max(max_x, hi_x)
max_y = @jsmath.max(max_y, hi_y)
}
LineTo(_, _) => ()
}
}
(min_x, min_y, max_x, max_y)
}
///|
/// `getBoundsFromPoints`.
fn points_bounds(
points : Array[(Double, Double)],
) -> (Double, Double, Double, Double) {
let mut min_x = @double.infinity
let mut min_y = @double.infinity
let mut max_x = @double.neg_infinity
let mut max_y = @double.neg_infinity
for p in points {
min_x = @jsmath.min(min_x, p.0)
min_y = @jsmath.min(min_y, p.1)
max_x = @jsmath.max(max_x, p.0)
max_y = @jsmath.max(max_y, p.1)
}
(min_x, min_y, max_x, max_y)
}
///|
/// `LinearElementEditor.getElementAbsoluteCoords`.
fn linear_absolute_coords(
cache : ShapeCache,
e : @model.Element,
) -> (Double, Double, Double, Double, Double, Double) {
let points = linear_points(e)
let (min_x, min_y, max_x, max_y) = match cache.get(e) {
Some(curve) => curve_ops_bounds(curve_path_ops(curve), fn(p) { p })
None => points_bounds(points)
}
let x1 = min_x + e.x
let y1 = min_y + e.y
let x2 = max_x + e.x
let y2 = max_y + e.y
(x1, y1, x2, y2, (x1 + x2) / 2.0, (y1 + y2) / 2.0)
}
///|
/// `getLinearElementRotatedBounds`.
fn linear_rotated_bounds(
cache : ShapeCache,
e : @model.Element,
cx : Double,
cy : Double,
map : Map[String, @model.Element],
) -> (Double, Double, Double, Double) {
// Upstream uses the cached shape if there is one, and otherwise draws a fresh
// one (without caching it).
let curve = match cache.get(e) {
Some(curve) => curve
None => generate_curve(e)
}
let ops = curve_path_ops(curve)
let bounds = curve_ops_bounds(ops, fn(p) {
rotate(e.x + p.0, e.y + p.1, cx, cy, e.angle)
})
match bound_text(e, map) {
Some(text) => bounds_with_text(cache, e, map, bounds, text)
None => bounds
}
}
///|
/// `getBoundTextElement`: the first text bound to a container.
pub fn bound_text(
e : @model.Element,
map : Map[String, @model.Element],
) -> @model.Element? {
for b in e.bound_elements {
if b.kind == "text" {
return map.get(b.id)
}
}
None
}
///|
fn point_global(
cache : ShapeCache,
e : @model.Element,
p : (Double, Double),
map : Map[String, @model.Element],
) -> (Double, Double) {
let (x1, y1, x2, y2, _, _) = absolute_coords(cache, e, map)
rotate(e.x + p.0, e.y + p.1, (x1 + x2) / 2.0, (y1 + y2) / 2.0, e.angle)
}
///|
/// `getControlPointsForBezierCurve`: the Bézier segment ending closest to
/// `end_point`. Upstream generates the shape here, which fills its cache.
fn control_points(
cache : ShapeCache,
e : @model.Element,
end_point : (Double, Double),
) -> Array[(Double, Double)]? {
// `generateElementShape`: the cached shape, or a new one that is then cached.
let curve = match cache.get(e) {
Some(curve) => curve
None => {
let curve = generate_curve(e)
cache.store(e, curve)
curve
}
}
let mut current = (0.0, 0.0)
let mut min_distance = @double.infinity
let mut result = None
for op in curve_path_ops(curve) {
match op {
Move(x, y) => current = (x, y)
BCurveTo(x1, y1, x2, y2, x3, y3) => {
let d = @jsnum.hypot(x3 - end_point.0, y3 - end_point.1)
if d < min_distance {
min_distance = d
result = Some([current, (x1, y1), (x2, y2), (x3, y3)])
}
current = (x3, y3)
}
LineTo(_, _) => ()
}
}
result
}
///|
/// `getBezierXY`. Note that the weights are listed from the end point back.
fn bezier_xy(cp : Array[(Double, Double)], t : Double) -> (Double, Double) {
let u = 1.0 - t
let eq = fn(p0 : Double, p1 : Double, p2 : Double, p3 : Double) {
@jsnum.cube(u) * p3 +
3.0 * t * (u * u) * p2 +
3.0 * (t * t) * u * p1 +
p0 * @jsnum.cube(t)
}
(
eq(cp[0].0, cp[1].0, cp[2].0, cp[3].0),
eq(cp[0].1, cp[1].1, cp[2].1, cp[3].1),
)
}
///|
/// `mapIntervalToBezierT`: the t that lies `interval` of the way along the
/// curve's length, measured on 20 points of it.
fn interval_to_t(
cp : Array[(Double, Double)],
end_point : (Double, Double),
interval : Double,
) -> Double {
let points = []
let mut t = 1.0
while t > 0.0 {
points.push(bezier_xy(cp, t))
t -= 0.05
}
let last = points[points.length() - 1]
if (last.0 - end_point.0).abs() < 10.0e-5 &&
(last.1 - end_point.1).abs() < 10.0e-5 {
points.push(end_point)
}
let arc_lengths = [0.0]
let mut distance = 0.0
for i in 0..<(points.length() - 1) {
distance += @jsnum.hypot(
points[i].0 - points[i + 1].0,
points[i].1 - points[i + 1].1,
)
arc_lengths.push(distance)
}
let count = arc_lengths.length() - 1
let target = interval * arc_lengths[count]
let mut low = 0
let mut high = count
let mut index = 0
while low < high {
index = low + (high - low) / 2
if arc_lengths[index] < target {
low = index + 1
} else {
high = index
}
}
if arc_lengths[index] > target {
index -= 1
}
if arc_lengths[index] == target {
return index.to_double() / count.to_double()
}
1.0 -
(
index.to_double() +
(target - arc_lengths[index]) /
(arc_lengths[index + 1] - arc_lengths[index])
) /
count.to_double()
}
///|
/// `getSegmentMidPoint`: the middle of a segment, or for a curve the point half
/// way along its length.
fn segment_mid_point(
cache : ShapeCache,
e : @model.Element,
points : Array[(Double, Double)],
start : (Double, Double),
end : (Double, Double),
end_index : Int32,
map : Map[String, @model.Element],
) -> (Double, Double) {
if points.length() > 2 && e.roundness is Some(_) {
let end_point = points[end_index]
if control_points(cache, e, end_point) is Some(cp) {
let t = interval_to_t(cp, end_point, 0.5)
return point_global(cache, e, bezier_xy(cp, t), map)
}
}
((start.0 + end.0) / 2.0, (start.1 + end.1) / 2.0)
}
///|
/// `LinearElementEditor.getBoundTextElementPosition`: a label sits on the middle
/// point, or on the middle of the middle segment.
pub fn bound_text_position(
cache : ShapeCache,
e : @model.Element,
text : @model.Element,
map : Map[String, @model.Element],
) -> (Double, Double) {
let points = linear_points(e)
let (x1, y1, x2, y2, _, _) = absolute_coords(cache, e, map)
let cx = (x1 + x2) / 2.0
let cy = (y1 + y2) / 2.0
let global = points.map(fn(p) {
rotate(e.x + p.0, e.y + p.1, cx, cy, e.angle)
})
let mid = if points.length() % 2 == 1 {
point_global(cache, e, points[points.length() / 2], map)
} else {
let index = points.length() / 2 - 1
segment_mid_point(
cache,
e,
points,
global[index],
global[index + 1],
index + 1,
map,
)
}
(mid.0 - text.width / 2.0, mid.1 - text.height / 2.0)
}
///|
/// `getMinMaxXYWithBoundText`: grows a line's box to contain its label.
fn bounds_with_text(
cache : ShapeCache,
e : @model.Element,
map : Map[String, @model.Element],
bounds : (Double, Double, Double, Double),
text : @model.Element,
) -> (Double, Double, Double, Double) {
let (bx1, by1, bx2, by2) = bounds
let mut x1 = bx1
let mut y1 = by1
let mut x2 = bx2
let mut y2 = by2
let cx = (x1 + x2) / 2.0
let cy = (y1 + y2) / 2.0
let (tx1, ty1) = bound_text_position(cache, e, text, map)
let tx2 = tx1 + text.width
let ty2 = ty1 + text.height
let top_left = rotate(x1, y1, cx, cy, e.angle)
let top_right = rotate(x2, y1, cx, cy, e.angle)
let tl = rotate(tx1, ty1, cx, cy, -e.angle)
let tr = rotate(tx2, ty1, cx, cy, -e.angle)
let bl = rotate(tx1, ty2, cx, cy, -e.angle)
let br = rotate(tx2, ty2, cx, cy, -e.angle)
if top_left.0 < top_right.0 && top_left.1 >= top_right.1 {
x1 = @jsmath.min(x1, bl.0)
x2 = @jsmath.max(x2, @jsmath.max(tr.0, br.0))
y1 = @jsmath.min(y1, tl.1)
y2 = @jsmath.max(y2, br.1)
} else if top_left.0 >= top_right.0 && top_left.1 > top_right.1 {
x1 = @jsmath.min(x1, br.0)
x2 = @jsmath.max(x2, @jsmath.max(tl.0, tr.0))
y1 = @jsmath.min(y1, bl.1)
y2 = @jsmath.max(y2, tr.1)
} else if top_left.0 >= top_right.0 {
x1 = @jsmath.min(x1, tr.0)
x2 = @jsmath.max(x2, bl.0)
y1 = @jsmath.min(y1, br.1)
y2 = @jsmath.max(y2, tl.1)
} else if top_left.1 <= top_right.1 {
x1 = @jsmath.min(x1, @jsmath.min(tr.0, tl.0))
x2 = @jsmath.max(x2, br.0)
y1 = @jsmath.min(y1, tr.1)
y2 = @jsmath.max(y2, bl.1)
}
(x1, y1, x2, y2)
}