所以我一直在用 Python 编写一个程序，该程序可以找到凸多边形的最小权重三角剖分。这意味着它找到了权重（所有三角形周长的总和），以及弦列表（穿过多边形的线将其分解为三角形，而不是边界）。
我的印象是我正在使用动态编程算法，但是当我尝试使用更复杂的多边形时，它需要很长时间（我不确定需要多长时间，因为我还没有完成它）。
它适用于 10 边多边形，但我正在尝试 25，这就是让它停滞的原因。我的老师给了我多边形，所以我认为 25 应该也可以工作。
由于该算法应该是O(n^3)，因此 25 边多边形的计算时间大约要长 15.625 倍，但是看到 10 边似乎是瞬时的，需要更长的时间。
我是否在那里进行了某种我没有意识到的 n 操作？我看不到我正在做的任何事情，除了最后一部分我通过将列表变成一个集合来消除重复项，但是在我的程序中，我在转换发生之前在 decomp 之后放置了一个跟踪，它不是甚至达到了那个地步。
这是我的代码，如果你们需要更多信息，请询问。里面的东西使它需要更长的时间O(n^3)，我需要找到它，这样我就可以把它修剪掉。
#!/usr/bin/python
import math
def cost(v):
ab = math.sqrt(((v[0][0] - v[1][0])**2) + ((v[0][1] - v[1][1])**2))
bc = math.sqrt(((v[1][0] - v[2][0])**2) + ((v[1][1] - v[2][1])**2))
ac = math.sqrt(((v[0][0] - v[2][0])**2) + ((v[0][1] - v[2][1])**2))
return ab + bc + ac
def triang_to_chord(t, n):
if t[1] == t[0] + 1:
# a and b
if t[2] == t[1] + 1:
# single
# b and c
return ((t[0], t[2]), )
elif t[2] == n-1 and t[0] == 0:
# single
# c and a
return ((t[1], t[2]), )
else:
# double
return ((t[0], t[2]), (t[1], t[2]))
elif t[2] == t[1] + 1:
# b and c
if t[0] == 0 and t[2] == n-1:
#single
# c and a
return ((t[0], t[1]), )
else:
#double
return ((t[0], t[1]), (t[0], t[2]))
elif t[0] == 0 and t[2] == n-1:
# c and a
# double
return ((t[0], t[1]), (t[1], t[2]))
else:
# triple
return ((t[0], t[1]), (t[1], t[2]), (t[0], t[2]))
file_name = raw_input("Enter the polygon file name: ").rstrip()
file_obj = open(file_name)
vertices_raw = file_obj.read().split()
file_obj.close()
vertices = []
for i in range(len(vertices_raw)):
if i % 2 == 0:
vertices.append((float(vertices_raw[i]), float(vertices_raw[i+1])))
n = len(vertices)
def decomp(i, j):
if j <= i: return (0, [])
elif j == i+1: return (0, [])
cheap_chord = [float("infinity"), []]
old_cost = cheap_chord[0]
smallest_k = None
for k in range(i+1, j):
old_cost = cheap_chord[0]
itok = decomp(i, k)
ktoj = decomp(k, j)
cheap_chord[0] = min(cheap_chord[0], cost((vertices[i], vertices[j], vertices[k])) + itok[0] + ktoj[0])
if cheap_chord[0] < old_cost:
smallest_k = k
cheap_chord[1] = itok[1] + ktoj[1]
temp_chords = triang_to_chord(sorted((i, j, smallest_k)), n)
for c in temp_chords:
cheap_chord[1].append(c)
return cheap_chord
results = decomp(0, len(vertices) - 1)
chords = set(results[1])
print "Minimum sum of triangle perimeters = ", results[0]
print len(chords), "chords are:"
for c in chords:
print " ", c[0], " ", c[1]
我将添加我正在使用的多边形，第一个多边形马上就解决了，而第二个多边形到目前为止已经运行了大约 10 分钟。
第一：
202.1177 93.5606
177.3577 159.5286
138.2164 194.8717
73.9028 189.3758
17.8465 165.4303
2.4919 92.5714
21.9581 45.3453
72.9884 3.1700
133.3893 -0.3667
184.0190 38.2951
第二个：
397.2494 204.0564
399.0927 245.7974
375.8121 295.3134
340.3170 338.5171
313.5651 369.6730
260.6411 384.6494
208.5188 398.7632
163.0483 394.1319
119.2140 387.0723
76.2607 352.6056
39.8635 319.8147
8.0842 273.5640
-1.4554 226.3238
8.6748 173.7644
20.8444 124.1080
34.3564 87.0327
72.7005 46.8978
117.8008 12.5129
162.9027 5.9481
210.7204 2.7835
266.0091 10.9997
309.2761 27.5857
351.2311 61.9199
377.3673 108.9847
390.0396 148.6748