Как найти все целочисленные точки отрезка?

Question

[Даниил Демидко]

Известен отрезок заданный двумя точками (x1, y1), (x2, y2).
Мне нужно найти все целочисленные точки лежащие на этом отрезке.
Как найти все эти точки?

Comments

[starboy03]

Количество целочисленных точек между (x0, y0) и (x1, y1) := НОД(|x0 - x1|, |y0 - y1|) + 1

Answer 1

[Rsa97]

Для произвольных (x₁, y₁) и (x₂, y₂), IMHO, только брать все целые значения между x₁ и x₂ и проверять значение y в полученных точках.
Для целочисленных (x₁, y₁) и (x₂, y₂) можно так:
n = НОД(|x₂ − x₁|, |y₂ − y₁|)
dx = (x₂ − x₁) / n
dy = (y₂ − y₁) / n
И взять все пары (x₁ + dx × i, y₁ + dy × i) для i = 1 .. n − 1

Comments

[Даниил Демидко]

А как называется этот алгоритм?

[Rsa97]

Даниил Демидко, Не знаю, есть ли у него название. Это просто следствие из свойств натуральных дробей.

[Даниил Демидко]

Спасибо вам, ваш способ работает в моей программе)

Answer 2

[Даниил Демидко]

Алгоритм Брезенхема?

Comments

[jcmvbkbc]

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

Answer 3

[Karpion]

Допустим, x1, y1, x2, y2 - целые.
Пусть x1=y1=0 (достигается: x2=-x1; y2=-y1;).

Ищем k=НОД(x2,y2) (там по ссылке есть алгоритмы).

Делим x2 и y2 на к - это координаты первой точки.
Умножаем координаты первой точки на 2,...,(k-1) - получаем все остальные точки (конечные точки и первая точка считаются уже найденными, их не выводим; если надо все - то ряд будет 0,1,...,k).

Answer 4

[Alexej Simakov]

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

В даны примеры
(1 1) (2 2 ) -> 2
(0 0) (-2 -2) -> 3
(1 1) (1 10) -> 10
Значит задача состоит в поиске целочисленных значений между двумя значениями.
Taкже мы исключим условие целочисленности концов отрезка. Чтобы решение стало универсальнее.

На питоне это можно сделать так:

код

i1 = -1.1
i2 = 8.9

input1 = int(i1)
input2 = int(i2)
print "==== will print for food ===="
print "      from "+str(input1)
print "     up to "+str(input2)
print "============================="

print [y for y in range(input1, input2+1)]

результат

==== will print for food ====
from -1
up to 8
========================
[-1, 0, 1, 2, 3, 4, 5, 6, 7, 8]