Разделение двух наборов точек по прямой

Question

Предположим, что у меня есть два набора точек, A и B, в 2D-пространстве. Я хочу знать, существует ли одна прямая линия, которая будет иметь все точки A с одной стороны и все точки B на другом, и, если возможно, найти одну такую ​​линию. Я нашел this вопрос во время поиска, но это скорее проблема «линии наилучшего соответствия».

Интуитивно я чувствую, что речь идет о кросс-продуктах, но я не могу понять, как это можно сделать.

Answer 1

Вы можете найти выпуклую оболочку для каждого набора точек, а затем выполните процедуру, описанную в этом вопросе, чтобы определить, если они пересекаются (и возвращают разделительную линию, если они не делают):

How do I determine if two convex polygons intersect?

Answer 2

В машинном обучении классическим решением является поддержка векторной машины (SVM). Он будет обобщать на N измерений, найти наилучшее приближение в случае, если нет решения, и если есть несколько решений, он будет оптимизировать поля слева и справа от разделителя. Возможно, для вас это может быть излишним, но уже есть несколько реализаций. (Например, OpenCV)