// Ported from robust-predicates 3.0.3 (orient2d.js, util.js; the Unlicense),
// after Jonathan Richard Shewchuk's public-domain predicates.c.
///|
let epsilon : Double = 1.1102230246251565e-16
///|
let splitter : Double = 134217729.0
///|
let resulterrbound : Double = (3.0 + 8.0 * epsilon) * epsilon
///|
let ccwerrbound_a : Double = (3.0 + 16.0 * epsilon) * epsilon
///|
let ccwerrbound_b : Double = (2.0 + 12.0 * epsilon) * epsilon
///|
let ccwerrbound_c : Double = (9.0 + 64.0 * epsilon) * epsilon * epsilon
///|
let b_exp : FixedArray[Double] = FixedArray::make(4, 0.0)
///|
let c1_exp : FixedArray[Double] = FixedArray::make(8, 0.0)
///|
let c2_exp : FixedArray[Double] = FixedArray::make(12, 0.0)
///|
let d_exp : FixedArray[Double] = FixedArray::make(16, 0.0)
///|
let u_exp : FixedArray[Double] = FixedArray::make(4, 0.0)
///|
/// `e[i]`, or 0 past its end where JavaScript reads `undefined`: `sum` looks
/// one element ahead but never uses that value.
fn at(e : FixedArray[Double], i : Int32) -> Double {
if i < e.length() {
e[i]
} else {
0.0
}
}
///|
/// util.js's `sum` (fast_expansion_sum_zeroelim): `e` + `f` into `h`, its length.
fn sum(
elen : Int32,
e : FixedArray[Double],
flen : Int32,
f : FixedArray[Double],
h : FixedArray[Double],
) -> Int32 {
let mut enow = e[0]
let mut fnow = f[0]
let mut eindex = 0
let mut findex = 0
let mut q = 0.0
if (fnow > enow) == (fnow > -enow) {
q = enow
eindex += 1
enow = at(e, eindex)
} else {
q = fnow
findex += 1
fnow = at(f, findex)
}
let mut hindex = 0
if eindex < elen && findex < flen {
let mut qnew = 0.0
let mut hh = 0.0
if (fnow > enow) == (fnow > -enow) {
qnew = enow + q
hh = q - (qnew - enow)
eindex += 1
enow = at(e, eindex)
} else {
qnew = fnow + q
hh = q - (qnew - fnow)
findex += 1
fnow = at(f, findex)
}
q = qnew
if hh != 0.0 {
h[hindex] = hh
hindex += 1
}
while eindex < elen && findex < flen {
let mut bvirt = 0.0
if (fnow > enow) == (fnow > -enow) {
qnew = q + enow
bvirt = qnew - q
hh = q - (qnew - bvirt) + (enow - bvirt)
eindex += 1
enow = at(e, eindex)
} else {
qnew = q + fnow
bvirt = qnew - q
hh = q - (qnew - bvirt) + (fnow - bvirt)
findex += 1
fnow = at(f, findex)
}
q = qnew
if hh != 0.0 {
h[hindex] = hh
hindex += 1
}
}
}
while eindex < elen {
let qnew = q + enow
let bvirt = qnew - q
let hh = q - (qnew - bvirt) + (enow - bvirt)
eindex += 1
enow = at(e, eindex)
q = qnew
if hh != 0.0 {
h[hindex] = hh
hindex += 1
}
}
while findex < flen {
let qnew = q + fnow
let bvirt = qnew - q
let hh = q - (qnew - bvirt) + (fnow - bvirt)
findex += 1
fnow = at(f, findex)
q = qnew
if hh != 0.0 {
h[hindex] = hh
hindex += 1
}
}
if q != 0.0 || hindex == 0 {
h[hindex] = q
hindex += 1
}
hindex
}
///|
fn estimate(elen : Int32, e : FixedArray[Double]) -> Double {
let mut q = e[0]
for i in 1.. Double {
let c = splitter * a
c - (c - a)
}
///|
/// Two-Product's error term of `a * b`, whose rounded value is `p`.
fn product_tail(a : Double, b : Double, p : Double) -> Double {
let ahi = split_hi(a)
let alo = a - ahi
let bhi = split_hi(b)
let blo = b - bhi
alo * blo - (p - ahi * bhi - alo * bhi - ahi * blo)
}
///|
/// Two-Two-Diff of `a * b - c * d` into the four words of `out`.
fn two_two_diff(
a : Double,
b : Double,
c : Double,
d : Double,
out : FixedArray[Double],
) -> Unit {
let s1 = a * b
let s0 = product_tail(a, b, s1)
let t1 = c * d
let t0 = product_tail(c, d, t1)
let mut i = s0 - t0
let mut bvirt = s0 - i
out[0] = s0 - (i + bvirt) + (bvirt - t0)
let j = s1 + i
bvirt = j - s1
let z = s1 - (j - bvirt) + (i - bvirt)
i = z - t1
bvirt = z - i
out[1] = z - (i + bvirt) + (bvirt - t1)
let u3 = j + i
bvirt = u3 - j
out[2] = j - (u3 - bvirt) + (i - bvirt)
out[3] = u3
}
///|
/// The tail of `a - b`, whose rounded value is `x` (Two-Diff-Tail).
fn diff_tail(a : Double, b : Double, x : Double) -> Double {
let bvirt = a - x
a - (x + bvirt) + (bvirt - b)
}
///|
fn orient2dadapt(
ax : Double,
ay : Double,
bx : Double,
by : Double,
cx : Double,
cy : Double,
detsum : Double,
) -> Double {
let acx = ax - cx
let bcx = bx - cx
let acy = ay - cy
let bcy = by - cy
two_two_diff(acx, bcy, acy, bcx, b_exp)
let mut det = estimate(4, b_exp)
let mut errbound = ccwerrbound_b * detsum
if det >= errbound || -det >= errbound {
return det
}
let acxtail = diff_tail(ax, cx, acx)
let bcxtail = diff_tail(bx, cx, bcx)
let acytail = diff_tail(ay, cy, acy)
let bcytail = diff_tail(by, cy, bcy)
if acxtail == 0.0 && acytail == 0.0 && bcxtail == 0.0 && bcytail == 0.0 {
return det
}
errbound = ccwerrbound_c * detsum + resulterrbound * det.abs()
det += acx * bcytail + bcy * acxtail - (acy * bcxtail + bcx * acytail)
if det >= errbound || -det >= errbound {
return det
}
two_two_diff(acxtail, bcy, acytail, bcx, u_exp)
let c1len = sum(4, b_exp, 4, u_exp, c1_exp)
two_two_diff(acx, bcytail, acy, bcxtail, u_exp)
let c2len = sum(c1len, c1_exp, 4, u_exp, c2_exp)
two_two_diff(acxtail, bcytail, acytail, bcxtail, u_exp)
let dlen = sum(c2len, c2_exp, 4, u_exp, d_exp)
d_exp[dlen - 1]
}
///|
/// Twice the signed area of the triangle a, b, c, exact in sign: positive when
/// clockwise in a y-up frame, negative counter-clockwise, 0 when collinear.
/// Bit for bit robust-predicates 3.0.3's `orient2d`.
pub fn orient2d(
ax : Double,
ay : Double,
bx : Double,
by : Double,
cx : Double,
cy : Double,
) -> Double {
let detleft = (ay - cy) * (bx - cx)
let detright = (ax - cx) * (by - cy)
let det = detleft - detright
let detsum = (detleft + detright).abs()
if det.abs() >= ccwerrbound_a * detsum {
return det
}
-orient2dadapt(ax, ay, bx, by, cx, cy, detsum)
}