На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
Страницы: (2) [1] 2  все  ( Перейти к последнему сообщению )  
> Минимальное расстояние между многоугольниками
    Дан невыпуклый многоугольник и множество невыпуклых многоугольников внутри него.
    Надо найти минимальное расстояние между внешним и внутренними многоугольниками за время O(n*log(n)), где n - общее количество вершин.
    В книге "Вычислительная геометрия" есть описание алгоритма для похожей задачи.
    Там дано N точек и нужно найти среди них пару с минимальным расстоянием. Там же говорится, что этот алгоритм можно обобщить на случай, когда даны 2 множества точек, и нужно найти расстояние между ними.
    Я планирую обобщить этот алгоритм для многоугольников, но, во-первых, не знаю ещё получится ли, и, во-вторых, возможно, для многоугольников есть свой алгоритм.
      Цитата prografix @
      где n - общее количество вершин

      Вершинами не обойдёшься. Если имеется два отрезка на плоскости, то у отрезка минимальной длины, один конец которого принадлежит первому отрезку, а другой второму, только один из концов гарантированно совпадает с концом одного из исходных отрезков, а вовсе даже не оба...
        Я писал про зависимость скорости от вершин. А так да, минимальное расстояние может быть или между двумя вершинами, или между вершиной и отрезком.
          Цитата prografix @
          А так да, минимальное расстояние может быть или между двумя вершинами, или между вершиной и отрезком.

          А при чём тут "или"? первое - частный случай второго.
          Я собственно к тому, что для набора точек алгоритм быстрее O(N2) только за счёт того, что |AB|=|BA|.
            Цитата prografix @
            минимальное расстояние может быть или между двумя вершинами, или между вершиной и отрезком.

            Это если исключить пересечения.
            Цитата Akina @
            что для набора точек алгоритм быстрее O(N2) только за счёт того, что |AB|=|BA|.

            А если задействовать, к примеру, QuadTree?
              Цитата Mikle @
              А если задействовать, к примеру, QuadTree?

              А какая разница? всё равно меньше O(NlogN) никак - N точек * logN поиск для каждой из них.
                Цитата Akina @
                всё равно меньше O(NlogN) никак

                Так это же как раз и требуется в первопосте.
                  Mikle
                  QuadTree не очень-то применим для расчёта расстояния между точкой и отрезком... потому как размер блока дискретизации должен быть не меньше размера отрезка, что в общем случае даёт QT из одного-единственного узла.
                    Цитата Akina @
                    QuadTree не очень-то применим для расчёта расстояния между точкой и отрезком

                    А ранее было, что я и цитировал в своём ответе:
                    Цитата Akina @
                    для набора точек алгоритм быстрее O(N2) только за счёт того, что |AB|=|BA|

                    Для отрезков - да, начинаются проблемы при относительно больших длинах отрезков. Но, даже когда отрезок сравним по длине с размером всего рассчитываемого пространства, он занимает в нём только ряд ячеек сетки вдоль самого отрезка.
                      Ещё вариант.
                      Строим триангуляцию с ограничениями O(N*log(N)), число получающихся треугольников O(N).
                      Далее пробегаемся по треугольникам, искомое расстояние это либо высота, либо ребро одного из треугольников.
                      Треугольники, находящиеся снаружи внешнего, или внутри вложенных многоугольников, можно сразу пропускать.

                      Можно без ограничений, но тогда придётся отдельно обрабатывать треугольники, пересекаемые сторонами многоугольников.
                      Можно добавлять точки на рёбрах, нарушающих условие Делоне.
                        Триангуляция произвольного набора точек неоднозначна.
                          Триангуляция Делоне однозначна, за исключением симметричных случаев.
                            Какая нахрен "триангуляция"? :blink: Не, ну возможно я как-то не в теме ... Но есть математический аппарат вычисления дистанции между точкой и прямой. Что мы имеем?

                            1) Любая прямая - задается координатами начала и конца прямой
                            2) Любые "началы" и "концы" могут выступать в роли точек
                            3) По условию - все линии прямые

                            Что, тупо перебор абсолютных смещений и взаиморасположений не решает? :blink:
                              Перебор - это O(n*n), а хочется быстрее.
                                Цитата Akina @
                                Триангуляция произвольного набора точек неоднозначна.
                                Ну и что? На результат эта неоднозначность не влияет.
                                Цитата prografix @
                                Триангуляция Делоне однозначна, за исключением симметричных случаев.
                                Здесь лучше получить триангуляию с ограничениями. Та же триангуляция Делоне, но не учитывается нарушение условия Делоне для пар треугольников, разделённых сторонами многоугольников.
                                Цитата JoeUser @
                                Но есть математический аппарат вычисления дистанции между точкой и прямой.
                                Ну высоту трегольника как раз так и удобнее вычислять. Триангуляция позволяет сократить число перебираемых пар точка-отрезок.
                                0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                                0 пользователей:


                                Рейтинг@Mail.ru
                                [ Script execution time: 0,0337 ]   [ 16 queries used ]   [ Generated: 29.03.24, 07:50 GMT ]