13

Imagagine I have a polygon like the following:

Irregular Polygon

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:

L-Polygon

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?

Metalhead89
  • 1,740
  • 9
  • 30
  • 58
  • 9
    FYI, having the centre of mass outside of a polygon is perfectly correct and OK so the algorithm is probably working fine. (though maybe not for the context of your application?) – Chris Sinclair Jan 03 '13 at 11:46
  • 1
    http://stackoverflow.com/questions/11716268/point-in-polygon-algorithm – Mudassir Hasan Jan 03 '13 at 11:48
  • 5
    Divide the polygon into triangles using a **polygon triangulation** algorithm, and then use **barycentric coordinates** with arbitrary values that total 1.0 to derive points inside the triangles. – Rotem Jan 03 '13 at 11:52
  • "always getting a point inside a polygon" is not possible. But you can choose a point and test whether it's inside or outside using the odd-edge-intercepts method. You can choose the barycenters of the triangles generated by three consecutive vertices; at least two of them will be inside the polygon. – LSerni Jan 03 '13 at 11:56
  • @lserni Not if the middle vertex is concave. – Rotem Jan 03 '13 at 12:00
  • @Rotem, you don't stop at the first triangle - you have to test all of them. – LSerni Jan 03 '13 at 12:12
  • @lserni Sorry, I misread. – Rotem Jan 03 '13 at 12:18

2 Answers2

9

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;
Rotem
  • 21,452
  • 6
  • 62
  • 109
  • 1
    +1 for the triangularization :-). The OP may also want to look at libraries such as Clipper (http://www.angusj.com/delphi/clipper.php). – LSerni Jan 03 '13 at 12:26
  • Or easier: Just look at any three consecutive pairs; Half the time they'll be 'turning in' and their centroid will be in the polygon. The other half of the time they'll be 'turning out' and you just go to the next triple. Computing the 'turning' can be done just using the cross product. – Thomas Ahle Sep 06 '14 at 10:46
0

Use This:

private Point getCentroid(pointArray)
{
   double centroidX = 0.0;
   double centroidY = 0.0;

   for (int i = 0; i < pointArray.Length; i++)
   {
          centroidX += pointArray[i].X;
          centroidY += pointArray[i].Y;`
   }
   centroidX /= pointArray.Length;
   centroidY /= pointArray.Length;

   return(new Point(centroidX ,centroidY));
}

this code is just to find Center of Mass of Polygon. To check whether a point is inside or outside polygon check this link http://bbs.dartmouth.edu/~fangq/MATH/download/source/Determining%20if%20a%20point%20lies%20on%20the%20interior%20of%20a%20polygon.htm

Vipin Sharma
  • 594
  • 5
  • 19