-1

我在二维空间中有一组点。这些点有两种不同的类型（比如少数点是黑色的，而其余的点是白色的）。我需要找到一种算法来找到将两个点子集分开的多边形。多边形的顶点可以是这两种点中的任何一种。

我尝试谷歌搜索，但找不到任何合适的算法。是否存在任何算法来做到这一点？

4

1 回答 1

0

您的问题不是很清楚，但我认为您只是在要求存在。考虑以下算法：

  1. 选择一种特定的颜色，比如黑色
  2. 使用直线将此顶点连接到所有其他黑色顶点。很可能，路径上不应该有白色顶点。
  3. 如果任何白色顶点正好在直线上，则无限绕道。
  4. 在这个由黑色节点形成的“星”网络周围画一个多边形。

只要您将多边形绘制得非常接近“星形”网络，就可以始终完成最后一步，因此您现在可以得到在 2D 中将黑色与白色点分开的多边形

于 2013-01-06T10:22:30.240 回答