Викиконспекты - Вклад участника [ru]

Упрощение полигональной цепи

2012-02-27T11:09:15Z

178.178.29.90: /* Пример */

Упрощение полигональной цепи - процесс, позволяющий уменьшить число точек кривой, аппроксимированной серией точек.
==Задача==
Пусть у нас есть некоторая аппроксимированная кривая, все точки которой нам не нужны, а большинство из них лишь занимает место. Такое встречается при обработки векторной графики и построении карт. Расмотрим пример для построения карт. Пусть у нас есть путь из Москвы в Санкт-Петербург, заданный точками через каждый километр пути. В маштабах всей России такая точность явно ни к чему, стоит оставить лишь точки, отражающие ключевые участки пути. В этом случае нам и пригодится упрощение, одним из вариантов реализации которой является алгоритм Дугласа-Пекера.
==Алгоритм Дугласа-Пекера==
Суть алгоритма Дугласа-Пекера(Douglas–Peucker) состоит в том, чтобы по данной ломаной, аппроксимирующей кривую, построить ломаную с меньшим числом точек. Алгоритм определяет расхождение, которое вычисляется по максимальному расстоянию между исходной и упрощённой кривыми. Упрощенная кривая состоит из подмножества точек, которые определяются из исходной кривой.
===Описание===
Начальная кривая представляет собой упорядоченный набор точек.

Алгоритм рекурсивно делит линию. Входом алгоритма служат координаты всех точек между первой и последней. Первая и последняя точка сохраняются неизменными. После чего алгоритм находит точку, наиболее удалённую от отрезка, состоящего из первой и последней. Если точка находится на расстоянии, меньше чем епсилон, то все точки, которые ещё не были отмечены к сохранению, могут быть выброшены из набора и получившаяся прямая сглаживает кривую с точностью не ниже епсилон.

Если же расстояние больше епсилон, то алгоритм рекурсивно вызывает себя с на наборе от начальной до данной и от данной до конечной точках (что означает, что данная точка будет отмечена к сохранению).

По окончанию всех рекурсивных вызовов выходная ломаная строится только из тех точек, что были отмечены к сохранению.
===Псевдокод===
<tex>Douglas–Peucker(first, last, eps)</tex>
:<code>Для всех точек между</code> <tex>first</tex> <code>и</code> <tex>last</tex>
::<code>Если точка удалена дальше чем предыдущие запомнить ее в</code> <tex>max</tex>
:<code>Если расстояние от</code> <tex>max</tex> <code>до отрезка</code> <tex>first-last</tex> <code>меньше</code> <tex>eps</tex>
::<code>Вернуться</code>
:<code>Иначе</code>
::<code>Добавить точку</code> <tex>max</tex> <code>в ответ</code>
::<tex>DouglasPeucker(first, max, eps)</tex>
::<tex>DouglasPeucked(max, last, eps)</tex>

===Пример===
Рассмотрим пример для точек, заданных на рисунке, где сплошная линия отражает исходную линию и епсилон равному <tex>\sqrt 2</tex>
{| class="wikitable"
! Шаг || Действие
|-
| <tex>1</tex> || Найдем наиболее удаленную точку от отрезка <tex>1-5</tex>, это точка <tex>3</tex>
|-
| <tex>2</tex> || Расстояние до точки <tex>3</tex> больше <tex>\sqrt 2</tex>, добавляем ее в ответ
|-
| <tex>3</tex> || Запустим алгоритм для точек <tex>1</tex> и <tex>3</tex>
|-
| <tex>4</tex> || Найдем наиболее удаленную точку от отрезка <tex>1-3</tex>, это точка <tex>2</tex>
|-
| <tex>5</tex> || Расстояние до точки <tex>2</tex> меньше <tex>\sqrt 2</tex>, возвращаемся
|-
| <tex>6</tex> || Запустим алгоритм для точек <tex>3</tex> и <tex>5</tex>
|-
| <tex>7</tex> || Найдем наиболее удаленную точку от отрезка <tex>3-5</tex>, это точка <tex>4</tex>
|-
| <tex>8</tex> || Расстояние до точки <tex>4</tex> меньше <tex>\sqrt 2</tex>, возвращаемся
|-
| <tex>9</tex> || Алгоритм завершен
|}

Упрощение полигональной цепи

2012-02-27T10:51:48Z

178.178.29.90: /* Псевдокод */

Упрощение полигональной цепи

2012-02-27T10:43:40Z

178.178.29.90:

Упрощение полигональной цепи - процесс, позволяющий уменьшить число точек кривой, аппроксимированной серией точек.
==Задача==
Пусть у нас есть некоторая аппроксимированная кривая, все точки которой нам не нужны, а большинство из них лишь занимает место. Такое встречается при обработки векторной графики и построении карт. Расмотрим пример для построения карт. Пусть у нас есть путь из Москвы в Санкт-Петербург, заданный точками через каждый километр пути. В маштабах всей России такая точность явно ни к чему, стоит оставить лишь точки, отражающие ключевые участки пути. В этом случае нам и пригодится упрощение, одним из вариантов реализации которой является алгоритм Дугласа-Пекера.
==Алгоритм Дугласа-Пекера==
Суть алгоритма Дугласа-Пекера(Douglas–Peucker) состоит в том, чтобы по данной ломаной, аппроксимирующей кривую, построить ломаную с меньшим числом точек. Алгоритм определяет расхождение, которое вычисляется по максимальному расстоянию между исходной и упрощённой кривыми. Упрощенная кривая состоит из подмножества точек, которые определяются из исходной кривой.
===Описание===
Начальная кривая представляет собой упорядоченный набор точек.

Алгоритм рекурсивно делит линию. Входом алгоритма служат координаты всех точек между первой и последней. Первая и последняя точка сохраняются неизменными. После чего алгоритм находит точку, наиболее удалённую от отрезка, состоящего из первой и последней. Если точка находится на расстоянии, меньше чем епсилон, то все точки, которые ещё не были отмечены к сохранению, могут быть выброшены из набора и получившаяся прямая сглаживает кривую с точностью не ниже епсилон.

Если же расстояние больше епсилон, то алгоритм рекурсивно вызывает себя с на наборе от начальной до данной и от данной до конечной точках (что означает, что данная точка будет отмечена к сохранению).

По окончанию всех рекурсивных вызовов выходная ломаная строится только из тех точек, что были отмечены к сохранению.
===Псевдокод===
<tex>Douglas–Peucker(first, last, eps)</tex>
:<code>Для всех точек между</code> <tex>first</tex> <code>и</code> <tex>last</tex>
::<code>Если точка удалена дальше чем предыдущие запомнить ее в</code> <tex>max</tex>
:<code>Если расстояние от</code> <tex>max</tex> <code>до отрезка</code> <tex>first-last</tex> <code>меньше</code> <tex>eps</tex>
::<code>Вернуться</code>
:<code>Иначе</code>
::<code>Добавить точку</code> <tex>max</tex> <code>в ответ</code>
::<tex>Douglas-Peucker(first, max, eps)</tex>
::<tex>Douglas-Peucked(max, last, eps)</tex>

===Пример===

Упрощение полигональной цепи

2012-02-27T10:43:24Z

178.178.29.90:

Упрощение полигональной цепи - процесс, позволяющий уменьшить число точек кривой, аппроксимированной серией точек.
==Задача==
Пусть у нас есть некоторая аппроксимированная кривая, все точки которой нам не нужны, а большинство из них лишь занимает место. Такое встречается при обработки векторной графики и построении карт. Расмотрим пример для построения карт. Пусть у нас есть путь из Москвы в Санкт-Петербург, заданный точками через каждый километр пути. В маштабах всей России такая точность явно ни к чему, стоит оставить лишь точки, отражающие ключевые участки пути. В этом случае нам и пригодится упрощение, одним из вариантов реализации которой является алгоритм Дугласа-Пекера.
==Алгоритм Дугласа-Пекера==
Суть алгоритма Дугласа-Пекера(Douglas–Peucker) состоит в том, чтобы по данной ломаной, аппроксимирующей кривую, построить ломаную с меньшим числом точек. Алгоритм определяет расхождение, которое вычисляется по максимальному расстоянию между исходной и упрощённой кривыми. Упрощенная кривая состоит из подмножества точек, которые определяются из исходной кривой.
===Описание===
Начальная кривая представляет собой упорядоченный набор точек.

Алгоритм рекурсивно делит линию. Входом алгоритма служат координаты всех точек между первой и последней. Первая и последняя точка сохраняются неизменными. После чего алгоритм находит точку, наиболее удалённую от отрезка, состоящего из первой и последней. Если точка находится на расстоянии, меньше чем епсилон, то все точки, которые ещё не были отмечены к сохранению, могут быть выброшены из набора и получившаяся прямая сглаживает кривую с точностью не ниже епсилон.

Если же расстояние больше епсилон, то алгоритм рекурсивно вызывает себя с на наборе от начальной до данной и от данной до конечной точках (что означает, что данная точка будет отмечена к сохранению).

По окончанию всех рекурсивных вызовов выходная ломаная строится только из тех точек, что были отмечены к сохранению.
===Псевдокод===
<tex>Douglas–Peucker(first, last, eps)</tex>
:<code>Для всех точек между</code> <tex>first</tex> <code>и</code> <tex>last</tex>
::<code>Если точка удалена дальше чем предыдущие запомнить ее в</code> <tex>max</tex>
:<code>Если расстояние от</code> <tex>max</tex> <code>до отрезка</code> <tex>first-last</tex> <code>меньше</code> <tex>eps</tex>
::<code>Вернуться</code>
:<code>Иначе</code>
::<code>Добавить точку</code> <tex>max</tex> <code>в ответ</code>
::<tex>Douglas-Peucker(first, max, eps)</tex>
::<tex>Douglas-Peucked(max, last, eps)</tex>

==Пример==

Упрощение полигональной цепи

2012-02-27T10:39:31Z

178.178.29.90: Новая страница: «Упрощение полигональной цепи - процесс, позволяющий уменьшить число точек кривой, аппро...»

Упрощение полигональной цепи - процесс, позволяющий уменьшить число точек кривой, аппроксимированной серией точек.
==Задача==
Пусть у нас есть некоторая аппроксимированная кривая, все точки которой нам не нужны, а большинство из них лишь занимает место. Такое встречается при обработки векторной графики и построении карт. Расмотрим пример для построения карт. Пусть у нас путь из Москвы в Санкт-Петербург, заданный точками через каждый километр пути. В маштабах всей России такая точность явно ни к чему, стоит оставить лишь точки, отражающие ключевые участки пути. В этом случае нам и пригодится упрощение, одним из вариантов реализации которой является алгоритм Дугласа-Пекера.
==Алгоритм Дугласа-Пекера==
Суть алгоритма Дугласа-Пекера(Douglas–Peucker) состоит в том, чтобы по данной ломаной, аппроксимирующей кривую, построить ломаную с меньшим числом точек. Алгоритм определяет расхождение, которое вычисляется по максимальному расстоянию между исходной и упрощённой кривыми. Упрощенная кривая состоит из подмножества точек, которые определяются из исходной кривой.
===Описание===
Начальная кривая представляет собой упорядоченный набор точек.

Алгоритм рекурсивно делит линию. Входом алгоритма служат координаты всех точек между первой и последней. Первая и последняя точка сохраняются неизменными. После чего алгоритм находит точку, наиболее удалённую от отрезка, состоящего из первой и последней. Если точка находится на расстоянии, меньше чем епсилон, то все точки, которые ещё не были отмечены к сохранению, могут быть выброшены из набора и получившаяся прямая сглаживает кривую с точностью не ниже епсилон.

Если же расстояние больше епсилон, то алгоритм рекурсивно вызывает себя с на наборе от начальной до данной и от данной до конечной точках (что означает, что данная точка будет отмечена к сохранению).

По окончанию всех рекурсивных вызовов выходная ломаная строится только из тех точек, что были отмечены к сохранению.
===Псевдокод===
<tex>Douglas–Peucker(first, last, eps)</tex>
:<code>Для всех точек между</code> <tex>first</tex> <code>и</code> <tex>last</tex>
::<code>Если точка удалена дальше чем предыдущие запомнить ее в</code> <tex>max</tex>
:<code>Если расстояние от</code> <tex>max</tex> <code>до отрезка</code> <tex>first-last</tex> <code>меньше</code> <tex>eps</tex>
::<code>Вернуться</code>
:<code>Иначе</code>
::<code>Добавить точку</code> <tex>max</tex> <code>в ответ</code>
::<tex>Douglas-Peucker(first, max, eps)</tex>
::<tex>Douglas-Peucked(max, last, eps)</tex>