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

Ответ 1

alt text http://imagebin.ca/img/yhFOHb.png

Диаграмма

После того, как вы найдете пересечение строк L1:Ax+By=C и L2:ax+by=c, то есть точку A(x1,y1).

Определите еще две строки y = ceil(y1) и y = floor(y1), параллельные X-axis, и найдите их пересечение с L1 и L2 i.e. Точками B(x2,y2) и C(x3,y3).

Тогда вам нужно указать D или E, что ближе к точке A. Аналогичная процедура применяется к другим частям плоскости.

D ( ceil(x2), ceil(y1)  )
E ( ceil(x3), floor(y1) )

Ответ 2

Эта проблема относится к категории Целочисленная выпуклая оптимизация.

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

Его можно решить в три этапа:

• Сначала определите, на какой стороне каждой строки будет отвечать ответ, как показано в ответе TheMachineCharmer.
• Как только это известно, проблема может быть переписана как проблема выпуклой оптимизации (подробнее см. Wikipedia). Оптимизированная функция минимизирует (x - x0) ^ 2 + (y - y0) ^ 2, где x0 и y0 - координаты пересечения двух линий. Две линии кажутся линейным неравенством, например. "x + y >= 0", вместе образуя выпуклую область, ответ можно найти в. Отмечу, что решение будет (x = x0, y = y0) - то, что вам нужно с этого этапа, способ выразить проблема, аналогичная допустимой таблице для симплекс-метод.
• В-третьих, целочисленное решение можно найти, повторно добавив cuts, чтобы дополнительно ограничить допустимую область, пока решение проблемы выпуклой оптимизации не будет интеграл. На этом этапе может потребоваться много итераций в общем случае, но, глядя на представленную проблему и, в частности, на ее двумерную природу, я считаю, что она будет решена не более чем двумя сокращениями.

Ответ 3

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

Рассмотрим две строки:

10000019 * X - 10000015 * Y + 909093 >= 0    (L1)
-10000022 * X + 10000018 * Y + 1428574 >= 0  (L2)
A = 10000019, B = -10000015, C = -909093

Точка пересечения равна H:

Hx = -5844176948071/3, Hy = -5844179285738/3

Для точки M (X, Y) квадрат расстояния HM ^ 2 равен:

HM^2 = (9*X^2+35065061688426*X
    +68308835724213587680825685
    +9*Y^2+35065075714428*Y)/9

g = gcd (A, B) = 1: уравнение L1 A*X+B*Y+909093 может принимать любое целочисленное значение.

Коэффициенты Bezout, U = 2500004 и V = 2500005 подтверждают:

A * U + B * V = 1

Теперь перепишем задачу в "двойственном" базисе (K, T), определяемом формулой:

X = T*U - K*B
Y = T*V + K*A

После подстановки получим:

T+909093 >= 0
2*T+12*K+1428574 >= 0
minimize 112500405000369*T^2
   +900003150002790*T*K
   +1800006120005274*K^2
   +175325659092760325844*T
   +701302566240903900522*K
   +Constant

После дальнейшего перевода (сначала на T, затем на K, чтобы минимизировать постоянная во втором уравнении), T = T1-909093, K = K1 + 32468:

T1 >= 0
2*T1+4+12*K1 >= 0
minimize 112500405000369*T1^2
    +300001050000930*T1
    +900003150002790*T1*K1
    +1200004080003516*K1
    +1800006120005274*K1^2
    +Constant

Предлагаемый алгоритм - это цикл на T1. На самом деле нам не нужно петля здесь, так как лучший результат задается T1 = K1 = 0, что соответствует:

X = -1948055649352, Y = -1948056428573

Мой начальный пост ниже.

Вот еще одна идея алгоритма. Он может работать, но я не реализовал его...

При соответствующей смене знаков в соответствии с положением (x, y) проблему можно записать:

A*X+B*Y>=C  (line D)
a*X+b*Y>=c  (line d)
minimize the distance between M(X,Y) and H, the intersection point
A*b != a*B (intersection is defined)
A,B,C,a,b,c,X,Y all integers

Множество всех значений, достигнутых (AX + BY), является множеством всех кратных g = gcd (A, B) и существуют целые числа (u, v) такие, что Au + Bv = g (теорема Безу). Из точки с целыми координатами (X0, Y0) все точки с целыми координатами и одно и то же значение AX + BY являются (X0-KB/g, Y0 + KA/g) для всех целых чисел K.

Чтобы решить эту задачу, мы можем петлять на прямых, параллельных D на расстоянии от H, и содержать точки с целыми координатами.

• Вычислить g, u, v и H (координаты H, вероятно, не нужны, нам нужны только коэффициенты квадратичной формы, соответствующие расстоянию).

• T0 = ceil (C/g)

• Петля из T = T0

  а. Найдите K наименьшее (или наибольшее, в зависимости от знака aB-bA) целое число, проверяющее a * (Tu-KB/g) + b * (Tv + KA/g) >= c

  б. Держите точку (Tu-KB/g, Tv + KA/g), если ближе к H

  с. Выйдите из цикла, когда (T-T0) соответствует расстоянию от D больше, чем лучший результат, в противном случае продолжайте с T + = 1

Ответ 4

Я исследовал проблему в прошлом (и потому, что это весело, и потому, что я столкнулся с чем-то связанным в том месте, где я работал).

Насколько я знаю, для этой проблемы нет эффективного алгоритма (FPTIME).

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

Обобщение этого (ILP - целочисленное линейное программирование), как известно, является NP-полным.

Ответ 5

Чем больше я думаю об этом, тем больше кажется, что он превращается в линейное программирование Integer, которое является NP-полным в общем случае. http://en.wikipedia.org/wiki/Linear_programming#Integer_unknowns

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

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

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

Ответ 6

Как уже отмечали некоторые другие, это проблема целочисленного линейного программирования (аналогично линейным диофантовым неравенствам).

Посмотрите эту ссылку: Алгоритм ABS для решения класса линейных диофантовых неравенств и целых задач LP. Авторы утверждают, что способны решать такие системы, как

max (c ^T x) для Ax≤b, x∈Z ⁿ где c∈Z ⁿ b∈Z ^m A∈Z ^{m, n} m≤n.

В частности, полагая m = 2, n = 2, мы получаем задачу нахождения

max (c ^T x) для Ax ≤ b, x∈Z ² где c∈Z ² b∈Z ² A∈Z ^2,2.

Здесь A - матрица 2x2, а b, c и x - 2x1 столбчатые векторы.

Задача, изложенная ОП, может быть пересчитана таким образом (если ее попросят, я попытаюсь более подробно описать это).

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

Это похоже на то, что в общем классе методы ABS, которые, похоже, набирают силу в нескольких проблемных областях.

Последнее предложение раздела 2 документа также относится к другому методу решения.

Как указывает @Alan, тогда как общая проблема ILP - NP-Hard, проблема, заявленная здесь, может и не быть. Я не уверен, почему это так, но может быть, потому что матрица A равна 2x2 (а не nx2), и потому что ограничения могут быть выражены как целые числа.

Edit1: сложность алгоритма выглядит как O (1) (Кажется, что O (d), где d - размерность решетки. В этом случае d = 2). Мое удивление в этом - O (!!), и понимание и реализация этого по-прежнему O (??), хотя я пережил это несколько раз, и это выглядит более просто, чем я думал.

Ответ 7

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

Ответ 8

Вам, ребята, не хватает смысла! ха-ха, извините, не смог устоять.

Эй, представьте себе немного более простую ситуацию.

У вас есть одна линия, исходящая из начала координат, составляющая угол менее 90 градусов с осью x. Найдите ближайшую целую точку.

Проблема только с поиском точек решетки, пока вы не нажмете тот, который нам нужен в квадранте, так это то, что вы не знаете, как далеко искать. В случае очень, очень острого угла мы могли бы рассмотреть базиллион очков, прежде чем мы ударим того, что в нашем регионе.

Решение:

Решить: (Наклон линии) * Дельта (x) = 1.

то есть. Delta (x) = 1/(Наклон линии), где мы начинаем поиск. При условии ограничения Delta (x) > 1.

Иными словами, мы достаточно далеко выходим, что должно быть хотя бы целочисленное различие между координатами x и y.

В нашей задаче мы должны соответствующим образом преобразовать и tweedle числа, чтобы дать соответствующий диапазон ошибок. Delta (x) >= 2, Delta (x) = 2/(Slope of Line) Я думаю, что сделаю это с моей головы, но у меня нет карандаша.

Нет

Ответ 9

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

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

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

Ответ 10

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

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

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

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

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

Обновлено для добавления большего количества вещества

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

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

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

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

Изменить # 3 - назад по (un) популярному запросу!

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

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

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

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

Ответ 11

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

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

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

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

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

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

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

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

• Найти, если в интересующем нас сегменте находятся окружающие целые точки с координатами [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.

Ответ 12

Я делал что-то подобное, когда мне приходилось находить точку для маркировки многоугольника.

Конечным результатом было 70000 полигонов за 5 секунд на pentium 3 в Autocad. Так что около 3 секунд, если вы исключите Autocad.

Сначала вам нужно найти точку пересечения. Затем вам нужно найти, где находится ваша точка (x, y), и провести через нее горизонтальную или вертикальную линию, так что ваши 2 линии (A, B, C) и (a, b, c) и новый горизонтальный /verical line образуют треугольник. Как найти вертикальную или горизонтальную линию: Нарисуйте горизонтальную и вертикальную линии через точку (x, y), а затем проверьте: для горизонтального:   - если пересечения для линий A, B, C и вашей горизонтальной линии и строки a, b, c делают это уравнение работать (пересечение с A, B, C).x < x < (пересечение с a, b, c).x, то вы знаете свою внутренность. (вы можете переключать A, B, C и a, b, c, так же, как и внутри x.   - аналогично для y, просто проверьте y, а не x.

Итак, теперь у вас есть треугольник, и вы знаете, где он (слева, справа, вверх, вниз). например, если это правильный треугольник (например, график выше). Вы берете x точки пересечения, и вы его перекрываете (если он слева вы его пола). Аналогично для y координаты, если у вас есть треугольник вверх/вниз. Затем вы нарисуете через него линию развертки, паралель к вашей линии сканирования через вашу (x, y) точку и проверьте, есть ли у вас точка внутри пересечений (похожа на x < x < x выше, но с новой строкой), Если у вас нет целого числа внутри, тогда вам нужно переместить точку своего прохода дальше от точки пересечения. Вы должны рассчитать подходящий "шаг" на основе угла между двумя линиями (если линии параллельны и очень близки друг к другу, тогда угол будет небольшим, поэтому вам нужно сделать шаг, если угол широкий, небольшой шаг не требуется.

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

Ответ 13

Проблема проверки того, является ли точка частью математического конуса, довольно проста. Для двух векторов v, w любая точка в конусе, определяемая (v, w), будет на форме: z = a *** v ** + b *** w **, где a, b >= 0. Заметим, что для этого вам нужно будет переместить Origo на пересечение двух линий, Поскольку мы не можем предполагать конечную точность пересечения, вам нужно будет сделать математику с плавающей запятой и решить, достаточно ли близко к тому, что вы хотите.

• Найти векторы, определяющие 4 конуса (их бесконечно много, нам просто нужно 2 для каждого конуса), которые определяются двумя строками.
• Узнайте, какой конус содержит нашу точку, назовите этот конус для C.
• Возьмите 2 вектора, определяющие C, и найдите средний вектор (вектор, который разделил бы C на 2 одинаковых конуса), назовите его m.
• Пришло время начать цикл. Для простоты я собираюсь предположить, что мы ограничиваем себя n-битами на оси x и y. Обратите внимание, что для длины m вам понадобится целое число больше n-бит. Теперь выполните двоичный поиск по длине m, и каждый раз проверяйте 2 кольца (я подозреваю, что 1 кольцо вокруг будет достаточно). Когда вы нашли наименьшую длину, которая содержит точки C, проверьте, какая из этих точек самая близкая.

Наихудший рост будет O (log (sqrt (2 * n ^ 2)), где n - это длина, которую мы используем для представления оси x и y.

Можно так сказать "обратный двоичный поиск", если вы не знаете длину * m. Просто продолжайте удваивать длину, которую вы выходите, пока не найдете точки в C. Затем вы знаете 2 очка на m, и вы можете выполнить двойной поиск между ними.

Основная проблема со всем этим - точность, поэтому имейте это в виду. Альтернативные способы преследования могут включать в себя 2 полуплоскости, которые составляют конус. Каждый конус выше определяется пересечением двух полуплоскостей, и, возможно, проверка того, является ли точка членом полуплоскости достаточно простой, я не уверен.

Редактирование: это действительно намного проще с полуплоскостями, 2 линии делят R ^ 2 на 2 полуплоскости каждый, это дает 4 комбинации, которые будут 4 конусами. Поэтому каждый раз, когда вы хотите проверить, является ли точка членом конуса, вы должны проверить, является ли он членом 2 полуплоскостей, составляющих этот конкретный конус. Как это сделать, объясняется здесь:

http://www.mathsteacher.com.au/year9/ch04_linear_graphs/07_half/planes.htm

и было бы легче, чем перемещать Origo и возиться с точностью. Заменяя метод проверки членства и сохраняя все остальное одинаково, вы достигаете такого же роста.

Ответ 14

Вот линейное время (то есть O (# бит A, B, C и т.д.), предполагая, что бит вписывается в O (1) слова памяти) с использованием линейных тестов и двоичного поиска:

Предположим, что w.l.o. что B!= 0 (иначе мы заменим A на a, B с b и C на c). Выполните линейный тест, чтобы увидеть, какая сторона линии (A, B, C) включена. Предположим, что w1. что точка ниже (или включена) линии.

Заметим, что для произвольной x-координаты x 'мы можем вычислить наименьшее y' такое, что (x ', y') находится над линией (A, B, C) в O (1) раз через y ' = (C - A * x ')/B.

Теперь предположим w.l.o.g. что входная точка (x, y) находится справа от (a, b, c) или ниже в случае горизонтальной линии. Затем мы можем выполнить линейный тест (x ', y') относительно строки (a, b, c) и определить, нужно ли нам увеличивать x 'или уменьшать x', чтобы найти минимум x 'такой, что (x ', y') падает на правильную сторону (a, b, c).

Двоичный поиск этой точки занимает не более O (w) времени, где w - количество бит в A, B и т.д. Обратите внимание, что поскольку входные координаты x и y каждый поместится в целое число, то и возвращаемое значение, Даже если x и y не обязательно находятся в пределах этих границ, а линии были почти параллельны, подходящий x будет найден в течение O (w), потому что разница в наклонах равна A/B - a/b = (Ab - aB)/Bb = 1/2 ^ (2w), поэтому x-координата ответа будет вписываться в O (1) слова памяти. Нам еще нужно найти y-координату ответа, который также можно найти через двоичный поиск.

Ответ 15

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

Ответ 16

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

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

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

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

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

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

ИЗМЕНИТЬ

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

Ответ 17

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

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

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

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

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

X = (Y-b1)/m1

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

Ответ 18

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

Пусть две заданные строки: l ₁, а l ₂ (l ₁ менее крутой, чем l _{2суб > )}

• найдите X = (a, b), перекрестку l ₁ и l ₂.

• пусть k = 0

• Пусть v _k - вертикальная линия с координатой x x _k= floor (a-k)

• найдите точки пересечения v _k с l ₁ и l ₂ (точки V ₁= (x ₁, y ₁), V ₂= (x ₂, y _{2суб > )).}

• если floor (y ₁)!= floor (y ₂), целевая точка (x ₁), floor ( y ₁)) END.

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

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

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

• найдите X = (a, b), перекрестку l ₁ и l ₂.

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

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

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

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