304
правки
Изменения
Нет описания правки
Алгоритм Реуманна-Виткама (Reumann-Witkam) определяет прямую через первые две точки цепи, последняя из последовательных точек начиная со второй, удаленных небольше чем на <tex>\varepsilon</tex>, соединяются прямой, а все промежуточные точки исключаются. Алгоритм продолжится последовательно для оставшихся точек до тех пор, пока не будет достигнута последняя.
На рисунке прямая, проходящая через точки отображена краснымкрасной линией, границы, в которые попадают вершины, допустимые для упрощения, отображены красным пунктиром. Точки красными пунктирными линиями, точки попавшие в итоговую цепь отображены черным.
<br clear="all"/>
Алгоритм Опхейма (Opheim) несколько схож с алгоритмом Реуманна-Виткама. В этом алгоритме мы рассматриваем все вершины в <tex>\varepsilon</tex> радиусе от первой, и строим луч из текущей и последней, попавшей в радиус. Если таких точек нет, то берется следующая за исходной. Последующие вершины упрощаются до тех пор, пока их расстояние до луча превосходит <tex>\varepsilon</tex> и радиальное расстояние до первой точке превосходит <tex>\varepsilon</tex>. Затем алгоритм продолжается для оставшихся точек до тех пор, пока не будет достигнута последняя.
На рисунке радиус, луч и максимальное радиальное расстояние отображены краснымкрасными линиями и дугами. Точки попавшие в итоговую цепь отображены черным.
<br clear="all"/>
==Алгоритм Ланга==
Алгоритм Ланга (Lang) определяет фиксированный размер поисковой области для упрощения. Две точки, что образуют поисковую область, составляют отрезок. Этот отрезок используется для расчета перпендикулярного расстояния до каждой промежуточной точки. Если рассчитанное расстояние больше заданного <tex>\varepsilon</tex>, область поиска будет уменьшен путем исключения ее последней точки. Этот процесс будет продолжаться, пока все рассчитанные расстояния не будут ниже заданного <tex>\varepsilon</tex>, или когда нет больше промежуточных точек. Все промежуточные точки удаляются, а новая область поиска определяется, начиная с последней точки в старой области.
Граница поисковой области помечена красной линией, допустимая область для упрощения - красной пунктирной линией, точки попавшие в итоговую цепь отображены черным.
==Ссылки==
