computer-science - 查找图形的外边缘

Question

查找图形外边缘的最佳方法是什么？

例如，这张图上的红色边:

我不知道这个算法有没有名字。这个名字足以帮助我在 Google 上找到一些东西。

Answer 1

我希望我没有误解这个问题，但我认为没有答案，除非你有图形的特定平面嵌入。

即使对于大多数平面图¹，您也可以重新排列节点，使不同的边位于“外部”。参见 Find border (boundary) edges of planar graph (geometric shape) .你的例子绝对不是平面的。

如果您有嵌入，则您要查找的内容与一组点的凸包 相关。这是 Dobb 博士关于它的文章 http://www.drdobbs.com/architecture-and-design/building-the-convex-hull/201806315 . “礼物包装”算法易于实现。

但是，给定图形嵌入的边界可能不是凸的，因此您必须修改算法以重新计算凸包的非边缘部分。 (您可以将其称为“收缩包装”算法)。

注 1:我能想到的唯一一类在平面中具有唯一嵌入的图是循环图。很可能还有其他人。 (编辑:至少在边界方面是独一无二的，你可以顺时针或逆时针嵌入一个循环)