function findInPolygonMark(quadtree, polygon) {
// marks
const time = performance.now();
const tested = [],
visited = [],
rejected = [],
accepted = [],
result = Object.assign([], { tested, visited, rejected, accepted });
function accept(d) {
result.push(d);
}
function acceptAll(node) {
if (node.length) {
for (const n of node) if (n) acceptAll(n);
} else {
accept(node.data);
}
}
const bounds = [d3.extent(polygon, d => d[0]), d3.extent(polygon, d => d[1])];
// Visit the quadtree from the top, recursively
quadtree.visit(function(node, x1, y1, x2, y2) {
if (node.length) {
// this is not a leaf: mark that we visited it
visited.push({ x1, y1, x2, y2 });
// When can we eliminate the quad?
// - the quad is outside the polygon bounds
if (
x1 > bounds[0][1] ||
x2 < bounds[0][0] ||
y1 > bounds[1][1] ||
y2 < bounds[1][0]
) {
rejected.push({ x1, y1, x2, y2 });
return true;
}
// OR
// - none of the 4 edges intersect with the polygon
// - & its first vertex is outside
// - & the first vertex of the polygon is outside the quad
const quad = [[x1, y1], [x2, y1], [x2, y2], [x1, y2]];
if (d3.polygonContains(quad, polygon[0])) return false;
if (polygonIntersect(polygon, quad)) return false;
// if the polygon fully contains the quad we can add
// all the points in that branch without further ado,
// then ignore.
if (d3.polygonContains(polygon, [x1, y1])) {
accepted.push({ x1, y1, x2, y2 });
acceptAll(node);
return true;
}
// reject
rejected.push({ x1, y1, x2, y2 });
return true;
}
// this is a leaf node: it contains 1 point in node.data
do {
const d = node.data;
// measure its euclidian distance to <x,y> and accept it if < radius
if (d3.polygonContains(polygon, d)) accept(d);
// mark that we tested it
tested.push(d);
} while ((node = node.next));
// the do...while chained call is used to test coincident points—which would belong
// to the same leaf node; in our case with random points, however, this test is useless
// as the probability of coincident points is 0.
});
result.time = (performance.now() - time).toFixed(1) + "ms";
return result;
}
function chart() {
const context = DOM.context2d(width, height),
canvas = context.canvas;
const paintPoints = d3.line().context(context);
function draw() {
context.fillStyle = "#fefef2";
context.fillRect(0, 0, width, height);
context.lineWidth = 0.25;
// found, tested points, visited quads, accepted quads
const found = findInPolygonMark(quadtree, polygon),
{ tested, visited, rejected, accepted, time } = found;
// accepted quads
context.fillStyle = "#eee";
accepted.forEach(({ x1, y1, x2, y2 }) =>
context.fillRect(x1, y1, x2 - x1, y2 - y1)
);
// rejected quads
context.fillStyle = "#ffffff";
rejected.forEach(({ x1, y1, x2, y2 }) =>
context.fillRect(x1, y1, x2 - x1, y2 - y1)
);
// visited quads
context.strokeStyle = "#000";
visited.forEach(({ x1, y1, x2, y2 }) =>
context.strokeRect(x1, y1, x2 - x1, y2 - y1)
);
// points
context.fillStyle = "#aaa";
context.beginPath();
paintPoints.curve(curvePoints(1.5))(data);
context.fill();
// tested points
context.fillStyle = "steelblue";
context.beginPath();
paintPoints.curve(curvePoints(2.5))(tested);
context.fill();
// found points
context.fillStyle = "#333";
context.beginPath();
paintPoints.curve(curvePoints(2.5))(found);
context.fill();
// polygon
context.lineWidth = 1.5;
context.strokeStyle = "orange";
context.stroke(new Path2D(`M${polygon.flat()}Z`));
context.fillStyle = "orange";
context.beginPath();
paintPoints.curve(curvePoints(5))(polygon);
context.fill();
// performance
context.fillStyle = "#000";
context.fillText(time, 10, height-10)
}
return d3
.select(canvas)
.call(draw)
.on("mousemove", function() {
const m = d3.mouse(this);
d3.select(canvas).style(
"cursor",
d3.min(polygon, p => distance(p, m)) < 10 ? "grab" : "crosshair"
);
})
.call(drag(polygon, draw))
.node();
}
polygon = [[333, 695], [300, 250], [100, 250], [100, 100], [400, 20], [700, 200]];
function distance(p, m) {
return Math.hypot(p[0] - m[0], p[1] - m[1]);
}
function drag(polygon, draw) {
return d3
.drag()
.subject(function() {
const e = d3.event,
m = [e.x, e.y],
distances = polygon.map(p => distance(p, m)),
i = d3.minIndex(distances);
return distances[i] < 10 && i;
})
.on("start", function() {
d3.select(this).style("cursor", "grabbing");
})
.on("drag", function() {
const e = d3.event;
polygon[e.subject] = d3.mouse(this).map((x,i) => clamp(x, 0,i ? height : width));
draw();
})
.on("end", function() {
d3.select(this).style("cursor", "grab");
});
}
findInPolygonMark(quadtree, polygon)
function polygonIntersect(a, b) {
let p0 = a[a.length - 1];
for (const p of a) {
let q0 = b[b.length - 1];
for (const q of b) {
if (segmentIntersect([p, p0], [q, q0])) return true;
q0 = q;
}
p0 = p;
}
}
function segmentIntersect([p, p0], [q, q0]) {
const a = [p0[0] - p[0], p0[1] - p[1]],
b = [q0[0] - q[0], q0[1] - q[1]],
s =
(-a[1] * (p[0] - q[0]) + a[0] * (p[1] - q[1])) /
(-b[0] * a[1] + a[0] * b[1]),
t =
(b[0] * (p[1] - q[1]) - b[1] * (p[0] - q[0])) /
(-b[0] * a[1] + a[0] * b[1]);
return s >= 0 && s <= 1 && t >= 0 && t <= 1;
}
function findInPolygon(quadtree, polygon, filter){}
quadtree = d3
.quadtree()
.extent([[-1, -1], [width + 1, height + 1]])
.addAll(data)
data = {
const randomx = d3.randomUniform(0, width),
randomy = d3.randomUniform(0, height - 20);
return Array.from({ length: 2500 }, () => [randomx(), randomy()]);
}
height = 700
d3 = require("d3@5", "d3-array@2")
import { curvePoints } from "5c4650cfb7214d6c"
function clamp(x, min, max) {
return Math.max(min, Math.min(max, x));
}
import {slider} from "@jashkenas/inputs"
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.
