Testing if a point is inside a Polygon

I’ve been playing with polygons and collisions lately so I decided to share some stuff.

Using rectangles to detect if the mouse is inside is handy for Buttons and rectangular shaped objects, but what about other irregular shaped objects?

Taking this into account I decided to create a Polygon class that basically has a List of Vector3 points. Although I’m just covering 2D collision you should use Vector3 for a more generic class.

Something like:

    class Polygon
    {
        public Polygon()
        {
            _vertexes = new List<Vector3>();
        }
 
        public void add_vertex(Vector3 v)
        {
            _vertexes.Add(v);
        }
 
        public List<Vector3> _vertexes;      
}

Now to the collision itself. A way to check if the point is inside is to compute the sum of the angles made between the test point and each pair of points making up the polygon. If this sum is 2 pi then the point is an interior point, if 0 then the point is an exterior point.

        bool isInside(ref Polygon polygon, Vector2 point)
        {
            int i;
            double angle = 0;
            Vector2 p1, p2;
            int n = polygon.get_vertex_count();
            for (i = 0; i < n; i++)
            {
                p1.X = polygon._vertexes[i].X - point.X;
                p1.Y = polygon._vertexes[i].Y - point.Y;
                p2.X = polygon._vertexes[(i + 1) % n].X - point.X;
                p2.Y = polygon._vertexes[(i + 1) % n].Y - point.Y;
                angle += getAngle(p1.X, p1.Y, p2.X, p2.Y);
            }
 
            if (Math.Abs(angle) < Math.PI)
                return false;
            else
                return true;
        }
 
        double getAngle(double x1, double y1, double x2, double y2)
        {
            double twoPI = 6.283185307179586476925287; // PI*2
            double dtheta, theta1, theta2;
 
            theta1 = Math.Atan2(y1, x1);
            theta2 = Math.Atan2(y2, x2);
            dtheta = theta2 - theta1;
            while (dtheta > Math.PI)
                dtheta -= twoPI;
            while (dtheta < -Math.PI)
                dtheta += twoPI;
 
            return (dtheta);
        }

That’s it for now. Robin, to the Code Cave!!!

3 Comments

  1. That’s a straight forward solution! The only drawback is that it only works for convex polygons. Concave ones will fail, e.g. in this example: http://yfrog.com/mkfalsificationp

    A common solution for detecting interior points is to draw a line from the point to any other point outside the polygon and counting the intersections with the polygon lines. If the count is odd the point lies within. Even counts tell you that the point is outside the polygon.

  2. Another solution would be to check if the point on the “inside” half space of the line.
    1. Calculate the vector of a point in the line minus the point being checked.
    2. Calculate the dot product between the previous vector and the normal of the line, if the angle is less-equals than 90° (in ALL lines of th polygon) then it’s inside.

    Note: the normal of the lines should be inward, meaning that should point to the half space inside the polygon. If not, the the angle of the dot product should be greater than 90°

  3. the theorem states that the point lies inside only if the sum is equal to 2pi then why are we comparing the value with pi only??

Leave a Reply