Convex Hull SVG Overlay

README.md

Convex Hull Overlay SVG

Generate a SVG overlay of the convex hull of a set of points.

convex.hull.highlight-zi2aan.mp4

• Go to the page http://okotte.com/wed/game/pannel.php
• Paste JS from script.js into page
• Click around

How It's Made

Tech Used: HTML, CSS, JavaScript

Reverse engineering the existing user interface and generated SVG elements was a good half of the process, but after discovering the way the points were being stored, using a Convex Hull algorithm from Project Nayuki, I was able to pass all the points within a circular radius of the center, then set the points of a new <polygon /> to the convex hull of the points.

Lessons Learned

Reverse engineering existing code is a great way to learn how to do something new, and dynamically generating & updating a <polygon /> was a fun challenge.

script.js

/*
 * Convex hull algorithm - Library (compiled from TypeScript)
 *
 * Copyright (c) 2020 Project Nayuki
 * https://www.nayuki.io/page/convex-hull-algorithm
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with this program (see COPYING.txt and COPYING.LESSER.txt).
 * If not, see <http://www.gnu.org/licenses/>.
 */
var convexhull;
(function (convexhull) {
    // Returns a new array of points representing the convex hull of
    // the given set of points. The convex hull excludes collinear points.
    // This algorithm runs in O(n log n) time.
    function makeHull(points) {
        var newPoints = points.slice();
        newPoints.sort(convexhull.POINT_COMPARATOR);
        return convexhull.makeHullPresorted(newPoints);
    }
    convexhull.makeHull = makeHull;
    // Returns the convex hull, assuming that each points[i] <= points[i + 1]. Runs in O(n) time.
    function makeHullPresorted(points) {
        if (points.length <= 1)
            return points.slice();
        // Andrew's monotone chain algorithm. Positive y coordinates correspond to "up"
        // as per the mathematical convention, instead of "down" as per the computer
        // graphics convention. This doesn't affect the correctness of the result.
        var upperHull = [];
        for (var i = 0; i < points.length; i++) {
            var p = points[i];
            while (upperHull.length >= 2) {
                var q = upperHull[upperHull.length - 1];
                var r = upperHull[upperHull.length - 2];
                if ((q.x - r.x) * (p.y - r.y) >= (q.y - r.y) * (p.x - r.x))
                    upperHull.pop();
                else
                    break;
            }
            upperHull.push(p);
        }
        upperHull.pop();
        var lowerHull = [];
        for (var i = points.length - 1; i >= 0; i--) {
            var p = points[i];
            while (lowerHull.length >= 2) {
                var q = lowerHull[lowerHull.length - 1];
                var r = lowerHull[lowerHull.length - 2];
                if ((q.x - r.x) * (p.y - r.y) >= (q.y - r.y) * (p.x - r.x))
                    lowerHull.pop();
                else
                    break;
            }
            lowerHull.push(p);
        }
        lowerHull.pop();
        if (upperHull.length == 1 && lowerHull.length == 1 && upperHull[0].x == lowerHull[0].x && upperHull[0].y == lowerHull[0].y)
            return upperHull;
        else
            return upperHull.concat(lowerHull);
    }
    convexhull.makeHullPresorted = makeHullPresorted;
    function POINT_COMPARATOR(a, b) {
        if (a.x < b.x)
            return -1;
        else if (a.x > b.x)
            return +1;
        else if (a.y < b.y)
            return -1;
        else if (a.y > b.y)
            return +1;
        else
            return 0;
    }
    convexhull.POINT_COMPARATOR = POINT_COMPARATOR;
})(convexhull || (convexhull = {}));
// convexHull.makeHull from https://www.nayuki.io/res/convex-hull-algorithm/convex-hull.js

(() => {
	const distanceBetween = ([x1, y1], [x2, y2]) => {
		const a = x1 - x2;
		const b = y1 - y2;
		return Math.sqrt(a*a + b*b);
	}
	
	const svg = $('svg');

	$('#viewport').addEventListener('click', e => {
		const xr = 200 / window.innerWidth;
		const yr = 200 / window.innerHeight;
		const mx = e.clientX * xr;
		const my = e.clientY * yr;
		//clicked position
		//svg.insertAdjacentHTML('beforeend', `<g><circle class="target" style="fill:salmon;" cx="${mx}" cy="${my}" r="0.7"></circle><text class="labelName" transform="matrix(1 0 0 1 ${mx} ${my-5})">Madai Sanchez</text><data class="name">Madai Sanchez</data><data class="visits">3</data><data class="menu">0</data><data class="pdf"></data><data class="ip">99.227.234.44</data><data class="whois">Pepe</data></g>`);

		const allPoints = Array.from($$('circle.target')).map(target => ({element: target, x: Number(target.getAttribute('cx')), y: Number(target.getAttribute('cy'))}));
		const center = [100, 100];
		const radius = Number($('circle.diameter').getAttribute('r'))
		const pointsWithin = allPoints.filter(p => distanceBetween(center, [p.x, p.y]) <= radius)
		//highlight individual points
		//pointsWithin.forEach(p => p.element.style.fill = 'white');
		const hull = convexhull.makeHull(pointsWithin);
		const svgPoints = hull.map(({ x, y }) => `${x},${y}`).join(' ')
		const highlight = $('#highlight');
		if (!highlight) $('svg').insertAdjacentHTML('beforeend', `<polygon id="highlight" style="opacity:0.4;fill:#FF002B;" points="${svgPoints}"/>`);
		else highlight.setAttribute('points', svgPoints);
	});
})();