在形状上查找 corners/edges(可以定义该形状的最少顶点数)

Find corners/edges on a shape (minimum vertices that can define that shape)

我正在尝试获得以下形状的角:

拐角是指这个(红点):

可以定义此形状的最小点数。

我已经实施了以下内容:

    public Shape Optimize()
    {
        // If the vertices are null or empty this can't be executed
        if (vertices.IsNullOrEmpty())
            return this; // In this case, return the same instance.

        if (!edges.IsNullOrEmpty())
            edges = null; //Reset edges, because a recalculation was requested

        // The corners available on each iteration
        var corners = new Point[] { Point.upperLeft, Point.upperRight, Point.downLeft, Point.downRight };

        //The idea is to know if any of the following or previous vertice is inside of the the array from upside, if it is true then we can add it.

        Point[] vs = vertices.ToArray();

        for (int i = 0; i < vertices.Count - 1; ++i)
        {
            Point backPos = i > 0 ? vs[i - 1] : vs[vertices.Count - 1],
                  curPos = vs[i], //Punto actual
                  nextPos = i < vertices.Count - 1 ? vs[i + 1] : vs[0];

            // We get the difference point between the actual point and the back & next point
            Point backDiff = backPos - curPos,
                  nextDiff = nextPos - curPos,
                  totalDiff = nextPos - backPos;

            if (corners.Contains(backDiff) || corners.Contains(nextDiff) || corners.Contains(totalDiff))
                AddEdge(curPos, center); // If any of the two points are defined in the corners of the point of before or after it means that the actual vertice is a edge/corner
        }

        return this;
    }

这适用于矩形形状,但旋转的形状非常尖锐,因此,这段代码效果不佳:

但是形状的锐度只定义了侧倾角,那么我可以做些什么来改善它?

此外,我已经测试了 Accord.NET BaseCornersDetector inherited classes, but the best result is obtained with HarrisCornersDetector,但是:

许多 edges/corners 是不必要的,它们不在需要的地方(见第一张照片)。

好吧,经过数小时的研究,我找到了一个名为 Simplify.NET that internally runs the Ramer–Douglas–Peucker algorithm 的库。

此外,您可能对 Bresenham algorithm, with this algorithm you can draw a line using two Points 感兴趣。

使用此算法,您可以检查您的容忍度是否过高,将实际点与此算法输出的点进行比较,并制作某种相似度百分比计算器。

最后,有趣的是提一下 Concave Hull and Convex Hull 算法。

这一切都与Unity3D有关。

我的输出:

my implementation.

非常重要的一点是,需要对点进行排序以强制将它们连接起来。如果形状是凹形的,如您在第二张照片中看到的那样,您可能需要迭代形状的墙壁。

您可以查看实施示例 here。感谢@Bunny83。