Skip to content

Instantly share code, notes, and snippets.

@darshit-shah
Last active December 30, 2016 23:38
Show Gist options
  • Save darshit-shah/16061ded7ba1d14694eea86c05da29db to your computer and use it in GitHub Desktop.
Save darshit-shah/16061ded7ba1d14694eea86c05da29db to your computer and use it in GitHub Desktop.
Mouse hovering on how many Convex Polygons?
<!DOCTYPE html>
<meta charset="utf-8">
<script src="https://d3js.org/d3.v3.min.js"></script>
<canvas width="500" height="500"></canvas>
<div style="float:left">
<div>
Total Polygon<input type="text" id="totalPolygon" value="3" style="margin-left:20px;" />
</div>
<div>
Visible Polygon<input type="text" id="drawPolygon" value="3" style="margin-left:20px;" />
</div>
<div>
# Sides (~ +3)<input type="text" id="numSides" value="3" style="margin-left:20px;" />
</div>
<input type="button" value="Random Polygin" onclick="generate()" />
</div>
<script>
var canvas = document.querySelector("canvas"),
context = canvas.getContext("2d");
var width = canvas.width,
height = canvas.height;
var counter=0;
var startTime = new Date().getTime();
var r = 200;
var cx = 250;
var cy = 250;
var pointPoolCount = 0;
var pointPool = [];
var n = 0;
var arrPoints = [];
var counter = 0;
var drawCounter=0;
var startTime = 0;
function generate(){
counter = +document.querySelector("#totalPolygon").value || 3;
drawCounter=+document.querySelector("#drawPolygon").value || 3;
arrPoints = new Array();
context.clearRect(0, 0, width, height);
while(true){
if(counter<=0){
break;
}
pointPoolCount = 120 + Math.ceil(Math.random()*120);
pointPool = new Array(pointPoolCount);
for (var i = 0, n = pointPoolCount; i < n; ++i) {
var a = (i*2*Math.PI)/pointPoolCount;
pointPool[i] = [cx + r * Math.cos(a), cy + r * Math.sin(a)];
}
n = (+document.querySelector("#numSides").value || 3) + Math.floor(Math.random()*3);
points = new Array(n);
var bucket = Math.floor(pointPoolCount/n);
for (var i = 0; i < n; i++) {
points[i] = pointPool[(i*bucket)+Math.floor(Math.random()*bucket)];
}
if(drawCounter>0){
context.font = "12px Arial";
context.fillStyle = "black";
context.lineWidth = 1;
context.strokeStyle = "BLACK";
context.fillText("move to any point",10,20);
context.closePath();
context.beginPath();
context.moveTo(points[0][0], points[0][1]);
for (var i = 1; i < n ; i++) {
context.lineTo(points[i][0], points[i][1]);
}
context.closePath();
context.fillStyle = "rgba(70, 130, 180, 0.1)";
context.fill();
context.lineWidth = 1.5;
context.lineJoin = "round";
context.strokeStyle = "rgba(70, 130, 180, 0.5)";
context.stroke();
}
arrPoints.push(points);
drawCounter--;
counter--;
}
}
generate();
d3.select("canvas")
.on("mousemove", function() {
var that = this;
var insideCounter = 0;
var startTime = new Date().getTime();
arrPoints.forEach(function(d){
if(IsInConvexPolygon(d3.mouse(that),d)){
insideCounter++;
}
});
context.clearRect(0, 0, 500, 30);
context.font = "12px Arial";
context.fillStyle = "black";
context.lineWidth = 1;
context.strokeStyle = "BLACK";
context.fillText("Point is inside "+insideCounter+" Convex polygons out of "+arrPoints.length+". Found in "+((new Date().getTime()-startTime)/1000)+" Seconds.",10,20);
context.closePath();
});
function IsInConvexPolygon(testPoint, polygonPoints)
{
var pos = 0;
var neg = 0;
for (var i = 0; i < polygonPoints.length; i++)
{
//If point is in the polygon
if (polygonPoints[i][0] == testPoint[0] && polygonPoints[i][1] == testPoint[1])
return true;
//Form a segment between the i'th point
var x1 = polygonPoints[i][0];
var y1 = polygonPoints[i][1];
//And the i+1'th, or if i is the last, with the first point
var i2 = i < polygonPoints.length - 1 ? i + 1 : 0;
var x2 = polygonPoints[i2][0];
var y2 = polygonPoints[i2][1];
var x = testPoint[0];
var y = testPoint[1];
//Compute the cross product
var d = (x - x1)*(y2 - y1) - (y - y1)*(x2 - x1);
if (d > 0) pos++;
if (d < 0) neg++;
//If the sign changes, then point is outside
if (pos > 0 && neg > 0)
return false;
}
//If no change in direction, then on same side of all segments, and thus inside
return true;
}
</script>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment