title: Algorithm for finding a point in an irregular polygon
body: <p>Imagagine I have a polygon like the following:</p>
  
  <p><img src="https://i.stack.imgur.com/uANZ5.jpg" alt="Irregular Polygon"></p>
  
  <p>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.  </p>
  
  <p>For finding the center of mass I used the following algorithm:</p>
  
  <pre><code>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 &lt; 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;
          }
  </code></pre>
  
  <p>This works good with polygones like this:</p>
  
  <p><img src="https://i.stack.imgur.com/W0NTV.png" alt="L-Polygon"></p>
  
  <p>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.</p>
  
  <p>Does anyone has an idea how to get always points inside any polygon?</p>