@RomirosR

Как найти все точки, которые равноудалены от данных с помощью манхэттенского расстояния?

Привет, перейдем к делу.

Формула манхэттенского расстояния: abs(x1 - x2) + abs(y1 - y2), где x1, y1, x2, y2 - координаты точек, между которыми находится расстояние. abs - функция получения числа по модулю

Дано ограниченное двумерное пространство и координаты нескольких точек.
Задача:
Найти все точки, которые равноудалены от данных, используя манхэттенское расстояние.
  • Вопрос задан
  • 767 просмотров
Решения вопроса 2
@U235U235
Это называется дистанционное преобразование. В Matlab это функция bwdist(bw_img,'cityblock');
Ответ написан
Комментировать
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Вам равноудаленные или наиболее удаленные точки? Это немного разные вещи.

Равноудаленные точки - это надо пересекать "серединные перпендикуляры" для каждой пары заданных точек и смотреть, что решение одна и та же точка. Самые удаленные - это посмотреть на пересечения всех пар серединных перпендикуляров, перпендикуляров с границами области, вершины области. Из всех этих точек выбрать наиболее удаленные от всех заданных.

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы