расстояние между элементами матрицы

[tomsksmile]

Нужен простой алгоритм для решения задачи:
В булевой матрице A(n,m) найти минимальное и максимальное расстояние между элементами, равными 1.

расстояние это (поправьте если это не так):

Если элементы располагаются в одной строке (столбце), то расстояние это
A(i,j)-A(i,j+k) = k ( A(i+k,j)-A(i,j) = k ), если элементы располагаются в разных строках (и/или столбцах), то расстояние определяется по правилу треугольника Пифагора:
k = sqrt((A(i+p,j)-A(i,j))^2+(A(i,j+p)-A(i+p,j))^2)

[Akina]

Заранее составить матрицу расстояний

distance(i, j) = sqrt(i*i + j*j)

и считать расстояния

k = distance(abs(x1-x2), abs(y1-y2))

[tomsksmile]

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

[OpenGL]

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

Сообщение отредактировано: OpenGL - 23.10.08, 10:32

[tomsksmile]

OpenGL, спасибо. смотрю.

Сообщение отредактировано: tomsksmile - 23.10.08, 10:24

[amk]

В C есть такая функция - hypot(x, y) считает длину гипотенузы треугольника с катетами x и y.
Проще говоря - sqrt(x^2 + y^2). Не вызывает переполнений.

[OpenGL]

а дельфийская переполнение вызывает?

[Pavia]

OpenGL
Hypot из модйля math. Нет не вызывает. И еще она там с повышенной точностью, нежели прямой вариант.