算法找到一个点，一个不规则的多边形 [英] Algorithm for finding a point in an irregular polygon

问题描述

Imagagine我有类似如下的多边形：

Imagagine I have a polygon like the following:

我要寻找一个C＃算法与我能找到一个点（可能是middlepoint或还随机点）的任何多边形内部。

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

这工作良好，像这样polygones：

This works good with polygones like this:

但是，如果我的多边形具有C或类似的东西，这algorithmn不起作用，因为该中心起飞质量多边形之外的形式。

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?

推荐答案

您可以使用多边形三角以掰开你的多边形为三角形。

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

一个这样的算法使用此$ C $的CProject文章

一旦你有三角形，发现趴在三角形容易任意点。随着1.0的总和乘上三角形的顶点会给你三角形内一个点的任何重心坐标。

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.

该中心可以使用重心坐标导出[0.333333，0.333333，0.333333]：

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;

这篇关于算法找到一个点，一个不规则的多边形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！