Имеется карта некоторой области, на которой отмечены водоёмы. Водоёмы заданы наборами координат точек своих береговых линий.
То есть имеется 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 метров, в зависимости от задачи), то расстояние до точки будет хорошей аппроксимацией для расстояние до берега (не до отрезка, их соединяющего, а до реального берега), если же они расставлены далеко, то, наверное, добавление отрезка даст прирост точности, но только такая точность отношения к реальному берегу имеет все меньше, чем больше расстояние между точками, зато усложняет задачу многократно. Уж лучше тогда на этом отрезке просто промежуточных точек понаставить, а то получается какая-то охота за ложной точностью.