Разделите точки на плоскости с линией

Question

У меня есть N зеленых точек и M красных точек (ни один из них не colinear). Я хочу сказать, можно ли разделить эти точки с линией таким образом, чтобы все зеленые точки были на одной стороне, а все красные точки - с другой стороны. Если есть такая строка, я бы хотел найти ее уравнение. Линия не может пройти через эти точки. Каков самый быстрый алгоритм для решения этой проблемы? Это не домашнее задание, а проблема, о которой я недавно думал.

Answer 1

Построение convex hulls для обоих комплектов. Если они пересекаются, то нет такой разделительной линии

Citation:

Две модели множеств Xi и Xj называются линейно разделимы, если их выпуклые оболочки не пересекаются

Когда шелуха не пересекаются , строка might be found с rotating calipers

Answer 2

Это точно, что SVMs сделать. Более конкретно, SVM найдет линию, которая будет дальше от обоих наборов точек, если они будут linearly separable; В противном случае алгоритм может быть настроен на то, чтобы найти какое-то «лучшее усилие».

Есть много источников, где вы можете прочитать о SVM более подробно, но в основном вам нужно будет использовать линейное ядро. Например, вот the SVM implementation in scikit-learn, с некоторыми изображениями.

Answer 3

Используйте (один слой) perceptron, чтобы узнать separating hyperplane (прямая линия в двух измерениях), поставив проблему как проблему двоичной классификации.

Если два множества точек являются linearly separable, то одна такая гиперплоскость существует, то алгоритм Персептрон гарантированно сходятся и решение даст вам hyperplane (прямую линию в 2-х измерениях) разделения двух классов (зеленый и синий) ,

В случае, если решение не существует, алгоритм не сходится и мы можем остановиться после конечного числа итераций.

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

Мы также можем использовать perceptron pocket algorithm, а не использовать наивную реализацию, но для нашей цели также будет реализована наивная реализация (https://en.wikipedia.org/wiki/Perceptron).