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


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

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

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

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

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

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

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

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

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