Python алгоритм построения прямой и нахождение, точек лежащих на прямой
Вопрос касательно моего предыдущего вопроса, прошу с ним ознакомиться.
Суть задачи из точки проводить луч(прямую) от верха до низа и находить такое положение прямой на которой будут лежать минимум 3 точки. По X время в unix, по Y всегда 4 точки. (на картинке немного не так) формат массива [[unix,v1,v2,v3,v4],[unix,v1,v2,v3,v4]...].
У меня не получается придумать алгоритм который бы выполнил задачу, помогите пожалуйста.
На GIF я намеренно пропустил несколько итераций чтобы не затягивать. Луч пускаем из каждой точи.
Ответы (2 шт):
А в чём проблема? Я не очень понимаю. Мне кажется, алгоритм очевиден:
- Выбираем очередную тройку точек (методом полного перебора)
- Проверяем, лежат ли эти точки на одной прямой.
И всё...
Полный перебор - три вложенных цикла. Если точек меньше ста, то цикл будет выполняться меньше миллиона раз - вполне допустимо. Нечто вроде:
for a in points:
for b in points:
for c in points:
if (a != b) and (b != c) and (a != c) :
# Проверяем - точки a, b и c - на одной прямой?
. . .
Как проверить, что точки лежат на одной прямой, я надеюсь знаете?
Перебор всех троек точек и проверка принадлежности их одной прямой - это первое решение, которое приходит в голову, но далеко не оптимальное. Комбинаций будет n^3. Вариант с пучками прямых (лучами) тоже n^3.
Более оптимальным будет вариант с построением прямых на всех парах точек. n-1 + n-2 + ... + 2 + 1 комбинаций.
- записываем уравнения всех прямых в виде y = kx + b (на первом же шаге отбрасываем векторы с одной нулевой координатой.)
- заносим в массив/список/словарь в виде "k_delim_b" => [[point1, point2], [point1, point2], ...] (так автоматом группируются все точки, принадлежащие одной и той же прямой)
- проходим по созданной структуре и выбираем те, в которых больше одной пары точек. (если правильно строить без повторов - т1 и т2-тN, т2 и т3-тN, ..., тN-1 и тN, то 2 пары точек - 100% три разные точки)
- выводим полученные точки.
Еще сильнее оптимизировать уже вроде никак.