包围给定点集的边界 [英] Boundary enclosing a given set of points
问题描述
我当前使用的算法存在一些问题。我希望它成为一个界限。
以下是当前行为的示例：
以下是通缉行为的MSPaint示例：
C＃中凸包的当前代码：
来自matplotlib.pyplot import *
＃构造输入点数据
np.random.seed（0）
x = 3.0 * np.random.rand（2000）
y = 2.0 * np.random.rand（2000）-1.0
内部=（（（x ** 2 + y ** 2> 1.0）&（（x-3）** 2 + y ** 2> 1.0）
点= np.vstack（[ x [inside]，y [inside]]）。T
＃计算alpha形状
edge = alpha_shape（points，alpha = 0.25，only_outer = True）
＃绘制输出
图（）
轴（'等于'）
图（points [:, 0]，points [:, 1]，'。'）
代表我，j在边缘：
plot（points [[i，j]，0]，points [[i，j]，1]）$ b $ b show（）
编辑：在注释中的请求之后，以下代码将输出边集缝合为连续边序列。
def find_edges_with（i，edge_set）：
i_first = [如果x == i，则j（x，j）为edge_set中的j]
i_second = [如果x == i，则edge_set中的（j，x）为j]
返回i_first，i_second
defitch_boundaries（edges）：
edge_set = edge.copy（）
boundary_lst = []
而len（edge_set）> 0：
边界= []
edge0 = edge_set.pop（）
boundary.append（edge0）
last_edge = edge0
而len（edge_set）> 0：
i，j = last_edge
j_first，j_second = find_edges_with（j，edge_set）
如果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]）＃翻转边缘rep
boundary.append（edge_with_j）
last_edge = edge_with_j
如果edge0 [0 ] == last_edge [1]：
中断
boundary_lst.append（boundary）
返回boundary_lst
然后您可以遍历边界列表的列表，并在每个边上附加与第一个索引对应的点，以获得边界多边形。
I am having a bit of a problem with an algorithm that I am currently using. I wanted it to make a boundary.
Here is an example of the current behavior:
Here is an MSPaint example of wanted behavior:
Current code of Convex Hull in C#:https://hastebin.com/dudejesuja.cs
So here are my questions:
1) Is this even possible?
R: Yes
2) Is this even called Convex Hull? (I don't think so)
R: Nope it is called boundary, link: https://www.mathworks.com/help/matlab/ref/boundary.html
3) Will this be less performance friendly than a conventional convex hull?
R: Well as far as I researched it should be the same performance
4) Example of this algorithm in pseudo code or something similar?
R: Not answered yet or I didn't find a solution yet
Here is some Python code that computes the alpha-shape (concave hull) and keeps only the outer boundary. This is probably what matlab's boundary does inside.
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
If you run it with the following test code you will get this figure, which looks like what you need:
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()
EDIT: Following a request in a comment, here is some code that "stitches" the output edge set into sequences of consecutive edges.
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
You can then go over the list of boundary lists and append the points corresponding to the first index in each edge to get a boundary polygon.
这篇关于包围给定点集的边界的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
