304
правки
Изменения
Нет описания правки
*<tex>|R_2| \ge \sqrt{|R_1|^2+|R_{12}|^2}</tex>, то ответ это <tex>|R_1|</tex>, так как угол между <tex>R_1</tex> и <tex>R_{12}</tex> при данном условии <tex> \ge 90^{\circ}</tex>
*Оба предыдущих условия ложны, то <tex>abs(| \overrightarrow{R_{12}} \times \overrightarrow{R_1}|/|\overrightarrow{R_{12}}|)</tex>, где <tex> \overrightarrow{R_{12}} = (x_2 -x_1, y_2 - y_1)</tex> и <tex> \overrightarrow{R_1} = (x_1 - x_0, y_1 - y_0)</tex>. Это следует из формул для площади параллелограмма через векторное произведение и через произведения основания на высоту
==Обзор ускорение работы алгоритма Дугласа-Пекера==
Как мы узнали ранее, в худшем случае алгоритм работает за <tex>O\left(n^2\right)</tex>. Теперь внесем дополнения, которые позволят получить нам <tex>O\left(n\log n\right)</tex> в худшем случае. Ускорение основывается на уменьшении времени поиска наиболее удаленной вершины. Мы можем это осуществить благодаря идее о том, что наиболее удаленная вершина лежит на выпуклой оболочке полигональной цепи.
В начале построим выпуклую оболочку алгоритмом Мелкмана (Melkman) за <tex>O\left(n\right)</tex>, затем используя бинарный поиск найдем искомую вершину за <tex>O\left(\log n\right)</tex>. Затем, если потребуется, мы разбиваем выпуклую оболочку в найденной точке и опять запускаем двоичный поиск и так далее.
Благодаря алгоритму Мелкмана разбиение мы сможем повести за <tex>O\left(\log n\right)</tex>, так как этот алгоритм в процессе построения строит не только искомую выпуклую оболочку, но и все промежуточные, нам остается только сохранить их.
В итоге мы получаем <tex>O\left(n\right)</tex> разбиений за <tex>O\left(\log n\right)</tex> и поиск за <tex>O\left(\log n\right)</tex>, что дает нам <tex>O\left(n\log n\right)</tex>.
===Замечания===
К сожалению, у данного метода есть несколько недостатков:
*исходная цепь должна быть без самопересечений для использования алгоритма Мелкмана
*ускорение подходит лишь для двумерного случая из-за способа построения выпуклой оболочки
*в некоторых случаях оригинальный алгоритм Дугласа-Пекера работает быстрее (например в случае, когда цепь приближено является окружностью)
==Ссылки==
