Outermost Polygon from a set of Edges

Question

Suppose I have a set of 2d line segments that are all connected. I need an algorithm that finds the outermost segments in the set. That is, the minimal subset that bounds the same region.

Note: this is not the same as finding the convex hull of the points making up the segments.

Edit: On the top is the initial set of segments. Below that is the same outline with interior segments deleted. (Ignore the little grey crosses, they're just to mark intersection points.)

Answer 1

你会用铅笔怎么做……？

1. 找到最左边的顶点（最小 x）。如果有多个，请选择其中最低的（最小 y）。当前顶点下方没有顶点，因此以“向下”方向作为参考。
2. 找到所有从当前顶点出发的边并计算它们的方向（方位角）。找到与参考方向成最小正角（逆时针）的那个。那将是大纲部分。
3. 选择它的另一端作为新的“当前”顶点，并将从该顶点到最近顶点的方向设置为新的参考方向。
4. 从第 2 步继续，直到到达起始顶点。
5. 删除所有未访问的段。
6. 移除所有孤立顶点（如果在步骤 5 中出现过）。