What's wrong with this code? Collision detection.

[mitz89]

I'm trying to detect if two polygons have intersected.
The Center point of PolygonA is -1,2.5 with points[a1(-4,4),b1(2,4),c1(-4,1),and d1(2,1)] and PolygonB is 2.5,2.5 with points[a2(1,4),b2(4,4),c2(1,1),and d2(4,1)]. Actualy one is a square and the other is a rectangle. Surely if you graph this they intersect with each other. Actually I just found this code and tried to test it manually. However it seems that when I test it it returns a no intersection which means it returns 0 instead of 1.
Need help..


typedef struct
{
double x;
double y;
} POINT;

typedef struct
{
POINT Center;
int NumSides;
POINT *Points;
} POLYGON;

/* Tests for a collision between any two convex polygons.
* Returns 0 if they do not intersect
* Returns 1 if they intersect
*/
int polypolyCollision(POLYGON *a, POLYGON *b)
{
POINT axis;
double tmp, minA, maxA, minB, maxB;
int side, i;

/* test polygon A's sides */
for (side = 0; side < a->NumSides; side++)
{
/* get the axis that we will project onto */
if (side == 0)
{
axis.x = a->Points[a->NumSides - 1].y - a->Points[0].y;
axis.y = a->Points[0].x - a->Points[a->NumSides - 1].x;
}
else
{
axis.x = a->Points[side - 1].y - a->Points[side].y;
axis.y = a->Points[side].x - a->Points[side - 1].x;
}

/* normalize the axis */
tmp = 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 = a->Points[0].x * axis.x + a->Points[0].y * axis.y;
for (i = 1; i < a->NumSides; i++)
{
tmp = a->Points[i].x * axis.x + a->Points[i].y * axis.y;
if (tmp > maxA)
maxA = tmp;
else if (tmp < minA)
minA = tmp;
}
/* correct for offset */
tmp = a->Center.x * axis.x + a->Center.y * axis.y;
minA += tmp;
maxA += tmp;

/* project polygon B onto axis to determine the min/max */
minB = maxB = b->Points[0].x * axis.x + b->Points[0].y * axis.y;
for (i = 1; i < b->NumSides; i++)
{
tmp = b->Points[i].x * axis.x + b->Points[i].y * axis.y;
if (tmp > maxB)
maxB = tmp;
else if (tmp < minB)
minB = tmp;
}
/* correct for offset */
tmp = b->Center.x * axis.x + b->Center.y * axis.y;
minB += tmp;
maxB += tmp;

/* test if lines intersect, if not, return false */
if (maxA < minB || minA > maxB)
return 0;
}

/* test polygon B's sides */
for (side = 0; side < b->NumSides; side++)
{
/* get the axis that we will project onto */
if (side == 0)
{
axis.x = b->Points[a->NumSides - 1].y - b->Points[0].y;
axis.y = b->Points[0].x - b->Points[a->NumSides - 1].x;
}
else
{
axis.x = b->Points[side - 1].y - b->Points[side].y;
axis.y = b->Points[side].x - b->Points[side - 1].x;
}

/* normalize the axis */
tmp = 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 = a->Points[0].x * axis.x + a->Points[0].y * axis.y;
for (i = 1; i < a->NumSides; i++)
{
tmp = a->Points[i].x * axis.x + a->Points[i].y * axis.y;
if (tmp > maxA)
maxA = tmp;
else if (tmp < minA)
minA = tmp;
}
/* correct for offset */
tmp = a->Center.x * axis.x + a->Center.y * axis.y;
minA += tmp;
maxA += tmp;

/* project polygon B onto axis to determine the min/max */
minB = maxB = b->Points[0].x * axis.x + b->Points[0].y * axis.y;
for (i = 1; i < b->NumSides; i++)
{
tmp = b->Points[i].x * axis.x + b->Points[i].y * axis.y;
if (tmp > maxB)
maxB = tmp;
else if (tmp < minB)
minB = tmp;
}
/* correct for offset */
tmp = b->Center.x * axis.x + b->Center.y * axis.y;
minB += tmp;
maxB += tmp;

/* test if lines intersect, if not, return false */
if (maxA < minB || minA > maxB)
return 0;
}

return 1;
}

[Marc G]

[ removed duplicate thread ]

[mitz89]

Really need help.. thanks..

[Vanaj]

Really need help.. thanks..

You might need to build in some tolerance...as if the diff is .000001 it won't show and intersection...

[mitz89]

You might need to build in some tolerance...as if the diff is .000001 it won't show and intersection...

What do you mean? Is the program working? because I haven't tried running it I just tested it manually however in testing it seems that the next loop in testing polygonA it already return 0 even if an intersection occured.

[Vanaj]

What do you mean? Is the program working? because I haven't tried running it
Load the points into the array and run through it in the debugger and see what happens...

I just tested it manually however in testing it seems that the next loop in testing polygonA it already return 0 even if an intersection occured.
How did you do this ??
What next loop are you talking about ??

[mitz89]

for (side = 0; side < a->NumSides; side++)
{
.....some codes
/* test if lines intersect, if not, return false */
if (maxA < minB || minA > maxB)
return 0;
}


when the side = 1 seems that the condition becomes True.
haven't tried running the program yet. I'm manually testing the program.
Why? does it give correct results?

[Vanaj]

for (side = 0; side < a->NumSides; side++)
{
.....some codes
/* test if lines intersect, if not, return false */
if (maxA < minB || minA > maxB)
return 0;
}


when the side = 1 seems that the condition becomes True.
haven't tried running the program yet. I'm manually testing the program.
Why? does it give correct results?

Double check the index values in the array...

[mitz89]

So you have already tried running the program?
So what happened?
I tried testing it twice but then on the condition part it enters the return 0 command.

[Vanaj]

So you have already tried running the program?
So what happened?
I tried testing it twice but then on the condition part it enters the return 0 command.
No I haven't..if you will post the project I will look it over..

[mitz89]

Actually it doesn't have a project yet. I just saw the code in a site and just tried testing it manually if the algorithm is correct.

[Vanaj]

Actually it doesn't have a project yet. I just saw the code in a site and just tried testing it manually if the algorithm is correct.
Again how did you "test" the program if you didn't run it ???

[mitz89]

Manually. Graph the two polygons assign their respective coordinates and just follow the flow of the program. That's why I'm quite not sure with the output because from the result of my tests it creates an error but also maybe it is a result of some miscalculations. I'm not sure if the program is indeed not working or it is just my mistake.

[Vanaj]

Best to make a project and load the chords into the array and step through the program in debug and see what values it gives..

[mitz89]

I tried creating a program however I get an access violation here:

int h;

POLYGON *g;
POLYGON *t;

g = new POLYGON();
t = new POLYGON();

g->Center.x = 6;
g->Center.y = 2;

g->NumSides = 4;

g->Points[0].x = 4; --->here..
g->Points[1].x = 4;
g->Points[2].x = 8;
g->Points[3].x = 8;

g->Points[0].y = 0;
g->Points[1].y = 4;
g->Points[2].y = 4;
g->Points[3].y = 0;

t->Center.x = 2.5;
t->Center.y = 2;

t->NumSides = 4;

t->Points[0].x = 0;
t->Points[1].x = 0;
t->Points[2].x = 5;
t->Points[3].x = 5;

t->Points[0].y = 0;
t->Points[1].y = 4;
t->Points[2].y = 4;
t->Points[3].y = 0;

h = polypolyCollision( g,t);


I just copied the same declaration of POLYGON from the given program.

[mitz89]

I was able to debug the program and it seems that the manual testing that I performed was right. It does have an error in the program. It return after the second loop of polygonA.