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

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

Назовем точку [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) -> мин. Этот вопрос является нашим ответом.

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

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

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

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

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

строка 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

Я был делать что-то подобное, когда мне нужно было найти точку для разметки многоугольника.

Окончательный результат составил 70000 полигонов за 5 секунд на Pentium 3 в Autocad. Это примерно 3 секунды, если исключить Autocad.

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

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

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

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

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

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

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

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

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

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

Если вы вычисляете наклон данной точки и точки пересечения, то вы получаете m_intersection . Это наклон линии, проходящей через точку пересечения. Предположим, что m_line1 является большим из двух наклонов, так что линия 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 - назад по (не) популярному спросу!

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

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

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

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

Вот частичное представление, которое может быть полезно для получения полного решения. Представьте, что эти две линии очень, очень близки друг к другу. Тогда любое интегральное решение между ними также будет интегральной точкой, которая находится очень близко к каждой линии. Попробуем найти близкие интегральные точки к прямой 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 в худшем случае ...

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

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

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

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

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

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

РЕДАКТИРОВАТЬ

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

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

Ознакомьтесь с этой ссылкой: Алгоритм 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.

Проблема, заявленная OP, может быть переформулирована таким образом (если спросят, я постараюсь изложить это более подробно).

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

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

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

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

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

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

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

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

2. пусть k = 0

3. пусть v _k будет вертикальной линией с координатой x x _k = floor (ak)

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

5. если этаж (y ₁ )! = Этаж (y ₂ ), целевая точка будет (x ₁ , этаж (y ₁ )) КОНЕЦ.

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 ₂ является целевой точкой

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

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

Рассмотрим две прямые:

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 может принимать любое целочисленное значение.

Коэффициенты Безу, 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

Набор всех значений, достигнутых (A X + B Y) - это набор всех кратных g = gcd (A, B), и существуют целые числа (u, v) такие, что A u + B v = g (теорема Безу). Из точки с целыми координатами (X0, Y0) все точки с целыми координатами и одинаковым значением A X + B Y равны (X0-K B / g, Y0 + K ] A / g) для всех целых чисел K.

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

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

2. T0 = ceil (C / g)

3. Цикл из T = T0

   a. Найдите K наименьшее (или наибольшее, в зависимости от знака Bb A) целое число, проверяющее a * (T uK B / g) + b * (T v + K A / g)> = c

   b. Сохраните точку (T u-K B / g, T v + K A / g), если она ближе к H

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

Вы, ребята, упускаете суть! хаха, извини, не удержался.

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

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

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

Решение:

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

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

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

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

Нет?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 и найдите их пересечение с L1 и L2 т.е. точки L2. т.е. точки B(x2,y2) и C(x3,y3).

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

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