import { quadrant, point } from "./Utils.js";
var EPSILON = 1e-8
var MAX_F = 1.0 / EPSILON;
function compareSlope(a, b) {
var ax = a[0],
ay = a[1],
bx = b[0],
by = b[1],
d = quadrant(ax, ay) - quadrant(bx, by)
if (d) {
return d
}
var p = ax * by,
q = ay * bx
if (p > q) {
return -1
}
if (p < q) {
return 1
}
return 0
}
function segIntersect(s, pt, dx, dy) {
var s0 = s[0],
s1 = s[1],
nx = s1[0] - s0[0],
ny = s1[1] - s0[1],
ax = s0[0] - pt[0],
ay = s0[1] - pt[1],
nn = ay * nx - ax * ny,
dd = dy * nx - dx * ny
return [dx * nn / dd + pt[0], dy * nn / dd + pt[1]]
}
function approxEq(x, y) {
return Math.abs(x - y) <= EPSILON * Math.min(Math.abs(x), Math.abs(y))
}
function pointsEqual(a, b) {
return approxEq(a[0], b[0]) && approxEq(a[1], b[1])
}
function cooriented(a, b, p, q) {
var pxqy = p[0] * q[1],
pyqx = p[1] * q[0],
ap = a[0] * p[1] + q[0] * a[1] + pxqy,
an = a[0] * q[1] + p[0] * a[1] + pyqx,
bp = b[0] * p[1] + q[0] * b[1] + pxqy,
bn = b[0] * q[1] + p[0] * b[1] + pyqx
return ((ap > an) === (bp > bn)) || approxEq(ap, an) || approxEq(bp, bn)
}
/**
* Computes the visible region from a point for a given environment represented by a collection of line segments
*
* 
*
* @module VisHull
* @see https://simblob.blogspot.com/2012/07/2d-visibility.html
*
* @example
* let walls = [
* [[0, 0], [100, 0]],
* [[100, 0], [100, 100]],
* [[100, 100], [0, 100]],
* [[0, 100], [0, 0]]
* ];
* let lines = VisHull.create(walls, 5, 5);
*
* let start = {x: lines[0][0], y: lines[0][1]};
*
* ctx.beginPath()
* ctx.moveTo(start.x, start.y)
* for (var i = 1; i < lines.length; ++i) {
* ctx.lineTo(lines[i][0], lines[i][1]);
* }
* ctx.lineTo(start.x, start.y);
* ctx.closePath();
* ctx.fill();
*/
export default {
/**
* create a visual hull
* @param {Array} segments array of [points](module-Utils#~point), the maximum range for each point is -100000000 to 100000000
* @param {Number} cx x coordinate of the center
* @param {Number} cy y coordinate of the center
* @returns {Array} Polygon points that describe the projected hull, in the form `[[x1, y1], [x2, y2], ...]`
*/
create(segments, cx, cy) {
var points = [];
//Copy segments and add a box around region
segments = segments.map(point)
segments.push([
[MAX_F + cx, MAX_F + cy],
[-MAX_F + cx, MAX_F + cy]
])
segments.push([
[-MAX_F + cx, MAX_F + cy],
[-MAX_F + cx, -MAX_F + cy]
])
segments.push([
[-MAX_F + cx, -MAX_F + cy],
[MAX_F + cx, -MAX_F + cy]
])
segments.push([
[MAX_F + cx, -MAX_F + cy],
[MAX_F + cx, MAX_F + cy]
])
//Project points onto circle
for (var i = 0, ns = segments.length; i < ns; ++i) {
var s = segments[i],
ax = s[0][0] - cx,
ay = s[0][1] - cy,
bx = s[1][0] - cx,
by = s[1][1] - cy
//Check degenerate cases
if ((approxEq(ax, 0) && approxEq(ay, 0)) ||
(approxEq(bx, 0) && approxEq(by, 0)) ||
(approxEq(ax, bx) && approxEq(ay, by))) {
continue
}
var a = [ax, ay, i, false],
b = [bx, by, i, true]
//Handle x-crossing degeneracy
if (by < 0 && ay > 0) {
var dy = by - ay,
dx = bx - ax,
x = ax - ay * dx / dy
if (x > EPSILON) {
var q = [x, 0, i, false]
if (!pointsEqual(b, q)) {
b[3] = false
points.push(b)
}
if (!pointsEqual(a, q)) {
a[3] = true
points.push(q)
points.push(a)
}
continue
}
}
if (ay < 0 && by > 0) {
var dy = ay - by,
dx = ax - bx,
x = bx - by * dx / dy
if (x > EPSILON) {
var q = [x, 0, i, false]
if (!pointsEqual(a, q)) {
points.push(a)
}
if (!pointsEqual(b, q)) {
points.push(q)
points.push(b)
}
continue
}
}
//Handle x-touching degeneracy
if (bx > 0 && ay < 0 && approxEq(by, 0)) {
points.push(a)
continue
}
if (ax > 0 && by < 0 && approxEq(ay, 0)) {
b[3] = false
points.push(b)
continue
}
var sign = compareSlope(a, b)
if (sign < 0) {
points.push(a)
points.push(b)
} else if (sign > 0) {
b[3] = false
points.push(b)
a[3] = true
points.push(a)
}
}
//Sort points by angle
points.sort(compareSlope)
points.push([1, 0, -1, true])
//Assemble visible hull
var vis_hull = [],
active = [],
pseg = -1;
for (var i = 0, np = points.length; i < np; ++i) {
var event = points[i];
if (event[3]) {
if (event[2] >= 0) {
active[active.indexOf(event[2])] = active[active.length - 1]
active.pop()
}
} else {
active.push(event[2])
}
if (i < np - 1 && compareSlope(points[i], points[i + 1]) === 0) {
continue
}
var min_n = Infinity,
min_d = 1,
min_a = -1,
dx = event[0],
dy = event[1];
for (var j = 0, na = active.length; j < na; ++j) {
var a = active[j],
s = segments[a],
s0 = s[0],
s1 = s[1],
nx = s1[0] - s0[0],
ny = s1[1] - s0[1],
ax = cx - s0[0],
ay = cy - s0[1],
nn = ay * nx - ax * ny,
dd = dx * ny - dy * nx;
if (dd < 0) {
nn = -nn
dd = -dd
}
if (nn > 0) {
var xx = min_n * dd,
yy = min_d * nn;
if (approxEq(xx, yy)) {
s = segments[min_a]
if (cooriented([cx, cy], s0, s[0], s[1]) && cooriented([cx, cy], s1, s[0], s[1])) {
min_a = a
}
} else if (xx > yy) {
min_n = nn
min_d = dd
min_a = a
}
}
}
if (min_a < 0) {
continue
}
var hull_n = vis_hull.length,
i1 = [dx * min_n / min_d + cx, dy * min_n / min_d + cy]
if (hull_n === 0) {
vis_hull.push(i1)
} else if (pseg !== min_a || event[2] < 0) {
var s = segments[min_a],
i0 = segIntersect(segments[pseg], [cx, cy], dx, dy)
if (!pointsEqual(i0, vis_hull[hull_n - 1])) {
vis_hull.push(i0)
if (!pointsEqual(i0, i1)) {
vis_hull.push(i1)
}
} else if (!pointsEqual(i1, vis_hull[hull_n - 1])) {
vis_hull.push(i1)
}
}
pseg = min_a
}
//Check if end points need to be joined
var hull_n = vis_hull.length
if (pointsEqual(vis_hull[hull_n - 1], vis_hull[0])) {
vis_hull.pop()
--hull_n
}
return vis_hull
}
};