不包含连接多个点的算法
Algorithm to connect multiple points without inclusion
我正在寻找一种算法来连接多个点而不包括其中一个点。要求是所有点都已连接，但没有点位于生成的多边形的内部。我不确定这可能是什么技术术语，也没有找到任何可以解决我的问题的方法。该设置可能与此类似：
Setting
我不是寻找凸包算法，因为它可能包含一些点（在图像 2、6、8 中）。结果应该接近凸包（尽可能）但满足不包含任何点的要求。有什么建议吗？
从一个点开始，然后按顺时针（或 counter-clockwise 方式）转到另一个点。根据 Green's Formula 你应该对面积进行积分（在离散情况下，它相当于计算你的顶点）。
顺时针程序：假设您从 top-most 点开始 xi
- 从 xi 右侧的所有点中，选择最靠近 xi
的点
- 如果不存在：从 xi 左侧的所有点中，选择最靠近 xi
的点
- 如果你到达了 bottom-most 点，你现在就往上走，但使用相反的方法（即先检查左侧，然后检查右侧）
你可以从 0->1, 1->2, .. n-1 -> n, n->0 开始
现在看看这些线，看看它们是否交叉。
如果第 a-b 行与第 c-d 行交叉，则删除这两行并创建两条新行，即第 a-c 行和第 a-d 行。
由于我们正在删除交叉点，所有线的总长度总是在减少，所以它应该收敛到零交叉点和所有连接的东西..
我正在寻找一种算法来连接多个点而不包括其中一个点。要求是所有点都已连接，但没有点位于生成的多边形的内部。我不确定这可能是什么技术术语，也没有找到任何可以解决我的问题的方法。该设置可能与此类似： Setting
我不是寻找凸包算法，因为它可能包含一些点（在图像 2、6、8 中）。结果应该接近凸包（尽可能）但满足不包含任何点的要求。有什么建议吗？
从一个点开始，然后按顺时针（或 counter-clockwise 方式）转到另一个点。根据 Green's Formula 你应该对面积进行积分（在离散情况下，它相当于计算你的顶点）。
顺时针程序：假设您从 top-most 点开始 xi
- 从 xi 右侧的所有点中，选择最靠近 xi 的点
- 如果不存在：从 xi 左侧的所有点中，选择最靠近 xi 的点
- 如果你到达了 bottom-most 点，你现在就往上走，但使用相反的方法（即先检查左侧，然后检查右侧）
你可以从 0->1, 1->2, .. n-1 -> n, n->0 开始 现在看看这些线，看看它们是否交叉。 如果第 a-b 行与第 c-d 行交叉，则删除这两行并创建两条新行，即第 a-c 行和第 a-d 行。 由于我们正在删除交叉点，所有线的总长度总是在减少，所以它应该收敛到零交叉点和所有连接的东西..