Имеется карта некоторой области, на которой отмечены водоёмы. Водоёмы заданы наборами координат точек своих береговых линий.
То есть имеется N массивов точек (каждая точка задаётся своими координатами X и Y). Каждый массив описывает координаты точек береговой линии водоёма.
На той же карте распложена ещё одна точка (назовём её точкой А).
Береговые линии имеют неправильную форму и могут быть как выпуклые так и невыпуклые. Координаты точек задаются вещественными числами с плавающей запятой.
Карта достаточно большая — каждая береговая линия задаётся несколькими тысячами точек.
Необходимо найти кратчайшее до береговой линии ближайшего водоёма. Расстояние меряется по прямой от точки А до ближайшей к ней точки каждого водоёма.
Вопрос: как решить данную задачу? Измерение расстояний до каждой точки каждой береговой линии не годится т.к. точек очень много.

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

U>Имеется карта некоторой области, на которой отмечены водоёмы. Водоёмы заданы наборами координат точек своих береговых линий.
U>То есть имеется N массивов точек (каждая точка задаётся своими координатами X и Y). Каждый массив описывает координаты точек береговой линии водоёма.
U>На той же карте распложена ещё одна точка (назовём её точкой А).
U>Береговые линии имеют неправильную форму и могут быть как выпуклые так и невыпуклые. Координаты точек задаются вещественными числами с плавающей запятой.
U>Карта достаточно большая — каждая береговая линия задаётся несколькими тысячами точек.
U>Необходимо найти кратчайшее до береговой линии ближайшего водоёма. Расстояние меряется по прямой от точки А до ближайшей к ней точки каждого водоёма.
U>Вопрос: как решить данную задачу? Измерение расстояний до каждой точки каждой береговой линии не годится т.к. точек очень много.

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

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

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

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

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

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

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

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

S>>Хорошая идея тут сделать диаграмму Вороного и в процессе ее построения взять какую-то сетку на карте (скажем, из квадратиков) и для каждой ячейки сетки запомнить список вершин водоемов, области которых пересекаются с этой ячейкой.
U>Великовата сетка получается. Может быть есть другой способ?

Великовата? Размеры сетки можно задавать руками. Можно взять и 100х100, и тоже будет неплохо работать.

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

U>Вопрос: как решить данную задачу? Измерение расстояний до каждой точки каждой береговой линии не годится т.к. точек очень много.

R1. [Замена водоема более простой фигурой] Аппроксимировать каждый водоем окружностью (эллипсом, прямоугольником) таким образом, чтобы фигура покрывала водоем. Можно также аппроксимировать каждый водоем несколькими фигурами.

R2. [Оцениваем снизу расстояние] Для каждого водоема высчитываем наименьшее расстояние от заданной точки до фигуры, которая аппроксимирует водоем. В результате ты получишь массив r_min[i], i = 1,N, N количество фигур, которые аппроксимируют водоем.

R3. [Сортируем оценки] Сортируем оценки r_min[i]. Пусть R_min[j] уже отсортированный массив оценок (j = 1,N), Idx[j] это индекс водоема, которому соответствует оценка R_min[j].

R4. [Подготовка к циклу] Полагаем J := 1, MinDistance = бесконечность

R5. [Уточнение расстояние] Уточняем расстояние до водоема Idx[J] по методу каждой точки. Получаем некоторое значение d. Если d меньше чем MinDistance, то MinDstance := d и индекс ближайшего водоема NearestLake := Idx[J]. После этого увеличиваем J := J + 1 и если J меньше либо равно N, то переходим на R4

R6. [Конец] Ближайший водоем имеет индекс NearestLake, расстояние до него MinDistance.

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

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

U>>Вопрос: как решить данную задачу? Измерение расстояний до каждой точки каждой береговой линии не годится т.к. точек очень много.

M>R1. [Замена водоема более простой фигурой] Аппроксимировать каждый водоем окружностью (эллипсом, прямоугольником) таким образом, чтобы фигура покрывала водоем. Можно также аппроксимировать каждый водоем несколькими фигурами.

Конечно, если водоем имеет форму множества Мандельброта, то этот алгоритм мало чем поможет.

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

...
M>>R1. [Замена водоема более простой фигурой] Аппроксимировать каждый водоем окружностью (эллипсом, прямоугольником) таким образом, чтобы фигура покрывала водоем. Можно также аппроксимировать каждый водоем несколькими фигурами.

M>Конечно, если водоем имеет форму множества Мандельброта, то этот алгоритм мало чем поможет.

А если аппроксимировать выпуклой оболочкой точек водоёма? Каждому ребру оболочки будет соответствовать интервал точек из множества. При пересечении линии с ребром оболочки детализируем место пересечения для всех отрезков соответсвующего интервала.

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

A>А если аппроксимировать выпуклой оболочкой точек водоёма? Каждому ребру оболочки будет соответствовать интервал точек из множества. При пересечении линии с ребром оболочки детализируем место пересечения для всех отрезков соответсвующего интервала.

Тут любой индекс подойдет, который бы позволил отсекать большие группы точек.

Здравствуйте, 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).

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

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

Это, конечно, замечательно, но оценка сложности верна для случая, когда точки разбросаны по карте более-менее равномерно. Для случая, когда они собраны в контура водоемов может быть ситуация, когда длинные сектора от выпуклой границы водоема идут под углом к x-y координатам. При этом по мин-макс координатам вокруг выбранной точки может оказаться до тысяч различных многоугольников и всех их придется перебирать, а это уже совсем не log(n).

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

Вот это уже лучше. Только почему просто не взять дополнительный массив? И если, конечно, хочется получить не приближенный ответ, а точный, то надо рассматривать ситуацию, когда в клетку карты попадает несколько разных многоугольников и всех их перебирать.

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

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

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

S>Это, конечно, замечательно, но оценка сложности верна для случая, когда точки разбросаны по карте более-менее равномерно. Для случая, когда они собраны в контура водоемов может быть ситуация, когда длинные сектора от выпуклой границы водоема идут под углом к x-y координатам. При этом по мин-макс координатам вокруг выбранной точки может оказаться до тысяч различных многоугольников и всех их придется перебирать, а это уже совсем не log(n).

Число многоугольников не может быть больше, чем число точек. Поэтому если поиск внутри полосы будет действительно log от числа многоугольников, имеющих с данной полосой общую область, то за logn мы никуда не вылезем.

Как такой поиск осуществить? Пересечение любого многоугольника с заданной полосой -- это либо пустое множество (или точка -- нам все-равно), либо треугольник, либо трапеция. Почему? Потому что если какая-то сторона попала в полосу, то она должна идти от левого края до правого, т.к. мы провели полосы через ВСЕ вершины многоугольников. Кстати, таких вершин также O(n). Таким образом пересечение полосы и многоугольника можно задать уравнениями двух прямых -- верхней части и нижней части полученной трапеции. Ну а теперь поиск в двоичном дереве по уравнениям этих прямых делается за log на ура. Что не так?

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

S>>Это, конечно, замечательно, но оценка сложности верна для случая, когда точки разбросаны по карте более-менее равномерно. Для случая, когда они собраны в контура водоемов может быть ситуация, когда длинные сектора от выпуклой границы водоема идут под углом к x-y координатам. При этом по мин-макс координатам вокруг выбранной точки может оказаться до тысяч различных многоугольников и всех их придется перебирать, а это уже совсем не log(n).

V>Число многоугольников не может быть больше, чем число точек. Поэтому если поиск внутри полосы будет действительно log от числа многоугольников, имеющих с данной полосой общую область, то за logn мы никуда не вылезем.

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

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

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

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

S>>>Это, конечно, замечательно, но оценка сложности верна для случая, когда точки разбросаны по карте более-менее равномерно. Для случая, когда они собраны в контура водоемов может быть ситуация, когда длинные сектора от выпуклой границы водоема идут под углом к x-y координатам. При этом по мин-макс координатам вокруг выбранной точки может оказаться до тысяч различных многоугольников и всех их придется перебирать, а это уже совсем не log(n).

V>>Число многоугольников не может быть больше, чем число точек. Поэтому если поиск внутри полосы будет действительно log от числа многоугольников, имеющих с данной полосой общую область, то за logn мы никуда не вылезем.

S>А если поиск внутри полосы будет не за log(n)? Мы же при поиске в полосе находим все многоугольники, которые по второй координате захватывают выбранную точку. Таких многоугольников может быть довольно много (предположим, они идут в косую полоску по полосе, которая их во много раз шире).

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

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

В реальности -- не может. Это же не просто какие-то многоугольникии какие-то полосы. Многоугольника Вороного, а полосы построены через их вершины. Если у тебя и будет полоса с O(n) трапеций, то O(n) оставшихся полос будут иметь O(1) трапеций. Что касается памяти, то здесь ее уж точно требуется гораздо меньше, чем для любых приемлемых сеток, например.

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

S>А если поиск внутри полосы будет не за log(n)? Мы же при поиске в полосе находим все многоугольники, которые по второй координате захватывают выбранную точку. Таких многоугольников может быть довольно много (предположим, они идут в косую полоску по полосе, которая их во много раз шире).

Хотя, вообще, если действовать по другому, то можно попать и в log(n). Это если искать нужную трапецию в полосе методом деления пополам (а не находить все подходящие по min-max координатам многоугольники).

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

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

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

V>Как это будет не за log(n)? Если у тебя n точек на прямой, заранее известных, сможешь поиск за log(n) организовать?

Да, согласен.

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

V>В реальности -- не может. Это же не просто какие-то многоугольникии какие-то полосы. Многоугольника Вороного, а полосы построены через их вершины. Если у тебя и будет полоса с O(n) трапеций, то O(n) оставшихся полос будут иметь O(1) трапеций. Что касается памяти, то здесь ее уж точно требуется гораздо меньше, чем для любых приемлемых сеток, например.

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

Можно, правда, подумать о каком-то более эффективном представлении полос, то есть как-то учитывать, что многоугольники в одной полосе являются продолжением многоугольников в другой, но это уже довольно сложно.

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

U>А как по диаграмме Вороного определить какая именно точка береговой линии окажется ближайшей к точке А и соотвественно определить расстояние до этой точки?

Чтобы сразу получить ответ на это вопрос диаграмма Вороного в такой ситуации строится не классческая "точечная", а реберно-вершинная, т.е. каждая ячейка диаграммы Вороного соответутвует либо вершине какого-то водоема, либо ребру какого-то водоема. Когда мы определили, в какую ячейку попала очередная тестовая точка, мы сразу знаем конкретный водоем и конкретный элемент его границы. Если элемент границы — вершина, то это и есть ближайшая точка. Если элемент границы — ребро, то на него придется опустить перпендикуляр, который даст нам ближайшую точку.

Однако решение с настоящей Евклидовой диаграммой Вороного — практически чересчур трудоемко, ибо в общем случае границы ячеек реберно-вершинной диаграммы Вороного будут отрезками парабол, а не прямых. Задача сильно упростится, если перейти к какой-другой метрике (манхеттен? L-inf?). Если же все таки нужен строго именно Евклид, то лучше пять раз подумать, прежде чем ввязываться в диаграммы Вороного. Может хватит обычного перебора с парой-тройкой эвристик?

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

АТ>(Ответа на вопрос о том, как каким образом предлагается решать задачу именно по традиционной точечной даграмме Вороного я пока не увидел. Может плохо смотрел? Перебором соседних ячеек Вороного?).

В частности, осмелюсь заметить, что если традиционная диаграмма Вороного говорит вам, что ближайшей вершиной является вершина Х водоема В, это совсем не означает, что Х является искомой ближайшей точкой границы. Более того, это даже совсем не означает, что искомая ближайшая точка принадлежит именно водоему В.

Здравствуйте, Андрей Тарасевич, Вы писали:

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

U>>А как по диаграмме Вороного определить какая именно точка береговой линии окажется ближайшей к точке А и соотвественно определить расстояние до этой точки?

АТ>Чтобы сразу получить ответ на это вопрос диаграмма Вороного в такой ситуации строится не классческая "точечная", а реберно-вершинная, т.е. каждая ячейка диаграммы Вороного соответутвует либо вершине какого-то водоема, либо ребру какого-то водоема. Когда мы определили, в какую ячейку попала очередная тестовая точка, мы сразу знаем конкретный водоем и конкретный элемент его границы. Если элемент границы — вершина, то это и есть ближайшая точка. Если элемент границы — ребро, то на него придется опустить перпендикуляр, который даст нам ближайшую точку.

АТ>Однако решение с настоящей Евклидовой диаграммой Вороного — практически чересчур трудоемко, ибо в общем случае границы ячеек реберно-вершинной диаграммы Вороного будут отрезками парабол, а не прямых. Задача сильно упростится, если перейти к какой-другой метрике (манхеттен? L-inf?). Если же все таки нужен строго именно Евклид, то лучше пять раз подумать, прежде чем ввязываться в диаграммы Вороного. Может хватит обычного перебора с парой-тройкой эвристик?

Никто не предлагает реберно-вершинную. Зачем? Просто вершинную, т.к. водоемы оппроксимированы набором точек, причем, судя по изначальному посту, БОЛЬШИМ числом точек. А ребра здесь совсем ни к месту. Так как ребро, как прямой отрезок, будет также аппроксиммацией к реальной береговой линии. Более того, если точки расставлены достаточно близко (ну не знаю, не более 10-100 метров, в зависимости от задачи), то расстояние до точки будет хорошей аппроксимацией для расстояние до берега (не до отрезка, их соединяющего, а до реального берега), если же они расставлены далеко, то, наверное, добавление отрезка даст прирост точности, но только такая точность отношения к реальному берегу имеет все меньше, чем больше расстояние между точками, зато усложняет задачу многократно. Уж лучше тогда на этом отрезке просто промежуточных точек понаставить, а то получается какая-то охота за ложной точностью.

Здравствуйте, Андрей Тарасевич, Вы писали:


АТ>>(Ответа на вопрос о том, как каким образом предлагается решать задачу именно по традиционной точечной даграмме Вороного я пока не увидел. Может плохо смотрел? Перебором соседних ячеек Вороного?).

Я так понимаю, что то, что ты здесь имеешь в виду, это не то, что задача поиска точки по диаграмме не решена, а то, что ты написал ниже.

АТ>В частности, осмелюсь заметить, что если традиционная диаграмма Вороного говорит вам, что ближайшей вершиной является вершина Х водоема В, это совсем не означает, что Х является искомой ближайшей точкой границы. Более того, это даже совсем не означает, что искомая ближайшая точка принадлежит именно водоему В.

Ну здесь, как раз все понятно. Например, может быть так, что я в точке (1,0), один водоем А имеет ближайшие точки (0,-1) и (0,1), а другой Б -- (1.1,0). Тогда, точка (1.1,0) является ближайшей точкой и принадлежит водоему Б, в то время как (!если провести прямое!) ребро между точками (0,-1) и (0,1) водоема А, то его его точка (0,0) окажется ближе. Однако это имеет к расстоянию до водоема А весьма относительное отношение. Это тот самый случай, когда точки плохо аппроксимируют водоем, причем настолько плохо, что расстояние между водоемами (в данном случае А и Б) имеет тот же порядок, что и расстояние между точками одного водоема (в данном случае А). Если же это не так, например, водоемы по размеру несколько сотен метров, точки через каждый метр, расстояние между ними также в несколько сотен метров, то подобная проблема может возникнуть только в пределах метра от какой-либо вершины, что означает "пара лишних шагов".

На самом деле мы вообще задачи до конца не знаем. Не знаем порядок расстояний, не знаем степень аппроксимации, не знаем, главное, цели подобного поиска. Может точки на берегу водоема выбраны не просто как аппроксимация, а с каким-то определенным смыслом, например, это точки назначения. Как вариант, на берегу каждого озера есть множество пляжей. Задача состоит в том, чтобы путешествующий мог в любой момент найти ближайший пляж на ближайшем озере.

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

АТ>>Однако решение с настоящей Евклидовой диаграммой Вороного — практически чересчур трудоемко, ибо в общем случае границы ячеек реберно-вершинной диаграммы Вороного будут отрезками парабол, а не прямых. Задача сильно упростится, если перейти к какой-другой метрике (манхеттен? L-inf?). Если же все таки нужен строго именно Евклид, то лучше пять раз подумать, прежде чем ввязываться в диаграммы Вороного. Может хватит обычного перебора с парой-тройкой эвристик?

V>Никто не предлагает реберно-вершинную. Зачем? Просто вершинную, т.к. водоемы оппроксимированы набором точек, причем, судя по изначальному посту, БОЛЬШИМ числом точек. А ребра здесь совсем ни к месту.

Ну я этого в постановке задачи не увидел. Что я вижу в постановке залдачи, так это то, что водоемы заданы полигонами (т.е. наброром вершин полигонов), а найти надо ближайшую точку границы полигона, которая в общем случае врешиной не является.

V>Более того, если точки расставлены достаточно близко (ну не знаю, не более 10-100 метров, в зависимости от задачи), то расстояние до точки будет хорошей аппроксимацией для расстояние до берега (не до отрезка, их соединяющего, а до реального берега),

Если будет — то будет, если не будет — то не будет.

V>если же они расставлены далеко, то, наверное, добавление отрезка даст прирост точности, но только такая точность отношения к реальному берегу имеет все меньше, чем больше расстояние между точками, зато усложняет задачу многократно.

Это уже вопрос предметной области. Есть рукотворные водоемы, для которых простая полигональная граница будет иметь очень хорошее отношение к реальному берегу.

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

Получится рельтат, который будет ненамного отличаться от банального перебора с парой-тройкой эвристик, безо всяких диаграмм Вороного.

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

V>Ну здесь, как раз все понятно. Например, может быть так, что я в точке (1,0), один водоем А имеет ближайшие точки (0,-1) и (0,1), а другой Б -- (1.1,0). Тогда, точка (1.1,0) является ближайшей точкой и принадлежит водоему Б, в то время как (!если провести прямое!) ребро между точками (0,-1) и (0,1) водоема А, то его его точка (0,0) окажется ближе.

Да, именно так.

V>Однако это имеет к расстоянию до водоема А весьма относительное отношение.

Нет, как раз таки наоборот. Именно это и есть "расстояние до водоема А" по определению. А вот подмена его на "расстояние до ближайшей вершины водоема А" есть аппроксимация. Насколько хорошей или плохой будет такая аппроксимация зависит от плотности расположения (возможно фиктивных) вершин на границах водоемов. Хотя сразу стоит заметить, что набивание фиктивных вершин в границу в этом случае — решение пораженческое.

V>Это тот самый случай, когда точки плохо аппроксимируют водоем,

Плохо или хорошо точки аппроксимируют водоем зависит от расположения точек и от формы водоема. Это вообще выходит за рамки данного обсуждения.

V>причем настолько плохо, что расстояние между водоемами (в данном случае А и Б) имеет тот же порядок, что и расстояние между точками одного водоема (в данном случае А). Если же это не так, например, водоемы по размеру несколько сотен метров, точки через каждый метр, расстояние между ними также в несколько сотен метров, то подобная проблема может возникнуть только в пределах метра от какой-либо вершины, что означает "пара лишних шагов".

Да, но для этого нужны "точки через каждый метр", что является ужасным решением для водоемов с длинными прямыми участками границ. Т.е. это фактически способ полностью убить красоту подхода с диаграммами Вороного.

V>На самом деле мы вообще задачи до конца не знаем.

Вот именно поэтому я расматриваю абстрактную задачу — набор полигонов, найти ближайшую точку границы ближайшего полигона.

Здравствуйте, Андрей Тарасевич, Вы писали:

V>>Однако это имеет к расстоянию до водоема А весьма относительное отношение.

АТ>Нет, как раз таки наоборот. Именно это и есть "расстояние до водоема А" по определению. А вот подмена его на "расстояние до ближайшей вершины водоема А" есть аппроксимация. Насколько хорошей или плохой будет такая аппроксимация зависит от плотности расположения (возможно фиктивных) вершин на границах водоемов. Хотя сразу стоит заметить, что набивание фиктивных вершин в границу в этом случае — решение пораженческое.

Не факт. Много ты видел даже искусственных водоемов с прямой границей в 1км. Такой водоем, если не в эстетических целях, строить гораздо накладнее, чем с гладким непрямым берегом. Даже если такие имеются, с такой протяженностью прямых берегов, то их единицы во всем мире, добавить к ним десяток точек при изначальном количестве в десятки тысяч точек -- дело пустяковое. Тем более, что нам требуется просчитать все это один раз, да и только. Если же берег кривой, а его аппроксимировали двумя столбами через километр, то о поведении берега между ними ты можешь только догадываться. Не вижу смысла усложнять задачу, а главное алгоритмически усложнять ее, чтобы выиграть в точности, где ее нет. Если аппроксимация водоема имеет точность 1 км, то почему тогда решение должно быть с точностью до сантиметра, к тому же к аппроксимированному берегу? Абсурд.

Хотя сама по себе задача в твоей постановке, т.е. когда расстояние между полигонами сравнимо с длиной ребер, достаточна интересна. Вороной здесь вряд ли поможет, а переход в другую метрику -- вообще вещь непонятная, идти-то путник будет в обычной метрике. Поиск по соседним ячейкам ничего не даст. Есть длинная река, она задана, как раз как у тебя, координатами начала и конца (ну с какой-то толщиной, т.е. как длинный прямоугольник). В середине реки по берегам есть несколько озер. Тогда ячейки Вороного в середине все принадлежат точкам на берегах озер, в то время как стороны реки проходят через них.

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

V>>>Однако это имеет к расстоянию до водоема А весьма относительное отношение.

АТ>>Нет, как раз таки наоборот. Именно это и есть "расстояние до водоема А" по определению. А вот подмена его на "расстояние до ближайшей вершины водоема А" есть аппроксимация. Насколько хорошей или плохой будет такая аппроксимация зависит от плотности расположения (возможно фиктивных) вершин на границах водоемов. Хотя сразу стоит заметить, что набивание фиктивных вершин в границу в этом случае — решение пораженческое.

V>Не факт. Много ты видел даже искусственных водоемов с прямой границей в 1км. Такой водоем, если не в эстетических целях, строить гораздо накладнее, чем с гладким непрямым берегом. Даже если такие имеются, с такой протяженностью прямых берегов, то их единицы во всем мире, добавить к ним десяток точек при изначальном количестве в десятки тысяч точек -- дело пустяковое. Тем более, что нам требуется просчитать все это один раз, да и только. Если же берег кривой, а его аппроксимировали двумя столбами через километр, то о поведении берега между ними ты можешь только догадываться. Не вижу смысла усложнять задачу, а главное алгоритмически усложнять ее, чтобы выиграть в точности, где ее нет. Если аппроксимация водоема имеет точность 1 км, то почему тогда решение должно быть с точностью до сантиметра, к тому же к аппроксимированному берегу? Абсурд.

Ну, во первых, все эти рассуждения основаны на предположении об огрублении аппроксимации именно путем выбора какого-то глобального размера шага (1 км вместо 1 м). На самом деле аппроксимация может быть огрублена множеством других способов, не говоря уже о том, что фиксированности шага оцифровки совсем не требуется. Может, например, оказаться, что какие-то участки границы намеренно представлены точнее, а какие-то — намеренно огрублены. Какой-то участок границы может быть решено аппроксимировать прямой намного длиннее 1 км. Я не вижу вы этом ничего необычного в случае разнообразных искусственных каналов и т.п. Как и не вижу проблемы с аппроксимацией круглого озера, скажем, восьмиугольником.

V>Хотя сама по себе задача в твоей постановке, т.е. когда расстояние между полигонами сравнимо с длиной ребер, достаточна интересна. Вороной здесь вряд ли поможет, а переход в другую метрику -- вообще вещь непонятная, идти-то путник будет в обычной метрике. Поиск по соседним ячейкам ничего не даст. Есть длинная река, она задана, как раз как у тебя, координатами начала и конца (ну с какой-то толщиной, т.е. как длинный прямоугольник). В середине реки по берегам есть несколько озер. Тогда ячейки Вороного в середине все принадлежат точкам на берегах озер, в то время как стороны реки проходят через них.

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

Что же касается использования других метрик — они успешно используются именно для этой цели (диаграммы Вороного) в задачах микроэлектронного САПР, несмотря на то, что там тоже хватает евклидовых расстояний.

Здравствуйте, Андрей Тарасевич, Вы писали:

АТ>Ну, во первых, все эти рассуждения основаны на предположении об огрублении аппроксимации именно путем выбора какого-то глобального размера шага (1 км вместо 1 м). На самом деле аппроксимация может быть огрублена множеством других способов, не говоря уже о том, что фиксированности шага оцифровки совсем не требуется. Может, например, оказаться, что какие-то участки границы намеренно представлены точнее, а какие-то — намеренно огрублены. Какой-то участок границы может быть решено аппроксимировать прямой намного длиннее 1 км. Я не вижу вы этом ничего необычного в случае разнообразных искусственных каналов и т.п. Как и не вижу проблемы с аппроксимацией круглого озера, скажем, восьмиугольником.

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

V>>Хотя сама по себе задача в твоей постановке, т.е. когда расстояние между полигонами сравнимо с длиной ребер, достаточна интересна. Вороной здесь вряд ли поможет, а переход в другую метрику -- вообще вещь непонятная, идти-то путник будет в обычной метрике. Поиск по соседним ячейкам ничего не даст. Есть длинная река, она задана, как раз как у тебя, координатами начала и конца (ну с какой-то толщиной, т.е. как длинный прямоугольник). В середине реки по берегам есть несколько озер. Тогда ячейки Вороного в середине все принадлежат точкам на берегах озер, в то время как стороны реки проходят через них.

АТ>Реберно-вершинный Вороной тут, разумеется, поможет. Теоретически. Но проблема эффективного представления результата и определения принадлежности точки ячейке Вороного, разумеется, сохраняется (и усложняется).

Этот да, только вот описать его -- задача не хилая, не говоря уж о том, сколько это потребует той же памяти, да и поиск ячейки теперь становится тоже более трудоемким.

АТ>Что же касается использования других метрик — они успешно используются именно для этой цели (диаграммы Вороного) в задачах микроэлектронного САПР, несмотря на то, что там тоже хватает евклидовых расстояний.

Здесь я имел в виду, что есть две ситуации, когда подмена метрик допустима. Первая, это когда как таковой метрики не существует, это скорее воображение создателя, и он волен выбрать то, что ему больше нравится. Пример: поиск ближайшего цвета в палитре. Выбирай любую метрику, лишь бы глаз радовало. Вторая, это когда какая-то объективная метрика существует, но подмена ее на другую приводит в большинстве случаев к схожим результатам (допустимым с точки зрения требований), при этом ее использование существенно упрощает жизнь. Пример: использование МНК в статистике, или использование законов классической механики в реальной жизни. В нашем случае метрика задана самой постановкой вопроса, а потому единственное, что можно предложить, это что-то, относящееся ко второй ситуации, т.е. какую-то метрику, которая "слегка выпрямит" кривые стороны ячеек Вороного в случае многоугольников, например, превратит ячейки в многоугольники с прямыми или дуговыми сторонами, но при этом не сильно их исказит.

А вообще, как тут сказали в соседнем топике, автора на сцену!