PDA

View Full Version : Inside and outside of a polygon



uNsignedINT
05-28-2003, 09:38 AM
Hello, I'm working with VC++ and GL constructing regular and non-regular polygons! How can i know if a point is inside the polygon??
Thanks!!

hkyProgrammer88
05-28-2003, 11:48 AM
Hello,

I will elaborate more later (hopefully).

Try reducing the problem to determining if a point is inside or outside of a triangle.

One way which I hear is not great is to measure the angles formed when you join every vertex of the triangle to your point. If the angles add up to 360 then the point is inside. (That is, if the point is inside the triangle, then it will be like the hub of a wheel, and the joining line segments are the spokes. If the angles make 360 then it must be inside the triangle, ie. is a proper hub).

Another way would be to determine the center of the triangle. Then determine if the line segment from your point to the center point crosses any of the 3 triangle lines/edges. If so, then the point is outside (you should note the special case when your point is on a triangle line/edge).

There are probably others. Also be aware that these two methods have draw backs due to precision and possible computation time.

cragwolf
05-28-2003, 05:06 PM
A nice "point in polygon" function is implemented here:
http://home.earthlink.net/~bobstein/inpoly

It works with integers, but you should be able to deal with that.

uNsignedINT
05-29-2003, 07:02 AM
Thank you all!!! I will take a look at the site...
Thanks for the tip of the triangle..
See ya :-)