擅长:python、mysql、java
<p>一种方法是选择阈值密度,将低于该阈值的所有体素转换为0,将高于该阈值的所有体素转换为1,然后在所有1-体素对中查找最短路径最长的1-体素对。这两个体素应该靠近最长的“绳子”的末端,而不管绳子的确切形状如何。你知道吗</p>
<p>可以定义一个图,其中每个1体素有一个顶点,每个1体素与其6个(或可能14个)相邻体之间有一条边。然后,可以使用广度优先搜索(这里不需要Dijkstra或Floyd Warshall,因为每条边都有权1),计算某个给定顶点u和O(| V |)时间和空间中其他每个顶点之间的最短路径的长度。对每个可能的起始顶点u重复此操作将给出一个O(| V | ^2)-时间算法。当你这么做的时候,要追踪到目前为止最远的一对。你知道吗</p>
<p>如果你的体素空间有w*h*d个单元,那么图中可能有w*h*d个顶点(如果每个体素都是1个体素),所以在最坏的情况下这可能需要O(w^2*h^2*d^2)时间,这可能是相当多的。幸运的是,如果你能负担得起一个稍微不精确的答案,有很多方法可以加快速度:</p>
<ul>
<li>仅从边界处的起始顶点计算最短路径,即具有少于6个(或14个)邻居的顶点。(我相信这不会牺牲最佳解决方案。)</li>
<li>或者,首先“骨架化”的图形,通过反复摆脱所有这样的边界顶点删除不会断开图形。你知道吗</li>
<li>选择起始顶点的一个好方法是首先选择任何顶点,然后始终选择一个与最后一个顶点的最大可能距离的顶点(当然还没有尝试过)。这将使您在3次迭代后获得一个非常好的最长-最短路径的近似值:距起始顶点最远的顶点将靠近两个绳索末端之一,距<em>该</em>顶点最远的顶点将靠近另一端!你知道吗</li>
</ul>
<p>注意:如果由于弯曲,绳子上彼此靠近的远点之间没有完整的体素间隙,那么最短路径将通过这些错误连接“短路”,并可能降低精确度。您可以通过增加阈值来改善这一点。如果门槛太高,绳子就会断开。我希望您希望选择仅导致1个连接组件的最高阈值。你知道吗</p>