Учитывая две прямые на плоскости, как найти целочисленные точки, наиболее близкие к их пересечению?

Question

Не могу решить:

Вам дано 8 целых чисел:

• A, B, C, представляющая линию на плоскости с уравнением A x + B y = C
• a, b, c, представляющий другую строку
• x, y представляет точку на плоскости

Две линии не параллельны, поэтому разделите плоскость на 4 части. Точка (x, y) лежит внутри одной из этих частей.

Проблема:
Напишите быстрый алгоритм, который найдет точку с целочисленными координатами в той же части, что и (x, y), которая является ближайшей к точке пересечения двух данных линий.

Примечание:
Это не домашнее задание, это старое задание типа Эйлера , к которому я абсолютно не знаю, как подойти.

Обновление: Можно предположить, что 8 чисел на входе - это 32-разрядные целые числа со знаком. Но вы не можете предполагать, что решение будет 32-разрядным.

Обновление 2: Трудный случай - когда линии почти параллельны - это суть проблемы

Обновление 3: Автор задачи утверждает, что решение является линейным O (n) алгоритмом. Где n - размер ввода (в битах). Т.е.: n = log (A) + log (B) + ... + log (y)
Но я все еще не могу решить это.

Пожалуйста, укажите сложности опубликованных алгоритмов (даже если они экспоненциальные).

Answer 1

Ну, это зависит от того, что считается достаточно быстрым.

Давайте назовем точку [x, y] P. Также я назову точки с целочисленными координатами «целочисленными точками».

Алгоритм, который я предлагаю:

1. Найдите точку Q, где эти две линии пересекаются. (Q = [x_q, y_q])

2. Получите функцию линии между Q и P, y = f (x) или обратную x = g (y);

3. Определите, является ли QP более вертикальным или горизонтальным в соответствии с его углом. Допустим, это вертикальное, чтобы упростить следующее решение (если оно горизонтальное, оси просто инвертируются, а где я пишу x, это будет y и наоборот).

4. Возьмем первую целочисленную координату y_1, идущую вдоль линии от Q к P.

5. Вычислить вторую координату этой точки: x_1 = f (y_1). Эта точка находится в нашем сегменте.

6. Найти, если окружающие целочисленные точки с координатами [floor (x_1); y_1] и [floor (x_1 + 1); y1] находятся в интересующем нас сегменте.

6.1 Если да, то мы перебираем горизонтальную линию x_3 = f (y_1), чтобы найти целую точку, которая все еще находится в нашем сегменте и имеет (x_3-x_q) -> min. Этот момент - наш ответ.

6.2 Если нет, то увеличьте y_1 на единицу и повторите с шага 5.

Answer 2

строка 1 определяется как y1 = m1 * x1 + b1. строка 2 определяется как y2 = m2 * x2 + b2.

m1, m2, b1, b2 - все известные значения [константы].

убедитесь, что m1 <> м2.

найти точку пересечения, т. Е. Где y1 == y2 и x1 == x2, определенные как (X, Y).

Y = ((m1 * b2) / m2) / (m1 / m2-1)

X = (Y-b1) / m1

Ближайшая точка может быть найдена путем округления X и Y до ближайшего целого числа. Вы решаете, что делать с .5

Answer 3

Вот частичная идея, которая может быть полезна для получения полного решения. Представьте, что две линии очень, очень близки друг к другу. Тогда любое интегральное решение между ними также будет интегральной точкой, которая очень близка к каждой прямой. Попробуем найти близкие целые точки к линии ax+by=c. Поскольку y = (c - ax)/b, нам нужно, чтобы y было очень близко к целому числу, поэтому b приблизительно делит c-ax. Другими словами, c-ax+D == 0 мод b для небольшого целого числа D.

Мы можем решить c-ax+D == 0 mod b для x: x = a^-1(c+D) mod b (a ^ -1 будет существовать, если a и b относительно простые, не уверен, что это так)

Таким образом, алгоритм должен оценить x = a^-1(c+D) mod b для D = 0, + 1, -1, + 2, -2, ... и попробовать полученные x, чтобы увидеть, работают ли они. Если на пересечении двух прямых есть близкие интегральные точки, они должны появиться в начале этой итерации. Конечно, вам, возможно, придется набрать D=b-1 в худшем случае ...

Answer 4

Из этих четырех частей плоскости один находится слева от обеих линий, один справа от обеих линий, один справа от одной и слева от другой линии, а последний - слева от одной и справа от другой линии. Это легче увидеть, если вы нарисуете его.

Относительное положение точки на линии зависит от результата этого определителя:

[1 p1x p1y; 1 p2x p2y; 1 p3x p3y], где p1 и p2 - две произвольные точки на линии, а p3 - заданная точка.

Если он равен нулю, точка находится на линии, если она больше нуля, это сторона, сторона зависит от относительного положения p1 и p2 в линии и от того, что вы считаете левым и правым на самолет.

Проблема заключается в выборе двух точек, которые соответствуют одинаковым критериям в обеих линиях, чтобы результаты были согласованными, возможно, p1 всегда имеет более низкое значение координаты x, чем p2 (координата y, если линия вертикальная).

Когда у вас есть обе точки для каждой линии, вычислите оба детерминанта, и все готово.

EDIT

Упс, это решает проблему частично. В любом случае вы можете вычислить сторону, с которой находится точка XY, вычислить пересечение, а затем вычислить относительное положение всех действительных точек (floor (x), floor (y)), (floor (x), ciel (y) ), ...

Answer 5

Я подозреваю, что это математическая задача оптимизации, которая может быть решена с помощью множителя Лагранжа ...

Answer 6

Мое предложение таково. Предположим, что участок плоскости, который содержит нашу целевую точку, полностью охватывает нижний левый квадрант, если смотреть с точки пересечения двух линий (другие квадранты аналогичны, и случай, когда участок плоскости охватывает более одного квадранта, будет рассмотрен позже).

Пусть две заданные строки будут l ₁ и l ₂ (l ₁"менее крутой", чем l ₂ )

1. найти X = (a, b), точку пересечения l ₁ и l ₂ .

2. let k = 0

3. пусть v _k будет вертикальной линией с координатой x x _k = этаж (a-k)

4. найти точки пересечения v _k с l ₁ и l ₂ (точки V ₁ = (x ₁ , y ₁ ), V ₂ = (x ₂ , y ₂ )).

5. если этаж (у ₁ )! = Этаж (у ₂ ), целевая точка равна (x ₁ , этаж (у * 1063) * 1 )) КОНЕЦ.

6. если floor (y ₁ ) == floor (y ₂ ), увеличить k и перейти к шагу 3.

Поскольку l ₁ и l ₂ не параллельны, abs (y ₁ - y ₂ ) должна расти с k. Когда abs (y ₁ - y ₂ ) становится больше 1, алгоритм наверняка остановится (хотя он может остановиться и раньше).

Теперь давайте рассмотрим (простой) случай, когда наша часть плоскости охватывает более одного квадранта, если смотреть с точки пересечения двух линий (она может охватывать два или три квадранта).

1. найти X = (a, b), точку пересечения l ₁ и l ₂ .

2. найти A, набор из четырех ближайших к X точек, имеющих целочисленные координаты

3. найти B, множество точек из A, которые находятся в целевой части плоскости.

4. точка от B, ближайшая к точке пересечения l ₁ , а l ₂ - целевая точка

(Этот случай выполняется в постоянное время.)

Answer 7

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

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

Вы должны иметь возможность проверять каждый целочисленный шаг на одной оси, чтобы определить, находится ли точка, которую вы тестируете, выше или между вашими двумя линиями (создайте новый вектор для этой точки от пересечения и определите наклон). Если точка выше, увеличьте шаг целого числа. Потому что вы тестируете наименьшее отличие градиента от одной из линий, это должно быть O (n). В алгоритме Брезенхамса их 8 секторов, а не только 4.

Answer 8

Я думаю, что есть 3 штуки к этому.

1. вычислите пересечение двух линий и удерживайте координаты X и Y этой точки

2. найдите участок, в котором находится данная точка. Это должно быть достаточно просто, потому что у вас есть наклон 2 линий, а также наклон линии, созданной данной точкой и точкой пересечения. Назовите их m_line1, m_line2 и m_intersect. Если m_intersect Существует формула для расчета разреза с использованием этих значений и местоположения заданной точки.

3. найти ближайшее целое число. Существует также прямое вычисление этого, когда вы знаете значения от # 1 выше, и наклоны от # 2. Вы можете перебор, но есть элегантное математическое решение.

Вот шаги, которые я предпринял, по крайней мере.

Обновлено, чтобы добавить больше вещества

Хорошо, я начну с обсуждения # 2.

Если вы вычислите наклон данной точки и точки пересечения, то вы получите m_intersection. Это наклон линии, которая проходит через точку пересечения. Давайте предположим, что m_line1 является наибольшим из 2 уклонов, так что линия 1 находится «выше» линии 2 при увеличении x после пересечения. Это облегчает поиск названий разделов. Мы будем называть секцию A секцией, заданной полоской между line1 и line2 для x, большей, чем координата пересечения x, а затем назовем остальные 3 секции по часовой стрелке, так что A и C противоположны друг другу.

Если m_intersection находится между m_line1 и m_lin2, то оно должно быть в одной из 2 секций A или C . Какой раздел является простой проверкой значения координаты x относительно координаты x пересечения. Мы определили A как раздел с большим значением. Аналогичный расчет можно сделать, если уклон находится за пределами m_line1 или m_line2.

Это дает вам раздел, в котором находится ваша точка. Все, что вы сделали, это вычислили 1 пересечение (5 умножений, 2 деления и несколько вычитаний, если вы делаете это традиционным способом), 3 склона, а затем пару целочисленных сравнений .

Edit # 3 - назад (не) популярным спросом!

Итак, вот как я вычислил # 3, ближайшую целую точку к пересечению. Возможно, он не самый лучший, но он использует бинарный поиск, поэтому это O (log n), где n связано с обратной величиной разности уклонов линий. Чем ближе они вместе, тем больше n.

Сначала возьмем разницу между наклонами двух линий. Скажи, что это 1/8. Это означает, что с точки пересечения вы должны пройти 8 единиц вдоль оси x, прежде чем вам будет гарантировано, что на оси y между двумя линиями есть целое число (оно может быть на одной из линий). Теперь, если само пересечение не находится на целочисленной координате х, то вам нужно выйти дальше, чтобы гарантировать, что ваша начальная точка находится на целочисленной координате х, но она ограничена. Если пересечение в точке х = 1,2, то в приведенном выше примере в худшем случае вы начнете с х = 41, а затем двигаетесь вниз на ~ 5 единиц вдоль оси у. Выберите либо потолок, либо этаж значения y, которое вы получите. Это не очень важно.

Теперь, когда у вас есть начальная точка, ближайшая точка может быть аппроксимирована бинарным поиском. Ваш новый отрезок линии находится между пересечением и начальной точкой, а ваши единицы движения кратны наклону этого отрезка. Рассчитайте среднюю точку отрезка и посмотрите, находится ли он между двумя линиями. Добавьте или вычтите 1, если это не прямое попадание, и если любое из этих попаданий, уменьшите оставшееся расстояние пополам и сделайте это снова. В противном случае ищите следующую половину сегмента.

Если у вас нет разницы наклона <1, я думаю, что проблема может быть проще (грубая сила пространства вокруг пересечения). Но это всего лишь особый случай поиска выше, когда вам не нужно далеко ходить, чтобы найти отправную точку. </p>