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

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

альтернативный текст 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, т.е. точками B(x2,y2) и C(x3,y3).

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

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

Answer 2

Эта проблема относится к категории Integer Convex Optimization .

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

Это может быть решено в три этапа:

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

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

Коэффициенты Безу, 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 А / г), для всех целых чисел К.

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

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

2. T0 = ceil (C / g)

3. Петля от T = T0

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

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

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

Answer 4

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

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

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

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

Answer 5

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

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

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

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

Answer 6

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

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

max (c ^T x) для Ax≤b, x∈Z ⁿ , где c∈Z ⁿ , b∈Z ^m , A∈Z ^{м, n} , м≤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 (??), хотя я уже прошел через это несколько раз, и это выглядит более простым, чем я думал.

Answer 7

Вот линейное время (т. Е. O (# биты A, B, C и т. Д.), При условии, что биты вписываются в O (1) слов памяти), решение с использованием тестов на стороне строки и двоичного поиска: 1001 *

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

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

Answer 8

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

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

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

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

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

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

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

и было бы легче, чем перемещать Ориго и вертеть с точностью. Заменив метод проверки членства и оставив все то же самое, вы получите такой же рост.

Answer 9

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

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

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

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

Решение:

Решить: (Slope of Line) * Delta(x) = 1.

т.е. Delta(x) = 1/(Slope of Line), где мы начинаем поиск. С учетом ограничения Delta(x) > 1.

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

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

Нет

Answer 10

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

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

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

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

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