Convex Polygon Intersection
/* | |
* This is the Point constructor. Polygon uses this object, but it is | |
* just a really simple set of x and y coordinates. | |
*/ | |
function Point(px, py) { | |
this.x = px; | |
this.y = py; | |
} | |
/* | |
* This is the Polygon constructor. All points are center-relative. | |
*/ | |
function Polygon(c, clr) { | |
this.points = new Array(); | |
this.center = c; | |
this.color = clr; // used when drawing | |
} | |
/* | |
* Point x and y values should be relative to the center. | |
*/ | |
Polygon.prototype.addPoint = function(p) { | |
this.points.push(p); | |
} | |
/* | |
* Point x and y values should be absolute coordinates. | |
*/ | |
Polygon.prototype.addAbsolutePoint = function(p) { | |
this.points.push( { "x": p.x - this.center.x, "y": p.y - this.center.y } ); | |
} | |
/* | |
* Returns the number of sides. Equal to the number of vertices. | |
*/ | |
Polygon.prototype.getNumberOfSides = function() { | |
return this.points.length; | |
} | |
/* | |
* rotate the polygon by a number of radians | |
*/ | |
Polygon.prototype.rotate = function(rads) { | |
for (var i = 0; i < this.points.length; i++) { | |
var x = this.points[i].x; | |
var y = this.points[i].y; | |
this.points[i].x = Math.cos(rads) * x - Math.sin(rads) * y; | |
this.points[i].y = Math.sin(rads) * x + Math.cos(rads) * y; | |
} | |
} | |
/* | |
* The draw function takes as a parameter a Context object from | |
* a Canvas element and draws the polygon on it. | |
*/ | |
Polygon.prototype.draw = function(ctx) { | |
ctx.save(); | |
ctx.fillStyle = this.color; | |
ctx.beginPath(); | |
ctx.moveTo(this.points[0].x + this.center.x, this.points[0].y + this.center.y); | |
for (var i = 1; i < this.points.length; i++) { | |
ctx.lineTo(this.points[i].x + this.center.x, this.points[i].y + this.center.y); | |
} | |
ctx.closePath(); | |
ctx.fill(); | |
ctx.restore(); | |
} | |
/* | |
* This function returns true if the given point is inside the polygon, | |
* and false otherwise. | |
*/ | |
Polygon.prototype.containsPoint = function(pnt) { | |
var nvert = this.points.length; | |
var testx = pnt.x; | |
var testy = pnt.y; | |
var vertx = new Array(); | |
for (var q = 0; q < this.points.length; q++) { | |
vertx.push(this.points[q].x + this.center.x); | |
} | |
var verty = new Array(); | |
for (var w = 0; w < this.points.length; w++) { | |
verty.push(this.points[w].y + this.center.y); | |
} | |
var i, j = 0; | |
var c = false; | |
for (i = 0, j = nvert - 1; i < nvert; j = i++) { | |
if ( ((verty[i]>testy) != (verty[j]>testy)) && | |
(testx < (vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i]) ) | |
c = !c; | |
} | |
return c; | |
} | |
/* | |
* To detect intersection with another Polygon object, this | |
* function uses the Separating Axis Theorem. It returns false | |
* if there is no intersection, or an object if there is. The object | |
* contains 2 fields, overlap and axis. Moving the polygon by overlap | |
* on axis will get the polygons out of intersection. | |
*/ | |
Polygon.prototype.intersectsWith = function(other) { | |
var axis = new Point(); | |
var tmp, minA, maxA, minB, maxB; | |
var side, i; | |
var smallest = null; | |
var overlap = 99999999; | |
/* test polygon A's sides */ | |
for (side = 0; side < this.getNumberOfSides(); side++) | |
{ | |
/* get the axis that we will project onto */ | |
if (side == 0) | |
{ | |
axis.x = this.points[this.getNumberOfSides() - 1].y - this.points[0].y; | |
axis.y = this.points[0].x - this.points[this.getNumberOfSides() - 1].x; | |
} | |
else | |
{ | |
axis.x = this.points[side - 1].y - this.points[side].y; | |
axis.y = this.points[side].x - this.points[side - 1].x; | |
} | |
/* normalize the axis */ | |
tmp = Math.sqrt(axis.x * axis.x + axis.y * axis.y); | |
axis.x /= tmp; | |
axis.y /= tmp; | |
/* project polygon A onto axis to determine the min/max */ | |
minA = maxA = this.points[0].x * axis.x + this.points[0].y * axis.y; | |
for (i = 1; i < this.getNumberOfSides(); i++) | |
{ | |
tmp = this.points[i].x * axis.x + this.points[i].y * axis.y; | |
if (tmp > maxA) | |
maxA = tmp; | |
else if (tmp < minA) | |
minA = tmp; | |
} | |
/* correct for offset */ | |
tmp = this.center.x * axis.x + this.center.y * axis.y; | |
minA += tmp; | |
maxA += tmp; | |
/* project polygon B onto axis to determine the min/max */ | |
minB = maxB = other.points[0].x * axis.x + other.points[0].y * axis.y; | |
for (i = 1; i < other.getNumberOfSides(); i++) | |
{ | |
tmp = other.points[i].x * axis.x + other.points[i].y * axis.y; | |
if (tmp > maxB) | |
maxB = tmp; | |
else if (tmp < minB) | |
minB = tmp; | |
} | |
/* correct for offset */ | |
tmp = other.center.x * axis.x + other.center.y * axis.y; | |
minB += tmp; | |
maxB += tmp; | |
/* test if lines intersect, if not, return false */ | |
if (maxA < minB || minA > maxB) { | |
return false; | |
} else { | |
var o = (maxA > maxB ? maxB - minA : maxA - minB); | |
if (o < overlap) { | |
overlap = o; | |
smallest = {x: axis.x, y: axis.y}; | |
} | |
} | |
} | |
/* test polygon B's sides */ | |
for (side = 0; side < other.getNumberOfSides(); side++) | |
{ | |
/* get the axis that we will project onto */ | |
if (side == 0) | |
{ | |
axis.x = other.points[other.getNumberOfSides() - 1].y - other.points[0].y; | |
axis.y = other.points[0].x - other.points[other.getNumberOfSides() - 1].x; | |
} | |
else | |
{ | |
axis.x = other.points[side - 1].y - other.points[side].y; | |
axis.y = other.points[side].x - other.points[side - 1].x; | |
} | |
/* normalize the axis */ | |
tmp = Math.sqrt(axis.x * axis.x + axis.y * axis.y); | |
axis.x /= tmp; | |
axis.y /= tmp; | |
/* project polygon A onto axis to determine the min/max */ | |
minA = maxA = this.points[0].x * axis.x + this.points[0].y * axis.y; | |
for (i = 1; i < this.getNumberOfSides(); i++) | |
{ | |
tmp = this.points[i].x * axis.x + this.points[i].y * axis.y; | |
if (tmp > maxA) | |
maxA = tmp; | |
else if (tmp < minA) | |
minA = tmp; | |
} | |
/* correct for offset */ | |
tmp = this.center.x * axis.x + this.center.y * axis.y; | |
minA += tmp; | |
maxA += tmp; | |
/* project polygon B onto axis to determine the min/max */ | |
minB = maxB = other.points[0].x * axis.x + other.points[0].y * axis.y; | |
for (i = 1; i < other.getNumberOfSides(); i++) | |
{ | |
tmp = other.points[i].x * axis.x + other.points[i].y * axis.y; | |
if (tmp > maxB) | |
maxB = tmp; | |
else if (tmp < minB) | |
minB = tmp; | |
} | |
/* correct for offset */ | |
tmp = other.center.x * axis.x + other.center.y * axis.y; | |
minB += tmp; | |
maxB += tmp; | |
/* test if lines intersect, if not, return false */ | |
if (maxA < minB || minA > maxB) { | |
return false; | |
} else { | |
var o = (maxA > maxB ? maxB - minA : maxA - minB); | |
if (o < overlap) { | |
overlap = o; | |
smallest = {x: axis.x, y: axis.y}; | |
} | |
} | |
} | |
return {"overlap": overlap + 0.001, "axis": smallest}; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment