graph-theory - 如何从一组点中获取所有多边形

Question

我需要从一组点中获取所有多边形组合（凸面和凹面），但看不到这样做的方法。

我正在考虑这两种方法

• 检查每个组合是否为具有所有节点等级 2 的平面图
• 检查每个组合没有相交的顶点（求解方程组）

我是对的，还是完全迷路了？

提前致谢

Answer 1

我假设所有点都必须在多边形中。

首先，我将实施回溯方法。从一个点开始，如果它不与当前路径的边缘相交，则将边缘添加到非访问点，并在访问所有点时重复。最后，检查从第一个到最后一个路径点的边缘与路径相交。

可以进行其他检查以删除下一个可能的候选边缘。找到所有点的凸包。以凸包的一点为起点，假设路径（多边形）是有向的。这意味着多边形内部位于路径的左侧。必须以正序访问凸包上的点。这意味着最后一个路径点不能连接到凸点，除了最后一次访问之后（逆时针方向）。通过此检查，所有点都是凸包点的输入点集（例如常规 n 边形）将生成宽度为 1 的搜索树（列表）。由于如果所有点都在凸包上，则不可能创建凹多边形，因为两个非邻居之间的任何连接都会拆分点集，因为这两个部分之间不存在边缘而不与该边缘相交。