Разделение двух наборов точек по прямой
Предположим, у меня есть два набора точек, A и B, в 2D-пространстве. Я хочу знать, существует ли единственная прямая линия, которая будет иметь все точки A на одной стороне и все точки B на другой, и, если возможно, найти одну такую линию. я нашел этот вопрос при поиске, но это скорее проблема «линии наилучшего соответствия».
Интуитивно я чувствую, что это вопрос к перекрестным продуктам, но я не могу понять, как это можно сделать.
Решение
Вы можете найти выпуклую оболочку для каждого набора точек, а затем выполнить процедуру, описанную в этом вопросе, чтобы определить, пересекаются ли они (и, если нет, вернуть разделительную линию):
Как определить, пересекаются ли два выпуклых многоугольника?
Другие решения
В машинном обучении классическим решением этой проблемы является машина опорных векторов (SVM). Он будет обобщать до N измерений, найдет наилучшее приближение в случае, если решения не существует, а если будет несколько решений, он оптимизирует поля слева и справа от делителя. Возможно, излишним для вас, но есть несколько реализаций уже доступны. (Например, OpenCV)