Алгоритм, который эффективно вычисляет расстояние одного помеченного пикселя до ближайшего другого помеченного пикселя
Я прошу прощения за мое длинное название. У меня есть два вопроса, где второй вопрос основан на первом.
(1). Предположим, у меня есть матрица, записи которой равны 0 или 1. Теперь я выбираю произвольную запись 0. Существует ли эффективный алгоритм, который ищет ближайшую запись с меткой 1 или вычисляет расстояние между выбранной записью 0 и ее ближайшей записью с меткой 1?
(2). Предположим теперь, что распределение записей 1 имеет геометрическое свойство. Чтобы сделать это утверждение более ясным, представьте эту матрицу как изображение. На этом изображении несколько непрерывных линий (не обязательно прямых). Эти линии образуют несколько границ, которые разделяют изображение на более мелкие фрагменты. Предположим, что границы обозначены 1, тогда как все пиксели в области разделения обозначены 0. Теперь, подобно (1), я выбираю случайный пиксель, обозначенный как 0, и я надеюсь выяснить координату ближайшего пикселя, обозначенного как 1 или расстояние между ними.
Намек / направление для части (1) мне достаточно. Если ввод ответа занимает слишком много времени, можно просто сказать мне название алгоритма, и я его посмотрю.
PS: Если я отправлю этот вопрос в неправильном разделе, пожалуйста, дайте мне знать. Я повторно отправлю это в соответствующий раздел. Спасибо!
1 ответ
Я думаю, что если у вас есть матрица, вы можете запустить версию BFS, где матрица A будет вашим графом G, а вершина v будет произвольным выбранным пикселем. Между любыми двумя соседними ячейками в матрице есть грань.