包含给定点集的边界

Question

我现在使用的算法有点问题。我想让它划定界限。

下面是当前行为的一个例子：

以下是一个被通缉行为的示例：

C#中凸壳的当前代码：https://hastebin.com/dudejesuja.cs

我的问题是：

1） 这可能吗？

R:是的

2）这甚至被称为凸包吗？（我不这么认为）

R：不，这叫边界，link：https://www.mathworks.com/help/matlab/ref/boundary.html

3） 这会不会比传统的凸面船体对性能不那么友好？

R：据我研究，应该是相同的性能

4） 这个算法的例子是伪代码还是类似的？

R：还没有回答或者我还没有找到解决办法

Answer 1

考虑使用阿尔法形状，有时称为凹壳。https://en.wikipedia.org/wiki/Alpha_shape

它可以通过Delaunay三角剖分在时间O（N logn）内建立。

Answer 2

我会用不同的方法来解决这个问题。由于我们使用的是一组二维点，因此计算点区域的边界矩形很简单。然后我用水平线和垂直线将这个矩形分成“单元”，每个单元只需计算其边界内的像素数。由于每个单元只能有4个相邻单元（单元边相邻），因此边界单元将是至少有一个空相邻单元或单元边位于边界矩形边界的单元。然后沿着边界单元侧面构建边界。边界看起来像一个“楼梯”，但选择较小的单元大小将改善结果。事实上，细胞大小应该通过实验来确定；它不能太小，否则区域内可能会出现空细胞。点之间的平均距离可用作单元大小的下边界。

Answer 3

下面是一些计算alpha形状（凹形船体）并只保留外部边界的Python代码。这可能就是matlab的边界在里面做的事情。

from scipy.spatial import Delaunay
import numpy as np


def alpha_shape(points, alpha, only_outer=True):
    """
    Compute the alpha shape (concave hull) of a set of points.
    :param points: np.array of shape (n,2) points.
    :param alpha: alpha value.
    :param only_outer: boolean value to specify if we keep only the outer border
    or also inner edges.
    :return: set of (i,j) pairs representing edges of the alpha-shape. (i,j) are
    the indices in the points array.
    """
    assert points.shape[0] > 3, "Need at least four points"

    def add_edge(edges, i, j):
        """
        Add an edge between the i-th and j-th points,
        if not in the list already
        """
        if (i, j) in edges or (j, i) in edges:
            # already added
            assert (j, i) in edges, "Can't go twice over same directed edge right?"
            if only_outer:
                # if both neighboring triangles are in shape, it's not a boundary edge
                edges.remove((j, i))
            return
        edges.add((i, j))

    tri = Delaunay(points)
    edges = set()
    # Loop over triangles:
    # ia, ib, ic = indices of corner points of the triangle
    for ia, ib, ic in tri.vertices:
        pa = points[ia]
        pb = points[ib]
        pc = points[ic]
        # Computing radius of triangle circumcircle
        # www.mathalino.com/reviewer/derivation-of-formulas/derivation-of-formula-for-radius-of-circumcircle
        a = np.sqrt((pa[0] - pb[0]) ** 2 + (pa[1] - pb[1]) ** 2)
        b = np.sqrt((pb[0] - pc[0]) ** 2 + (pb[1] - pc[1]) ** 2)
        c = np.sqrt((pc[0] - pa[0]) ** 2 + (pc[1] - pa[1]) ** 2)
        s = (a + b + c) / 2.0
        area = np.sqrt(s * (s - a) * (s - b) * (s - c))
        circum_r = a * b * c / (4.0 * area)
        if circum_r < alpha:
            add_edge(edges, ia, ib)
            add_edge(edges, ib, ic)
            add_edge(edges, ic, ia)
    return edges

from matplotlib.pyplot import *

# Constructing the input point data
np.random.seed(0)
x = 3.0 * np.random.rand(2000)
y = 2.0 * np.random.rand(2000) - 1.0
inside = ((x ** 2 + y ** 2 > 1.0) & ((x - 3) ** 2 + y ** 2 > 1.0)
points = np.vstack([x[inside], y[inside]]).T

# Computing the alpha shape
edges = alpha_shape(points, alpha=0.25, only_outer=True)

# Plotting the output
figure()
axis('equal')
plot(points[:, 0], points[:, 1], '.')
for i, j in edges:
    plot(points[[i, j], 0], points[[i, j], 1])
show()

编辑：根据注释中的请求，下面是一些将输出边集“缝合”为连续边序列的代码。

def find_edges_with(i, edge_set):
    i_first = [j for (x,j) in edge_set if x==i]
    i_second = [j for (j,x) in edge_set if x==i]
    return i_first,i_second

def stitch_boundaries(edges):
    edge_set = edges.copy()
    boundary_lst = []
    while len(edge_set) > 0:
        boundary = []
        edge0 = edge_set.pop()
        boundary.append(edge0)
        last_edge = edge0
        while len(edge_set) > 0:
            i,j = last_edge
            j_first, j_second = find_edges_with(j, edge_set)
            if j_first:
                edge_set.remove((j, j_first[0]))
                edge_with_j = (j, j_first[0])
                boundary.append(edge_with_j)
                last_edge = edge_with_j
            elif j_second:
                edge_set.remove((j_second[0], j))
                edge_with_j = (j, j_second[0])  # flip edge rep
                boundary.append(edge_with_j)
                last_edge = edge_with_j

            if edge0[0] == last_edge[1]:
                break

        boundary_lst.append(boundary)
    return boundary_lst

然后，可以浏览边界列表列表，并在每条边上附加与第一个索引对应的点，以获得边界多边形。