Page 1 of 1
Point inside polygon collision detection
Posted: Sun Nov 23, 2008 12:15 pm
by cypher1554R
I see a lot of ppl coming with this problem. I decided to show in a short (and hopefully friendly) app. how it can be done using vector's cross product checking. The deal is: The difference vectors of every next 2 vertices that form a triangle with the point, have to give a cross product that has the same sign for z coordinate of the product result throughout the whole polygon loop.
Don't ask me about the last sentence :D
Just look at the example (if you're interested):
mr.SanJin - point inside convex polygon collision detection(B).rar
I also included the release app. It's basically a pentagon that changes attributes on collision detection with the cursor.
This can be useful for user interface.
Note: It's written in OpenGL using the GLUT library. don't forget you need their .dll-s to have it working.
Re: Point inside polygon collision detection
Posted: Wed Nov 26, 2008 5:43 pm
by cypher1554R
Just wondering if this even works on other computers.. Anyone tried it yet?
edit: and no.. there's no bug or virus in it.. I grew over that.
Re: Point inside polygon collision detection
Posted: Wed Nov 26, 2008 6:07 pm
by avansc
cypher1554R wrote:Just wondering if this even works on other computers.. Anyone tried it yet?
edit: and no.. there's no bug or virus in it.. I grew over that.
what do you mean "works on other computers"?
Re: Point inside polygon collision detection
Posted: Wed Nov 26, 2008 6:33 pm
by cypher1554R
avansc wrote:what do you mean "works on other computers"?
If it executes on your computer without crashing / not starting etc..
I know that it shouldn't, but I can only try it on mine.
I'm not asking anyone to try it. I was just wondering if anyone did, and how it went. And also if it was useful (code), or was it too dirty to take out things from it.
Re: Point inside polygon collision detection
Posted: Wed Nov 26, 2008 8:27 pm
by dandymcgee
Code: Select all
PtInCPoly.exe - Entry Point Not Found
The procedure entry point __glutInitWithExit could not be located in the dynamic link library glut32.dll.
I'm too lazy to figure out what that means.. my guess would be that I have the wrong version of glut32.dll. Could you include the required libraries in the .rar?
Re: Point inside polygon collision detection
Posted: Thu Nov 27, 2008 3:28 am
by cypher1554R
Okay, I edited the link. It's there now.
Re: Point inside polygon collision detection
Posted: Sat Nov 29, 2008 8:09 pm
by dandymcgee
Hehe, I'm working on someone else's computer right now, but as soon as I'm finished I'll check out again.
Re: Point inside polygon collision detection
Posted: Mon Dec 15, 2008 12:15 pm
by avansc
i looked at that code, but i dont like it for some or other reason.
i think its mainly that i feel its worthless for having a 3 component vector if you are only using 2 components.
and there are computations that are inefficient.
here is what i came up with. its simpler, less code, and ~2X the speed. with the same precision.
Code: Select all
int side_of_line(Vec2 &a, Vec2 &b, Vec2 &p)
{
return float(p.y - a.y) * float(b.x - a.x) - float(p.x - a.x) * float(b.y - a.y);
}
bool point_inside_poly(std::vector<Vec2> &poly, Vec2 &point)
{
for(int i = 0; i < poly.size()-1; i++)
{
if(side_of_line(poly[i], poly[i+1], point) > 0)
return false;
}
if(side_of_line(poly[poly.size()-1], poly[0], point) > 0)
return false;
return true;
}
note that Vec2 is a struct with components float x, y.
here are the execution times for ITERATIONS = 10000000;
algo 1 = 15984 ms
algo 2 = 8219 ms
Re: Point inside polygon collision detection
Posted: Tue Dec 16, 2008 3:49 am
by cypher1554R
Interesting.. Although I wasn't really going for the speed. I was lazy and just copied vector computation code from my other project.
A good resume for someone looking for speed.
EDIT: BTW, does anyone know any good, easy method for point inside any poly? Meaning - it also works with concave polygons.