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

Question

[RomirosR]

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

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

Дано ограниченное двумерное пространство и координаты нескольких точек.
Задача:
Найти все точки, которые равноудалены от данных, используя манхэттенское расстояние.

Comments

[Lynn «Кофеман»]

Три раза прочитал ничего не понял

[RomirosR]

Lynn «Кофеман», Так лучше?

[Lynn «Кофеман»]

Меня больше смущает что вы понимаете под двумерным пространством.
Обычно это бесконечная плоскость так что вопрос максимального удаления не имеет смысла.

[RomirosR]

Lynn «Кофеман», поправил

Answer 1

[U235U235]

Это называется дистанционное преобразование. В Matlab это функция bwdist(bw_img,'cityblock');

Answer 2

[Wataru]

Вам равноудаленные или наиболее удаленные точки? Это немного разные вещи.

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

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