Здравствуйте, Ulvred, Вы писали:

U>Здравствуйте, vadimcher, Вы писали:

V>>Скорее всего водоемы не меняются во времени, а зато поиск, возможно, надо осуществлять постоянно для разных точек A.
U>Верно, водоёмы не меняются во времени, точки А меняются

V>>В связи с этим имеет смысл построить заранее что-то типа диаграммы Вороного для множества точек береговых линий, такая диаграмма даст сразу для любой точки A ближайшую к ней точку ближайшего водоема.
U>А как по диаграмме Вороного определить какая именно точка береговой линии окажется ближайшей к точке А и соотвественно определить расстояние до этой точки?

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

Саму диаграмму Вороного строить можно различными способами. Самый простой -- это для заданной точки построить серединные перпендикуляры к отрезкам, соединяющим эту точку со всеми остальными, тогда образованный ими многоугольник будет ячейкой для данной точки. Такой алгоритм требует O(n^2*logn) времени. Если картинка статическая (что следует ожидать в случае водоемов), то сложность алгоритма не так важна. Ну займет это минут 30 один раз, зато затем только пользуй. Есть и другие способы, которые требуют достаточных навыков программирования, например, построение с помощью заметающей прямой. Прямая движется сверху вниз. Для каждой точки, которая выше этой прямой построена парабола -- множество точек, равноудаленных от этой точки и заметающей прямой. Совокупность всех нижних кусков парабол образует кривую линию над заметающей прямой. Все, что выше этой кривой линии -- там уже все вершины многоугольников Вороного известны. При движении прямой вниз параболы расширяются. Допустим при данном пооложении кривая линия образована кусками парабол 1, 2 и 3 в таком порядке, парабола i -- множество точек равноудаленных от заметающей прямой и точки i. При движении прямой вниз может так произойти, что нижний кусок параболы 2 сойдется в точку, а параболы 1 и 3 будут проходить через эту точку. Это означает, что эта точка равноудалена от точек 1, 2 и 3 и от прямой (т.е. находится дальше от любой точки ниже прямой). Такая точка и будет новой вершиной многоугольника Вороного -- она будет общей вершиной многоугольников точек 1, 2 и 3. Отмечаем эту вершину, забываем про параболу 2 и движемся дальше. Как-то так. Выигрыш: алгоритм требует O(n*logn) времени. Проигрыш: эффективная реализация алгоритма требует построения разных там списков и двоичных деревьев поиска, динамичекую их модификацию и т.д. В случае статической картинки и разумного числа вершин, игра не стоит свеч.

Остается вопрос поиска многоугольника Вороного для заданной точки. Как вариант, можно упорядочить все расчитанные вершины многоугольников по оси x, для двух соседних значений x хранить список многоугольников, попавших в вертикальную полосу между ними, и для каждого многоугольника в таком списке хранить минимальную и максимальную координаты по y. Тогда поиск полосы -- log(n), поиск многоугольника log от числа многоугольников в полосе.

Кстати, если у тебя информация представлена в виде карты, и есть возможность впихнуть дополнительную информацию в карту (например, под каждую точку карты выделено 4 байта, а палитру можно снизить до 65536 цветов, т.е два старших байта каждой точки использовать в личных целях), то можно сразу запомнить для каждой точки карты номер ближайшей к ней точки ближайшего водоема. Тогда поиск O(1).