Поиск целочисленной точки в треугольнике

stasyun

собственно есть треугольник на двухмерной плоскости
кто-нибудь знает алгоритм поиска в нём целочисленной точки?
или хотя бы не самой точки а факта наличия?

iri3955

Если вершины в целочисленных координатах, то формула Пика спасёт.

stasyun

вершины в рациональных, граница относится к треугольнику

antcatt77

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

blackout

Насколько я понимаю, это частный случай целочисленного программирования, которое NP-полно. Так что лучше, чем полный перебор не получится.

olga-sklyarova

Если числители и знаменатели координат не сверхбольшие, то можно попробовать следующий алгоритм.
Очевидно, модельный случай — это "вытянутый" треугольник. Применяя повороты на 90 градусов и сдвиги, сделаем так, чтобы самый острый угол лежал в I квадранте. Пусть теперь наш треугольник — треугольник OAB, OA>OB.
Воспользуемся "алгоритмом вытягивания носов", описанным в книжке Арнольда "Цепные дроби" (книжка для Малого мехмата, то есть для школьников). Он позволяет за время работы алгоритма Евклида для числителя и знаменателя (разложение в цепную дробь) для тангенса угла наклона прямой OA найти "ближайшие" к OA точки (строго говоря, если координаты A есть [math]$x_A$[/math], [math]$y_A$[/math], то можно рассмотреть треугольник [math]$y<y_A$[/math], [math]$x>x_A$[/math], [math]$\frac{y}{x} > \frac{y_A}{x_A}$[/math], и алгоритм даст границу выпуклой оболочки целых точек, попавших в этот треугольник). Теперь можно перебирать только эти точки. В среднем время работы логарифмическое от [math]$\max(x_A,y_A)$[/math], но в худшем случае линейное от них же.
Алгоритм можно несколько улучшить, проделав аналогичное построение с OB и сравнивая два полученных массива точек.

iri3955

Не, при сдвиге мы можем потерять целую точку.
Задачу можно свести в подсчёту кол-ва целочисленных точек в прямоугольном треугольнике, катеты которого лежат в целочисленных осях.
То есть нужна формула f(x, y) = кол-во точек внутри без гипотенузы, где x, y - длины катетов (а мне кажется, такая формула лекго выводится

olga-sklyarova

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

blackout

Задачу можно свести в подсчёту кол-ва целочисленных точек в прямоугольном треугольнике, катеты которого лежат в целочисленных осях.
Как? Вершины исходного треугольника не целые.

incwizitor

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

stasyun

правильно ли я понимаю, что вы утверждаете, что поиск целочисленной точки в симплексе NP-полная задача?
можно ссылку на пруф?

stasyun

ну этот алгоритм то понятен
хочется быстрого)

incwizitor

хочется быстрого)
ну давайте конкретнее: что тут небыстрого? :grin: :grin: :grin: :grin:

lenmas

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

incwizitor

Я так понял, что он хочет для очень узких треугольников
1) а я не понял :grin: ТС нигде об этом не сообщал
2) предложенный алгоритм справляется с этими ситуациями
3) я по-прежнему намекаю на то, что задача плохо сформулирована

lenmas

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

iri3955

Берём объемлющий прямоугольник и сокращаем его до целочисленного (в оставшейся рамке точек точно нет)
Разность между ним и треугольником предсталяется в в виде объединения рпрямоугольных треугольников, если исходный остроуголен.
В случае тупоугольного по-другому, но тоже раскладывается. Доказательство повторяет доказательство формулы Пика.

toxin

На онсайте кубка была задача - найти число целых точек в прямоугольном треугольнике [math]$x\ge 0, y\ge 0, Ax+By\le C$[/math]. Это делается через цепные дроби/алгоритм евклида, но это весьма не тривиально. Мне понадобилось кучу времени, чтобы придумать правильный алгоритм.
Задачу для симплекса можно свести к обобщению предыдущей, где [math]$x\ge0$[/math] заменено на [math]$x\ge r, r \in \mathbb{Q}, 0<r<1$[/math]. Возможно она решается схожим методом.

BoBochka

собственно есть треугольник на двухмерной плоскости
кто-нибудь знает алгоритм поиска в нём целочисленной точки?
или хотя бы не самой точки а факта наличия?
Вроде бы тривиальный алгоритм:
(1) Ищем отрезок-проекцию треугольника T на вертикаль. Целочисленные точки в этом отрезке — это горизонтальные линии, на которых мы будем искать искомую целочисленную точку.
(2) Обрабатываем последовально каждую из этих горизонтальных прямых L так:
находим пересечение L c T (напр. просто считаем координаты концов по коэффициентам в уравнениях ребер треугольника). Это отрезок. Если длина отрезка больше или равна единице, то искомая целочисленная точка в нем есть. Если меньше единицы, то проверяем, есть ли целочисленная точка на этом отрезке.
/* Можно добавить шаг оптимизации: проходить по списку горизонтальных линий L, начиная с тех, которые могут иметь наиболее длинное пересечение с T, чтобы увеличить вероятность раннего обнаружения искомой целочисленной точки */
P.S. Этот алгоритм тривиально обобщается на случай симплексов произвольной размерности.
Оставить комментарий
Имя или ник:
Комментарий: