我有一个多边形,其中一些顶点用线连接(起点和终点是多边形的一个顶点)。每条线(连接顶点)有 4 条规则:
- 该线不与其他线相交
- 直线不与多边形相交
- 该线完全包含在多边形中
- 这条线不是多边形的边
h
行很好- 线
i
不好,因为它与多边形相交 - 行
j
是错误的,因为它与行h
和i
相交 k
线不好,因为它是多边形的一条边g
线不好,因为它不包含在多边形中
我有一个包含多边形顶点的数组和一个包含线的数组,如下所示:
polygon = [
{x: ..., y: ...},
...
]
lines = [
{
p1: {x: ..., y: ...},
p2: {x: ..., y: ...}
},
...
]
lines
数组只包含有效的行。
如何获得被线切割的多边形。
我想要这样的东西:
function getSlicedPolygons(polygon, lines){
// No check for valid lines, they are already valid
// Do the algorithm...
}
到目前为止我尝试了什么
我从第一个顶点开始,然后继续前进,直到到达连接的顶点。从那个顶点,我转到在线另一端连接的顶点。现在我继续下一步,直到另一个连接的顶点,依此类推,直到到达我开始的顶点。现在我有了第一个多边形。我找不到其他人...
代码(实现,不是真正的代码):
function getSlicedPolygons(polygon, line){
var results = []
var ofl = 0; // Overflow counter, to prevent infinite looping
while(lines.length > 0){
// Iterate through polygon
var i = 0;
var r = []; // Array of new indices
var iterations = 0; // An overflow counter again
while(i < polygon.length){
r.push[i]
// findNextConnectionIndex(...) searches for a line
// that connects with this vertex and returns the index of
// the other connected vertex
var n = findNextConnectionIndex(i, polygon, lines) || i+1
i=n;
// Don't loop infinite
iterations++;
if(iterations > 10) break;
}
var result = [];
for(var z = 0; z<r.length; z++){
result.push(polygon[r[z]])
}
results.push(result)
// Now I should do something to get another polygon next
// time ...
// Don't loop infinite
ofl++;
if(ofl >= 10) break;
}
return results;
}
它在一个数组中返回同一个多边形 10 次...
最佳答案
将多边形及其相交线视为带环的无向图,并对其应用环检测算法。由于我们知道连接线,事情变得更简单了,我们实际上可以在 O(V)
中解决问题。
这将是一个足以解释基本原理的模型。我们可以将我们的多边形转换为一个由线列表切片的矩形。由于没有线可能相交,这也将适用于生成的矩形。现在可以从图的一个 Angular 开始,沿着两条边行进,直到在两条路径上都到达 3 度的顶点。因此,我们找到了第一个由原始多边形切片得到的多边形。从上一步到达的两个点继续,直到再次到达 3 度的顶点。当两条路径相遇并且您已列出所有可能的多边形时终止此步骤。
该流程单步运行示意图:
寻找“Angular ”顶点
从图形/多边形中的任意点开始,沿多边形沿任意方向遍历顶点,直到到达 3 度的顶点。存储对应的切片线,沿着多边形继续前进,直到到达3度的顶点。如果是相同的切片线,则您找到了一个“Angular ”顶点,否则存储新的切片线并重复。
编辑
Python 中的工作实现:
def slice_polygon(poly, part):
# find the "corner point"
last_slice = None
last_pt = None
for pt in poly:
s = [x for x in part if pt in x]
if s:
if last_slice in s:
break
last_slice = s[0]
last_pt = pt
# find slicing starting from border-point
a = poly.index(last_pt)
b = (a + 1) % len(poly) # current positions on the polygon
sliced_poly = [] # current polygon
slicing = [] # list of all polygons that are created by the slicing
while a != b:
if not [x for x in part if poly[a] in x]:
# point doesn't lie on slicing-line => add to current polygon
sliced_poly.insert(0, poly[a]) # prepend point
a = (a - 1 + len(poly)) % len(poly) # advance a by one
elif not [x for x in part if poly[b] in x]:
# point doesn't lie on slicing-line => add to current polygon
sliced_poly.append(poly[b]) # append point
b = (b + 1 + len(poly)) % len(poly) # advance by one
else:
# append points of slicing line
sliced_poly.insert(0, poly[a])
sliced_poly.append(poly[b])
# store created polygon and start over
slicing.append(sliced_poly)
sliced_poly = []
# remove partitioning-line at which the algorithm stopped
part.remove([x for x in part if poly[a] in x and poly[b] in x][0])
# add last point to the current polygon, as it's not yet added to it
sliced_poly.append(poly[a])
# add last polygon to result-set
slicing.append(sliced_poly)
return slicing
# test
polygon = [(150, 110), (270, 40), (425, 90), (560, 150), (465, 290), (250, 290), (90, 220)]
partition = [((270, 40), (250, 290)), ((425, 90), (250, 290))]
print(slice_polygon(polygon, partition))
输出:
[[(425, 90), (560, 150), (465, 290), (250, 290)], [(270, 40), (425, 90), (250, 290)], [(90, 220), (150, 110), (270, 40), (250, 290)]]
由于总共有两个“Angular 点”(至少),如果我们遍历多边形一次,我们保证至少找到一个。
关于javascript - 来自多边形的连接顶点,如何获得新的多边形,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/42512118/