Изменения
→Реализация
Введём обозначения:
*<tex>R_1</tex> {{---}} отрезок <tex>[(x_0, y_0)</tex><tex>; (x_1, y_1)]</tex>*<tex>R_2</tex> {{---}} отрезок <tex>[(x_0, y_0)</tex><tex>; (x_2, y_2)]</tex>*<tex>R_{12}</tex> {{---}} отрезок <tex>[(x_1, y_1)</tex><tex>; (x_2, y_2)]</tex>
Если:
*<tex>|R_1| \ge \sqrt{|R_2|^2+|R_{12}|^2}</tex>, то ответ это <tex>|R_2|</tex>, так как угол между <tex>R_2</tex> и <tex>R_{12}</tex> при данном условии <tex> \ge 90^{\circ}</tex>
*<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>\operatorname{abs} (\frac{| \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>. Это следует из формул для площади параллелограмма через векторное произведение и через произведения основания на высоту
<br clear="all"/>
==Обзор ускорения работы алгоритма Дугласа-Пекера==
Как описано выше, в худшем случае алгоритм работает за <tex>O(n^2)</tex>. Можно внести дополнения, которые позволят получить <tex>O(n\log n)</tex> в худшем случае. Ускорение основывается на уменьшении времени поиска наиболее удаленной вершины. Это можно осуществить благодаря идее о том, что наиболее удаленная вершина лежит на выпуклой оболочке полигональной цепи.
