Найти прямую, пересекающую наибольшее число отрезков
Вспомнилась задача, которую приходилось решать в самом первом семестре обучения в университете.
Вход:
Множество отрезков, каждый задается двумя точками. (координата начала - координата конца)
Выход:
Коэффициенты в уравнении прямой, пересекающей наибольшее число заданных отрезков. (Ax + By + C = 0)
Насколько помню, на тот момент я решал задачу так:
- Находил область на плоскости, в которой лежали все заданные отрезки.
- Расширял данную область в каждом направлении на небольшое значение. (пусть это будет 5)
- Перебирал все прямые, которые мог построить в данной области (от одного края до другого), проверял, сколько отрезков при этом прямая пересекает.
- Останавливался в тот момент, когда находил прямую, пересекающую все заданные отрезки, либо когда перебирать уже было нечего.
А какие у вас мысли по поводу алгоритма решения данной задачи?
Ответы (1 шт):
Можно попробовать решать методом, аналогичным алгоритму Хафа.
Для каждого отрезка известно семейство прямых в rho-theta пространстве, которые его пересекают.
Создаём двумерным массив-аккумулятор Н - сетку по rho и по theta нужной дискретности. Для каждого отрезка добавляем единицы в те ячейки Н, которые соответствуют уравнениям прямых, пересекающих отрезок. Для классического Хафа точка задаёт кривую дугу, здесь же будет изогнутая полоса.
После обработки отрезков находим ячейку аккумулятора Н с наибольшим значением. Она соответствует искомой прямой