用直线划分两组点

Question

假设我在2D空间中有两组点，A和B。我想知道是否存在一条直线，它的一侧有a的所有点，另一侧有B的所有点。如果可能的话，找到一条这样的线。我在搜索时发现了这个问题，但它更像是一个"最佳匹配线"问题。

直觉上，我觉得这是一个关于交叉产品的问题，但我不知道如何做到。

Answer 1

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

如何确定两个凸多边形是否相交？

Answer 2

在机器学习中，这方面的经典解决方案是支持向量机（SVM）。它将推广到N维，在没有解的情况下找到最佳近似，如果有多个解，它将优化除法器的左右边缘。对您来说可能有些过头了，但已经有多种实现可用。（例如OpenCV）