c++ - 用直线分割两组点

Question

假设我在二维空间中有两组点 A 和 B。我想知道是否存在一条直线，其一侧的所有 A 点和另一侧的所有 B 点，如果可能，找到一条这样的线。我在搜索时发现了这个问题，但它更像是一个“最合适的线”问题。

直觉上，我觉得这是一个关于交叉产品的问题，但我无法弄清楚它是如何完成的。

score 2 · Accepted Answer

您可以找到每组点的凸包，然后按照此问题中的过程确定它们是否相交（如果不相交，则返回分界线）：

score 0 · Accepted Answer

在机器学习中，对此的经典解决方案是支持向量机 (SVM)。它将推广到 N 维，在没有解决方案的情况下找到最佳近似值，如果有多个解决方案，它将优化分隔线的左右边距。那么可能对你来说有点矫枉过正，但已经有多种实现可用。（例如 OpenCV）

2 回答 2