|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrey Romanov 2:5052/13.10 29 Jul 2001 02:43:06
To : Sandro (Vladimir Uryvaev)
Subject : Упрощение контура двумерного полигона
--------------------------------------------------------------------------------
28 Jul 01 20:47, Sandro (Vladimir Uryvaev) wrote to All:
A>> Есть двумерный полигон как последовательность вершин. Hаложили на
A>> битмап-карту (ячейка = находится в ней полигон или нет). После этого
A>> отследили контур заполненной области этой карты, и получили другой
SU> полигон,
A>> который повторяет форму исходного, но в котором гораздо больше
A>> вершин.
SU> Куча
A>> мелких отрезков перпендикулярных друг другу.
A>> Hадо его упростить, что бы он по форме и по количеству вершин (или
SU> отрезков)
A>> был максимально близок к исходному.
A>> Просьба поделиться мыслями, на эту тему.
SU> Пришла мысль о скашивании линий.
SU> x | x | x | x x | x | x | x # - угол
SU> #=======#---+-+- #==____-+---+---
SU> o | o H x | x ==> o | o---x___x
SU> ---+---#=======# ---+---+---+-==#
SU> o | o | o | o o | o | o | o
SU> Линия после преобразования так проходит?
SU> тода можно находить такие ломаные, при замене которых на прямую
SU> не потребовалось бы перекраски ни одной ячейки
SU> это надо?
SU> кстати, если ломаную 1-2-3 нельзя заменить на 1-3, это не значит, что
SU> нельзя ломаную 1-2-3-4 заменить на 1-4
SU> можно придумать что нибудь с перемещение узлов на +- 0.5 пиксела
Опять изобретаем велосипед :-(
Для человека с достyпом в интернет, это мягко говоря, некрасиво...
Всего то ведь надо спросить любой поисковик о Curve/Polygon
simplification/approximation.
Идyщий ниже текст, цитата из статьи Garland'а.
EUROGRAPHICS '99
Multiresolution Modeling: Survey & Future Opportunities
Michael Garland
Computer Science Department, Carnegie Mellon University
Pittsburgh, PA 15213, USA
garland@cs.cmu.edu
Perhaps the most widely used algorithm for curve simplification
is a simple refinement algorithm, commonly referred
to as the Douglas-Peucker algorithm. This algorithm begins
with with some minimal approximation, normally a single
line segment from the first to last vertex. This segment
is split at the point on the original curve which is furthest
from the approximation. Each of the two new subsegments
can be recursively split until the approximation meets some
termination criteria. This is evidently a rather natural algorithm
for curve approximation, since it was independently
invented by a number of people.
Andrey
--- GoldED 3.00.Beta1+
* Origin: (2:5052/13.10)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
