Visual representation of the process of finding convex hull for a set of random 2D points (implementation known as the Gift Wrapping or Jarvis's March algorithm).
Last active
June 8, 2019 02:55
-
-
Save saifuddin778/35b03529078e0dfba5476d13f7bcea40 to your computer and use it in GitHub Desktop.
Convex Hull (Jarvis's March)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| <!DOCTYPE html> | |
| <meta charset="utf-8"> | |
| <style> | |
| body { | |
| text-align: center; | |
| } | |
| .dots { | |
| fill: #50ff50; | |
| fill-opacity: 0.6; | |
| stroke: #383838; | |
| } | |
| </style> | |
| <body> | |
| <script src="http://d3js.org/d3.v3.js"></script> | |
| <script> | |
| //saif, a. (2k19) | |
| function genSpace(width, height, points){ | |
| var space = d3.select("body").append("svg").attr("width", width).attr("height", height).style("background", "snow").append("g"); | |
| space.selectAll() | |
| .data(points) | |
| .enter() | |
| .append("g") | |
| .append("circle") | |
| .attr("cx", function(d){return d.x}) | |
| .attr("cy", function(d){return d.y}) | |
| .attr("r", function(d){return 3}) | |
| .attr("class", "dots"); | |
| return space | |
| } | |
| function sleep(ms) { | |
| return new Promise(resolve => setTimeout(resolve, ms)); | |
| } | |
| function getOrientation(origin, p1, p2){ | |
| /** | |
| -- returns orientation of point p1 wrt p2 using origin as the center point. -ve if p2 is clockwise wrt p1, else +ve. | |
| **/ | |
| const orient = ((p2.x - origin.x) * (p1.y - origin.y)) - ((p1.x - origin.x) * (p2.y - origin.y)); | |
| return orient; | |
| } | |
| function distance(p1, p2){ | |
| /** | |
| -- standard distance function | |
| **/ | |
| var dist = 0; | |
| for (var i=0; i<p1.length; i++){ | |
| dist += Math.pow(Math.abs(p1[i]-p2[i]), 2); | |
| } | |
| return dist; | |
| } | |
| async function run(){ | |
| /** | |
| -- entry point | |
| */ | |
| const width = 500; | |
| const height = 500; | |
| const n = 2000; | |
| const points = d3.range(n).map(function(d){ | |
| const r = 10 + (200 * Math.random()) * Math.random(); | |
| const theta = Math.random() * 2 * Math.PI; | |
| return { | |
| x: Math.round((width/2) + r * Math.cos(theta), 2), | |
| y: Math.round((height/2) + r * Math.sin(theta), 2) | |
| } | |
| }); | |
| var space = genSpace(width, height, points); | |
| //now run over the points and find the left most | |
| let left_most = points[0]; | |
| let left_most_idx = 0; | |
| for (var i=0; i<n; i++){ | |
| if (points[i].x < left_most.x){ | |
| left_most = points[i]; | |
| left_most_idx = i; | |
| } | |
| } | |
| var hulls = []; | |
| //now begin from the left most | |
| var l = left_most_idx; | |
| hulls.push(points[l]); | |
| var connect_from = 0; | |
| while(true){ | |
| var q = (l + 1) % points.length; | |
| for (var i=0; i<n; i++){ | |
| if (i == l){ | |
| continue | |
| } | |
| var d = getOrientation(points[l], points[i], points[q]); | |
| if ((d > 0) || ((d==0) && (distance(points[i], points[l]) > distance(points[q], points[l])))) { | |
| q = i; | |
| } | |
| } | |
| l = q; | |
| if (l == left_most_idx){ | |
| space.append("line").attr("x1", hulls[0].x).attr("y1", hulls[0].y).attr("x2", hulls[hulls.length-1].x).attr("y2", hulls[hulls.length-1].y).style("fill", "none").style("stroke", "tomato").style("stroke-width", 2).style("stroke-dasharray", ("3, 3")); | |
| break; | |
| } | |
| hulls.push(points[q]); | |
| space.append("line").attr("x1", hulls[connect_from].x).attr("y1", hulls[connect_from].y).attr("x2", hulls[hulls.length-1].x).attr("y2", hulls[hulls.length-1].y).style("fill", "none").style("stroke", "tomato").style("stroke-width", 2).style("stroke-dasharray", ("3, 3")); | |
| if (connect_from == 0){ | |
| d3.select(space.selectAll("circle")[0][left_most_idx]).style("fill", "red").attr("r", 4); | |
| } | |
| d3.select(space.selectAll("circle")[0][q]).style("fill", "red").attr("r", 4); | |
| await sleep(500); | |
| connect_from += 1; | |
| } | |
| } | |
| run(); | |
| </script> | |
| </body> |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment