Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[3.17.186.140] |
|
Сообщ.
#1
,
|
|
|
Дан невыпуклый многоугольник и множество невыпуклых многоугольников внутри него.
Надо найти минимальное расстояние между внешним и внутренними многоугольниками за время O(n*log(n)), где n - общее количество вершин. В книге "Вычислительная геометрия" есть описание алгоритма для похожей задачи. Там дано N точек и нужно найти среди них пару с минимальным расстоянием. Там же говорится, что этот алгоритм можно обобщить на случай, когда даны 2 множества точек, и нужно найти расстояние между ними. Я планирую обобщить этот алгоритм для многоугольников, но, во-первых, не знаю ещё получится ли, и, во-вторых, возможно, для многоугольников есть свой алгоритм. |
Сообщ.
#2
,
|
|
|
Цитата prografix @ где n - общее количество вершин Вершинами не обойдёшься. Если имеется два отрезка на плоскости, то у отрезка минимальной длины, один конец которого принадлежит первому отрезку, а другой второму, только один из концов гарантированно совпадает с концом одного из исходных отрезков, а вовсе даже не оба... |
Сообщ.
#3
,
|
|
|
Я писал про зависимость скорости от вершин. А так да, минимальное расстояние может быть или между двумя вершинами, или между вершиной и отрезком.
|
Сообщ.
#4
,
|
|
|
Цитата prografix @ А так да, минимальное расстояние может быть или между двумя вершинами, или между вершиной и отрезком. А при чём тут "или"? первое - частный случай второго. Я собственно к тому, что для набора точек алгоритм быстрее O(N2) только за счёт того, что |AB|=|BA|. |
Сообщ.
#5
,
|
|
|
Цитата prografix @ минимальное расстояние может быть или между двумя вершинами, или между вершиной и отрезком. Это если исключить пересечения. Цитата Akina @ что для набора точек алгоритм быстрее O(N2) только за счёт того, что |AB|=|BA|. А если задействовать, к примеру, QuadTree? |
Сообщ.
#6
,
|
|
|
Цитата Mikle @ А если задействовать, к примеру, QuadTree? А какая разница? всё равно меньше O(NlogN) никак - N точек * logN поиск для каждой из них. |
Сообщ.
#7
,
|
|
|
Цитата Akina @ всё равно меньше O(NlogN) никак Так это же как раз и требуется в первопосте. |
Сообщ.
#8
,
|
|
|
Mikle
QuadTree не очень-то применим для расчёта расстояния между точкой и отрезком... потому как размер блока дискретизации должен быть не меньше размера отрезка, что в общем случае даёт QT из одного-единственного узла. |
Сообщ.
#9
,
|
|
|
Цитата Akina @ QuadTree не очень-то применим для расчёта расстояния между точкой и отрезком А ранее было, что я и цитировал в своём ответе: Цитата Akina @ для набора точек алгоритм быстрее O(N2) только за счёт того, что |AB|=|BA| Для отрезков - да, начинаются проблемы при относительно больших длинах отрезков. Но, даже когда отрезок сравним по длине с размером всего рассчитываемого пространства, он занимает в нём только ряд ячеек сетки вдоль самого отрезка. |
Сообщ.
#10
,
|
|
|
Ещё вариант.
Строим триангуляцию с ограничениями O(N*log(N)), число получающихся треугольников O(N). Далее пробегаемся по треугольникам, искомое расстояние это либо высота, либо ребро одного из треугольников. Треугольники, находящиеся снаружи внешнего, или внутри вложенных многоугольников, можно сразу пропускать. Можно без ограничений, но тогда придётся отдельно обрабатывать треугольники, пересекаемые сторонами многоугольников. Можно добавлять точки на рёбрах, нарушающих условие Делоне. |
Сообщ.
#11
,
|
|
|
Триангуляция произвольного набора точек неоднозначна.
|
Сообщ.
#12
,
|
|
|
Триангуляция Делоне однозначна, за исключением симметричных случаев.
|
Сообщ.
#13
,
|
|
|
Какая нахрен "триангуляция"? Не, ну возможно я как-то не в теме ... Но есть математический аппарат вычисления дистанции между точкой и прямой. Что мы имеем?
1) Любая прямая - задается координатами начала и конца прямой 2) Любые "началы" и "концы" могут выступать в роли точек 3) По условию - все линии прямые Что, тупо перебор абсолютных смещений и взаиморасположений не решает? |
Сообщ.
#14
,
|
|
|
Перебор - это O(n*n), а хочется быстрее.
|
Сообщ.
#15
,
|
|
|
Цитата Akina @ Ну и что? На результат эта неоднозначность не влияет.Триангуляция произвольного набора точек неоднозначна. Цитата prografix @ Здесь лучше получить триангуляию с ограничениями. Та же триангуляция Делоне, но не учитывается нарушение условия Делоне для пар треугольников, разделённых сторонами многоугольников.Триангуляция Делоне однозначна, за исключением симметричных случаев. Цитата JoeUser @ Ну высоту трегольника как раз так и удобнее вычислять. Триангуляция позволяет сократить число перебираемых пар точка-отрезок. Но есть математический аппарат вычисления дистанции между точкой и прямой. |
Сообщ.
#16
,
|
|
|
Цитата amk @ Ну и что? На результат эта неоднозначность не влияет. Ты почему-то, вероятно, рассчитываешь на то, что расчёт расстояний в итоговых треугольниках содержит в том числе и минимальное? Это не так. См. рис. Прикреплённая картинка
|
Сообщ.
#17
,
|
|
|
Цитата Akina @ Я вовсе не рассчитываю на это. Я это точно знаю.Ты почему-то, вероятно, рассчитываешь на то, что расчёт расстояний в итоговых треугольниках содержит в том числе и минимальное? И не вижу в этом рисунке ничего, что противоречило бы моим словам. Точнее там вообще ничего почти не нарисовано - только круг и набор каких-то линий. Какое отношение они имеют к упоминаемой мною триангуляции? Там же ни одного треугольника даже нет. |
Сообщ.
#18
,
|
|
|
Цитата amk @ там вообще ничего почти не нарисовано - только круг и набор каких-то линий. Круг - это тот самый описанный круг вокруг трёх узлов, в котором при триангуляции Делоне нет других узлов. Однако прекрасно видно, что минимальное расстояние от ребра до узла - это расстояние от синего ребра до любого из нижних узлов, которое в треугольник триангуляции Делоне никак не попадает. Ну что сам треугольник по трём чёрным вершинам пунктирчиком не нарисовал - ну ленив я, уж извиняюсь... Добавлено И да, в классическом варианте определения триангуляция Делоне не всегда однозначна. Простейший пример - квадрат. |
Сообщ.
#19
,
|
|
|
Есть триангуляция точек, а есть триангуляция многоугольников. Здесь речь идёт о многоугольниках и для них есть своя триангуляция Делоне ( оптимизация на максимум минимального угла ).
|
Сообщ.
#20
,
|
|
|
Цитата Akina @ Ленив, в данном случае, слишком мягко сказано. Там что вся триангуляция из одного единственного треугольника состоит? Кроме того, ты невнимателен. Речь идёт о триангуляции с ограничениями. А в ней указанного тобой треугольника (стороны которого пересекают один из заданных многоугольников) даже не существует - такие треугольники запрещены.Ну что сам треугольник по трём чёрным вершинам пунктирчиком не нарисовал - ну ленив я, уж извиняюсь... Цитата Akina @ В данном случае это несущественно. Подходящий треугольник всё равно найдётся.И да, в классическом варианте определения триангуляция Делоне не всегда однозначна. Простейший пример - квадрат. И иллюстрация по поводу триангуляции Прикреплённая картинка
Зелёным нарисованы рёбра триангуляции. Зелёные точки - добавленные узлы, чтобы триангуляция оставалась триангуляцией Делоне. Малиновый кандидаты на то, чтобы быть минимальными расстояниями |
Сообщ.
#21
,
|
|
|
Поразглядывал картинку и решил её немного дорисовать
Прикреплённая картинка
В среднем треугольнике, примыкающем к синему отрезку надо проверить правую сторону. Если бы правая зелёная точка не была добавлена, то этот отрезок мог бы быть искомым расстоянием. Кроме того, добавил серым проверяемые отрезки для верхних треугольников. |