代码之家 › 专栏 › 技术社区 › Chao Liu

VTK刀具输出

vtk line

Chao Liu · 技术社区 · 7 年前

我正在寻找一种连接所有具有相同坡度并共享一个公共点的线的解决方案。例如,加载STL文件并使用平面进行剪切后,刀具输出包括定义轮廓的点。将它们逐个连接形成一条(或多条)多段线。但是,如果某些直线的坡度相同并且共享一个公共点,则可以合并这些直线。E、例如,[[0,0,0]、[0,0,1]]和[[0,0,1]、[0,0,2]]可以用一条直线[[0,0,0]、[0,0,2]]表示。

我写了一个函数,可以分析所有的行,如果可以合并的话,可以连接它们。但当线路数量巨大时,这一过程就很慢。我在想,在VTK管道中,有没有办法进行线路合并?

干杯

plane = vtk.vtkPlane()
plane.SetOrigin([0,0,5])
plane.SetNormal([0,0,1])
cutter = vtk.vtkCutter()
cutter.SetCutFunction(plane)
cutter.SetInput(triangleFilter.GetOutput())
cutter.Update()

cutStrips = vtk.vtkStripper()
cutStrips.SetInputConnection(cutter.GetOutputPort())
cutStrips.Update()

cleanDataFilter = vtk.vtkCleanPolyData()
cleanDataFilter.AddInput(cutStrips.GetOutput())
cleanDataFilter.Update()
cleanData = cleanDataFilter.GetOutput()

print cleanData.GetPoint(0)
print cleanData.GetPoint(1)
print cleanData.GetPoint(2)
print cleanData.GetPoint(3)
print cleanData.GetPoint(4)

输出为:

(0.0, 0.0, 5.0) (5.0, 0.0, 5.0) (10.0, 0.0, 5.0) (10.0, 5.0, 5.0) (10.0, 10.0, 5.0)

将上述点逐个连接将形成表示切割结果的多段线。如我们所见,[点0,点1]和[点1,点2]可以合并。

下面是合并行的代码: 假设行由列表表示:[[(p0),(p1)],[(p1),(p2)],[(p2),(p3)],…]

appended = 0
CurrentLine = LINES[0]
CurrentConnectedLine = CurrentLine
tempLineCollection = LINES[1:len(LINES)]
while True:
    for HL in tempLineCollection:
        QCoreApplication.processEvents()
        if checkParallelAndConnect(CurrentConnectedLine, HL):
            appended = 1
            LINES.remove(HL)
            CurrentConnectedLine = ConnectLines(CurrentConnectedLine, HL)
    processedPool.append(CurrentConnectedLine) 
    if len(tempLineCollection) == 1:
        processedPool.append(tempLineCollection[0])
    LINES.remove(CurrentLine)
    if len(LINES) >= 2:
        CurrentLine = LINES[0]
        CurrentConnectedLine = CurrentLine
        tempLineCollection = LINES[1:len(LINES)]
        appended = 0
    else:
        break

解决方案:

我找到了一种使用vtk数据结构进一步加速此过程的方法。我发现多段线将存储在单元格中,可以使用GetCellType()进行检查。由于多段线的点顺序已经排序,因此不需要全局搜索哪些线与当前线共线。对于多段线上的每个点,我只需要检查点[I-1]、点[I]、点[I+1]。如果它们是共线的,则线的端点将更新到下一个点。此过程将继续,直到到达多段线的终点。与全局搜索方法相比,速度大幅提高。

1 回复 | 直到 7 年前

tomj 7 年前

不确定它是否是慢度的主要来源(取决于对共线性的正面点击数),但从向量中删除项目的成本很高(O(n)),因为它需要重新组织向量的其余部分,所以应该避免它。但即使没有关于共线性的点击 LINES.remove(CurrentLine) 调用确实会减慢速度,实际上也没有任何必要-只需保持向量不变,将最终结果写入新向量即可( processedPool )并摆脱 LINES 最后是向量。您可以通过为每个项创建一个bool数组(vector),并将其初始化为“false”,来修改算法,然后当您删除一行时,实际上并不删除它,而是将其标记为“true”,并跳过所有具有“true”的行,即类似这样的内容(我不会说python,因此语法不准确):

wasRemoved = bool vector of the size of LINES initialized at false for each entry
for CurrentLineIndex = 0; CurrentLineIndex < sizeof(LINES); CurrentLineIndex++
    if (wasRemoved[CurrentLineIndex])
        continue // skip a segment that was already removed
    CurrentConnectedLine = LINES[CurrentLineIndex]
    for HLIndex = CurrentLineIndex + 1; HLIndex < sizeof(LINES); HLIndex++:
        if (wasRemoved[HLIndex])
           continue;
        HL = LINES[HLIndex]
        QCoreApplication.processEvents()
        if checkParallelAndConnect(CurrentConnectedLine, HL):
            wasRemoved[HLIndex] = true
            CurrentConnectedLine = ConnectLines(CurrentConnectedLine, HL)
    processedPool.append(CurrentConnectedLine) 
    wasRemoved[CurrentLineIndex] = true // this is technically not needed since you won't go back in the vector anyway

LINES = processedPool

顺便说一句,真正正确的数据结构 线 用于这种算法的将是一个链表,因为从那时起,删除的复杂性将达到O(1),并且不需要布尔数组。但快速的google显示,在Python中列表并不是这样实现的,也不知道它是否会干扰程序的其他部分。或者,使用集合可能会使其更快(尽管我希望时间与我的“bool array”解决方案类似),请参阅 python 2.7 set and list remove time complexity

如果这不起作用,我建议您测量程序各个部分的时间,以找到瓶颈。