c# - 在不规则多边形中寻找点的算法

Question

假设我有一个如下所示的多边形:

我正在寻找一种 C# 算法，通过它我可以在任何多边形内找到一个点(可以是中间点，也可以是随机点)。

为了找到质心，我使用了以下算法:

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;
        }

这适用于像这样的多边形:

但是如果我的多边形具有 C 或类似的形式，则此算法将不起作用，因为中心偏离质量在多边形之外。

有谁知道如何始终在任何多边形内获取点？

Answer 1

您可以使用多边形三角剖分将多边形分成三角形。

在 this CodeProject article 中使用 c# 演示了一个这样的算法.

一旦有了三角形，就很容易找到位于三角形内的任意点。总和为 1.0 的任何重心坐标乘以三角形的顶点都会得到三角形内部的一个点。

可以使用重心坐标 [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;

或者更简单地说:

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