Skip to content

Instantly share code, notes, and snippets.

@sdailey
Created September 20, 2012 01:22
Show Gist options
  • Star 2 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save sdailey/3753426 to your computer and use it in GitHub Desktop.
Save sdailey/3753426 to your computer and use it in GitHub Desktop.
Polygon overlap detection, javascript
function determinant(vector1, vector2)
{
return vector1.x * vector2.y - vector1.y * vector2.x;
}
function lineSegmentsIntersect(_segment1_Start, _segment1_End, _segment2_Start, _segment2_End)
{ //note the use of 'subtract'
det = determinant(_segment1_End.subtract(_segment1_Start), _segment2_Start.subtract(_segment2_End));
t = determinant(_segment2_Start.subtract(_segment1_Start), _segment2_Start.subtract(_segment2_End)) / det;
u = determinant(_segment1_End.subtract(_segment1_Start), _segment2_Start.subtract(_segment1_Start)) / det;
return (t >= 0) && (u >= 0) && (t <= 1) && (u <= 1);
}
function PointCollectionContainsPoint(area, point)
{
start = new Point(-100, -100);
intersections = 0;
for (i = 0; i < area.length; i++)
{
if (lineSegmentsIntersect(area[i], area[(i + 1) % area.length], start, point))
{
intersections++;
}
}
return (intersections % 2) == 1;
}
function PointCollectionsOverlap_Fast(area1, area2)
{
for (i = 0; i < area1.length; i++)
{
for (j = 0; j < area2.length; j++)
{
if (lineSegmentsIntersect(area1[i], area1[(i + 1) % area1.length], area2[j], area2[(j + 1) % area2.length]))
{
return true;
}
}
}
if (PointCollectionContainsPoint(area1, area2[0]) ||
PointCollectionContainsPoint(area2, area1[0]))
{
return true;
}
return false;
}
//Building array of points -- probably won't be relevant to your needs.
//I'm breaking apart google api objects here
count = 0;
area1= new Array(); //to be a collection of points
while(count< vertex.length){
innercount = 0;
lat = vertex[count]['$a'];
lng = vertex[count]['ab'];
pAdd = new Point(lng, lat);
if(area1.length < 1){
area1 = [pAdd];
} else
{
area1.push(pAdd);
}
count++;
}
count = 0;
area2=[]; //collection of points
area2= new Array();
count = 0;
while(count < compareArray.length){
//for each compared polygon
innercount = 0;
while(innercount< compareArray[count].length){
//console.log('compareArray');
//console.debug(compareArray[count][innercount]);
lat = compareArray[count][innercount]['$a'];
lng = compareArray[count][innercount]['ab'];
pAdd = new Point(lng, lat);
if(area1.length < 1){
area2 = [pAdd];
} else {
area2.push(pAdd);
}
innercount++;
}
PointCollectionsOverlap_Fast(area1, area2);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment