Как проверить, лежит ли точка на (минимальной) линии Манхэттена?

Question

У меня есть матрица 8x10 с заблокированными квадратами:

no = [(2,4),(3,4),(6,4),(7,4),(2,5),(3,5),(6,5),(7,5)]

И мне нужно выяснить, является ли кратчайший (манхэттенский) путь между двумя точками, заданными этой функции в виде вложенного кортежаподобно ((0,5), (6,2)), содержит любой блок и перенаправляет его вокруг.

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

def manhattan_dist(move): #order doesn't matter
    a = move[0][0]
    b = move[0][1]
    c = move[1][0]
    d = move[1][1]
    mandist = abs(a-c)+abs(b-d)

    if (any (abs(a-box[0])+abs(b-box[1])) == (mandist-(abs(c-box[0])+abs(d-box[1]))) for box in no):
        print("blocked")
        #calculate go-around logic

    return mandist

Он печатает «заблокировано» для manhattan_dist(((0,1),(0,7))), так что я знаю, что я тоже делаю что-то не так в питоне.

Answer 1

Теперь, чтобы сделать это, я пытался применить логику, которая работает для евклидова расстояния, чтобы увидеть, находится ли C на линии между A и B, добавив расстояние от A до C к расстоянию от C доB и выяснение, равно ли оно A B

Используемая здесь математическая концепция называется "метрикой".Это всего лишь обобщение евклидова расстояния, с которым вы уже знакомы.Подробнее см. статья в Википедии .Манхэттенское расстояние удовлетворяет всем требованиям метрики.Это означает, что вы можете быть уверены, что если d(A, B) + d(B, C) = d(A, C), то B лежит на некотором кратчайшем пути между A и C.В отличие от евклидова расстояния, может быть много путей от A до C с одинаковым расстоянием, и многие из них могут проходить через B.

Answer 2

Отвечая, а не комментируя из-за отсутствия повторения (... я новичок здесь).
Мне кажется немного нечетким.Манхэттенское расстояние не имеет ни одного кратчайшего пути ... На самом деле оно по определению имеет много кратчайших путей.
Так что, возможно, попробуйте уточнить, что вы имели в виду?

Кстати, если вы хотите знать, заблокированы ли какие-либо манхэттенских путей, то это просто означает, что у вас есть поле с

min([a, c]) < box[0] < max([a, c]) and min([b, d]) < box[1] < max([b, d])

---

Правитьиз-за обсуждения в комментариях:
Прежде всего, всегда есть точно abs(a-c) + abs(b-d) , выбирайте abs(a-c) путей с минимальным манхэттенским расстоянием.(Извините за плохую запись; просто следуйте параграфам вопросов и, к сожалению, отсутствует поддержка латекса).
Если вы правильно просмотрите геометрию, все минимальный блокируемый путь довольно сложен и не будет быстрым,Я не вижу, как можно избежать обхода всех путей, с некоторой оптимизацией, полученной путем сортировки путей в иерархическое дерево и удаления полных ветвей, когда квадрат заблокирован ...