Published
Edited
Jul 9, 2019
6 stars
// isLeft(): tests if a point is Left|On|Right of an infinite line.
// Input: three points P0, P1, and P2
// Return: >0 for P2 left of the line through P0 and P1
// =0 for P2 on the line
// <0 for P2 right of the line
isLeft = (P0, P1, P2) =>
( (P1[0] - P0[0])*(P2[1] - P0[1])
- (P2[0] - P0[0])*(P1[1] - P0[1]))
// wn_PnPoly(): winding number test for a point in a polygon
// Input: P = a point,
// V[] = vertex points of a polygon V[n+1] with V[n]=V[0]
// Return: wn = the winding number (=0 only when P is outside)
wn_PnPoly = function wn_PnPoly(P, V) {
let wn = 0; // the winding number counter
// loop through all edges of the polygon
for (let i = 0, n = V.length-1; i < n; i++) { // edge from V[i] to V[i+1]
if (V[i][1] <= P[1]) { // start y <= P.y
if (V[i + 1][1] > P[1]) // an upward crossing
if (isLeft(V[i], V[i + 1], P) > 0) // P left of edge
++wn; // valid up intersection
}
else { // start y > P.y (no test needed)
if (V[i + 1][1] <= P[1]) // a downward crossing
if (isLeft(V[i], V[i + 1], P) < 0) // P right of edge
--wn; // valid down intersection
}
}
return wn;
}
point_in_polygon_draft = function point_in_polygon_draft(point, vertices) {
const n = vertices.length - 1;
const [px, py] = point;
let winding_number = 0;
for (let i = 0; i < n; i++) { // loop through each edge a -> b in the polygon
const [ax, ay] = vertices[i];
const [bx, by] = vertices[i+1];
// twice the signed area of the triangle abp:
const point_left_of_edge = (ax - px)*(by - py) - (ay - py)*(bx - px);
winding_number += (
(ay <= py) & (by > py) & (point_left_of_edge > 0) // +1 if upward edge
- (ay > py) & (by <= py) & (point_left_of_edge < 0)); // -1 if downward edge
}
return winding_number;
}
point_in_polygon = function point_in_polygon(point, vertices) {
const n = vertices.length - 1;
const [px, py] = point;
let winding_number = 0;
let bx = vertices[0][0] - px, by = vertices[0][1] - py;
let b_below_p = by <= 0;
for (let i = 1; i <= n; i++) { // loop through each edge a -> b in the polygon
const ax = bx, ay = by, a_below_p = b_below_p; // re-use from previous iteration
bx = vertices[i][0] - px, by = vertices[i][1] - py;
b_below_p = by <= 0;
const point_left_of_edge = ax*by - ay*bx; // 2 * signed area of the triangle abp
winding_number += (
a_below_p & (b_below_p^1) & (point_left_of_edge > 0) // +1 if upward edge
- b_below_p & (a_below_p^1) & (point_left_of_edge < 0)); // -1 if downward edge
}
return winding_number;
}
point_in_polygon_overkill = function point_in_polygon_overkill(point, vertices) {
const n = vertices.length - 1;
const [px, py] = point;
let winding_number = 0;
let bx = vertices[0][0] - px, by = vertices[0][1] - py;
let b_below_p = by <= 0;
for (let i = 1; i <= n; i++) { // loop through each edge a -> b in the polygon
const ax = bx, ay = by, a_below_p = b_below_p; // re-use from previous iteration
bx = vertices[i][0] - px, by = vertices[i][1] - py;
b_below_p = by <= 0;
const axby = ax*by, aybx = ay*bx;
const p_left_of_ab = axby > aybx;
winding_number += ( // +1 if upward edge, -1 if downward edge
(a_below_p ^ b_below_p) * (b_below_p ^ p_left_of_ab)
* (p_left_of_ab - (axby < aybx)));
}
return winding_number;
}
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.
