JavaScript
Detecting Mouse Hover over Irregular Shapes
Using a classic, brilliant algorithm from 1970
by Joe Honton
W. Randolph Franklin's "point inclusion in polygon" algorithm weighs in at just seven lines of C code. It's intuitively easy to understand, yet fast enough to work with sophisticated GIS datasets. It's one of those gems that every advanced programmer should know.
This article demonstrates how to use Franklin's PNPOLY with client-facing JavaScript to detect when the user's mouse is hovering over a non-rectangular polygon.
PNPOLY algorithm
The concept behind the algorithm is simple enough: extend an imaginary, semi-infinite ray from the position of the mouse towards the right, counting how many times the line crosses an edge of the polygon.
The code iterates over the nodes of the polygon, from i:1 → N and j:0 → N-1. Each iteration examines one edge of the polygon, defined by the endpoints i and j.
The test performed during each iteration determines whether the each of the two nodes are on the left-side or right-side of the imaginary horizontal ray. This first part of the test is a simple comparison of the y coordinates of the nodes to the y coordinate of the mouse position.
When the two nodes of the current iteration are on opposite sides, the second part of the test is to determine whether the mouse is to the left or to the right of the i-j edge. If the mouse's x coordinate is less than the x coordinate of the i-j edge where it intersects the ray (as determined through mathematical triangulation), the imaginary ray crosses the edge.
Here is Franklin's code, converted to JavaScript, and slightly more verbose, for additional clarity:
function isInsidePolygon(polygon, mouseX, mouseY) {
const c = false;
for (let i=1, j=0; i < polygon.length; i++, j++) {
const ix = polygon[i].x;
const iy = polygon[i].y;
const jx = polygon[j].x;
const jy = polygon[j].y;
const iySide = (iy > mouseY);
const jySide = (jy > mouseY);
if (iySide != jySide) {
const intersectX = (jx-ix) * (mouseY-iy) / (jy-iy) + ix;
if (mouseX < intersectX)
c = !c;
}
}
return c;
}
As coded, the loop stops at the last node, under the assumption that the first and last nodes are the same point, forming a closed polygon. If the polygon is not closed, one more comparison must be performed where i=0 and j=polygon.length-1.
When the ray crosses an odd number of polygon edges, the mouse is inside the polygon. When it cross an even number of edges, the mouse is outside the polygon.
We can intuitively see the second case with this modified polygon, where the ray crosses the polygon twice.
In geography applications, polygon shapes are often convoluted, but the algorithm still works. This convoluted example contains a peninsula and a bay. The imaginary ray crosses three polygon edges, so the mouse is correctly determined to be within the polygon.
Mouse hover
Monitoring the mouse position is straightforward. Simply set up a listener for the mousemove event. For example, here's how to monitor a canvas element that contains several polygonal shapes.
const shapes = new Map();
shapes.set('triangle',
[{x:100, y:100},
{x:120, y:120},
{x:140, y:140},
{x:100, y:100}]);
shapes.set('quadrangle',
[{x:371, y:229},
{x:229, y:229},
{x:229, y:371},
{x:371, y:371},
{x:371, y:229}]);
shapes.set('pentagon',
[{x:550, y:450},
{x:455, y:519},
{x:491, y:631},
{x:609, y:631},
{x:645, y:519},
{x:550, y:450}]);
const el = document.querySelector('#canvas');
el.addEventListener('mousemove', e => {
for (let [name, polygon] of shapes) {
if (isInsidePolygon(polygon, e.offsetX, e.offsetY))
console.log(`Mouse is hovering over ${name}`)
}
});
Handling clipped polygons
Sometimes polygons are only partially rendered within the user's viewport. This causes the standard PNPOLY algorithm to fail. One common example of this is when the drawing is scrolled, causing some of the polygons to be partially invisible.
For these situations, a preprocessing step needs to be performed to begin the ray casting test with firstv, the first visible node. On each subsequent iteration of the test loop, the algorithm must ensure that both the i and j nodes are visible. In the implementation shown here, this is handled with the mrv variable, which stores the most recently visible node.
function isInsideClippedPolygon(polygon, mouseX, mouseY) {
const c = false;
// make sure there are at least 3 visible nodes
var countv = 0;
for (let k=0; k < polygon.length && countv < 3; k++) {
if (polygon[k].visible == true)
countv++;
}
if (countv < 3)
return false;
// get the first visible node
const firstv = null;
for (let k=0; k < polygon.length; k++) {
if (polygon[k].visible == true) {
firstv = k;
break;
}
}
// raycast most-recent-visible-node -> next-visible-node
const mrv = firstv;
for (let i=mrv+1; i < polygon.length; i++) {
if (polygon[i].visible == false)
continue;
let j = mrv;
const ix = polygon[i].x;
const iy = polygon[i].y;
const jx = polygon[j].x;
const jy = polygon[j].y;
const iySide = (iy > mouseY);
const jySide = (jy > mouseY);
if (iySide != jySide) {
const intersectX = (jx-ix) * (mouseY-iy) / (jy-iy) + ix;
if (mouseX < intersectX)
c = !c;
}
mrv = i;
}
// raycast most-recent-visible-node -> first-visible-node
const ix = polygon[firstv].x;
const iy = polygon[firstv].y;
const jx = polygon[mrv].x;
const jy = polygon[mrv].y;
const iySide = (iy > mouseY);
const jySide = (jy > mouseY);
if (iySide != jySide) {
const intersectX = (jx-ix) * (mouseY-iy) / (jy-iy) + ix;
if (mouseX < intersectX)
c = !c;
}
return c;
}
This is the approach used by the simply.earth website, shown in the title block, which renders Earth using an orthographic projection. Notice how the algorithm is able to detect which country the mouse is hovering over, even when it is at the extreme edge of the globe.
Franklin's first version of the code debuted in July of 1970. It was written in FORTRAN, contained four GO TO statements, and was limited to polygons with a maximum of 200 nodes. But from that humble beginning, Franklin went on to a five-decade career at Rensselaer Polytechnic Institute developing algorithms for working on spatial problems involving terrains, meshes, GIS, and CAD. Meanwhile, Franklin's PNPOLY algorithm has remained an ever-steady classic: it has been encoded into many of the most popular computer languages.
