Published
Edited
Feb 6, 2022
25 stars
function findTriangleEdge(m) {
// start with a triangle
let t = 0,
e,
triangle,
f,
steps = [],
_seen = {},
lastpoint = -1;
m = cartesian(m);
// find an edge where our point is on the left side, and switch to the other triangle that shares this edge
do {
triangle = delaunay.triangles[t];
let e = -1;
for (let i = 0; i < 3; i++) {
// spare a comparison if we're coming from that edge
if (triangle[i] !== lastpoint) {
f = [triangle[i], triangle[(i + 1) % 3]];
if (excess([m, cartesian(points[f[1]]), cartesian(points[f[0]])]) > 0) {
e = i;
break;
}
}
}
if (e > -1) {
lastpoint = triangle[(e + 1) % 3];
t = (neighbors[3 * t + e] / 3) | 0;
} else t = -1;
steps.push({ t, e, triangle, f });
// if the point is to the right of no edge, it's inside the triangle
} while (
t > -1 &&
!_seen[t] &&
(_seen[t] = true) &&
steps.length < delaunay.triangles.length // irrational fear of infinite loops
);
// instrumentation
triangle.steps = steps;
if (t === -1) return triangle;
}
function excess(triangle) {
return dot(triangle[0], cross(triangle[2], triangle[1]));
}
// neighbors[3*t] = triangle id of triangle opposite edge 0 of triangle t.
neighbors = {
const triangles = delaunay.triangles,
neighbors = Array.from({ length: triangles.length }),
_index = {};
// create index
delaunay.triangles.forEach((tri, t) => {
for (let i = 0; i < 3; i++) {
const e = [tri[i], tri[(i + 1) % 3]].join("-");
_index[e] = 3 * t + i;
}
});
// read it
delaunay.triangles.forEach((tri, t) => {
for (let i = 0; i < 3; i++) {
const e = [tri[(i + 1) % 3], tri[i]].join("-");
neighbors[3 * t + i] = _index[e];
}
});
return neighbors;
}
findTriangleEnumerate([0, -90])
findTriangleEdge([0, -80])
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
