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