Algorithm for finding a point in an irregular polygon

Question

Imagagine I have a polygon like the following:

I am looking for a C# algorithm with whom I can find a point (could be the middlepoint or also a random point) inside any polygon.

For finding the center of mass I used the following algorithm:

private Point3d GetPolyLineCentroid(DBObject pObject, double pImageWidth, double pImageHeight)
        {
            Point2d[] pointArray = GetPointArrayOfRoomPolygon(pObject);

            double centroidX = 0.0;
            double centroidY = 0.0;
            double signedArea = 0.0;
            double x0 = 0.0; // Current vertex X
            double y0 = 0.0; // Current vertex Y
            double x1 = 0.0; // Next vertex X
            double y1 = 0.0; // Next vertex Y
            double a = 0.0;  // Partial signed area

            int i = 0;
            for (i = 0; i < pointArray.Length - 1; ++i)
            {
                x0 = pointArray[i].X;
                y0 = pointArray[i].Y;
                x1 = pointArray[i + 1].X;
                y1 = pointArray[i + 1].Y;
                a = x0 * y1 - x1 * y0;
                signedArea += a;
                centroidX += (x0 + x1) * a;
                centroidY += (y0 + y1) * a;
            }

            x0 = pointArray[i].X;
            y0 = pointArray[i].Y;
            x1 = pointArray[0].X;
            y1 = pointArray[0].Y;
            a = x0 * y1 - x1 * y0;
            signedArea += a;
            centroidX += (x0 + x1) * a;
            centroidY += (y0 + y1) * a;

            signedArea *= 0.5;
            centroidX /= (6.0 * signedArea);
            centroidY /= (6.0 * signedArea);

            Point3d centroid = new Point3d(centroidX, centroidY, 0);

            return centroid;
        }

This works good with polygones like this:

But if my polygon has the form of a C or something like that this algorithmn does not work because the center off mass is outside the polygon.

Does anyone has an idea how to get always points inside any polygon?

Answer 1

You can use polygon triangulation to break your polygon apart into triangles.

One such algorithm is demonstrated using c# in this CodeProject article.

Once you have triangles, finding arbitrary points that lie within the triangle is easy. Any barycentric coordinate with a sum of 1.0 multiplied by the vertices of the triangle will give you a point inside the triangle.

The center can be derived using the barycentric coordinate [0.333333, 0.333333, 0.333333] :

float centerX = A.x * 0.333333 + B.x * 0.333333 + C.x * 0.3333333;
float centerY = A.y * 0.333333 + B.y * 0.333333 + C.y * 0.3333333;

or more simply:

float centerX = (A.x + B.x + C.x) / 3f;
float centerY = (A.y + B.y + C.y) / 3f;