Point inside polygon collision detection

[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.

[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.

[avansc]

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"?

[cypher1554R]

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.

[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?

[cypher1554R]

Okay, I edited the link. It's there now.

[dandymcgee]

Hehe, I'm working on someone else's computer right now, but as soon as I'm finished I'll check out again.

[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

[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.