Нужно научиться строить ломаную линию — "график функции" (один x -> один y) с как можно более длинными сегментами в условиях заданного коридора пролегания и ограничений на углы переломов.
По-любому же человечеством что-то изобретено на эту тему. Подскажите, что почитать.
Здравствуйте, ylem, Вы писали:
Y>Нужно научиться строить ломаную линию — "график функции" (один x -> один y) с как можно более длинными сегментами в условиях заданного коридора пролегания и ограничений на углы переломов. Y>По-любому же человечеством что-то изобретено на эту тему. Подскажите, что почитать.
Хотя если есть проверенные развития этого алгоритма на тему вписать ломаную в "облако точек" (но так, что б вершины не обязательно лежали в исходных точках) -- тоже интересно.
Здравствуйте, ylem, Вы писали:
Y>"Это" я в курсе. Не оно совсем.
Y>Хотя если есть проверенные развития этого алгоритма на тему вписать ломаную в "облако точек" (но так, что б вершины не обязательно лежали в исходных точках) -- тоже интересно.
Надо вычислить скелетон этого коридора (medial axis) и затем применить Дуглас-Пекер, возможно, модифицированный.
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
В виде "наклонных прямоугольников", "вертикальных ворот" и точек, через которые ломаная должна пройти обязательно.
Прямоугольники многодлинней, чем шире ("выше").
ТЗИ>>Как задается коридор? Y>В виде "наклонных прямоугольников", "вертикальных ворот" и точек, через которые ломаная должна пройти обязательно. Y>Прямоугольники многодлинней, чем шире ("выше").
Ну тогда тривиально. Берем резинку и тянем ее вдоль коридора, зацепляя за точки, через которые ломаная должна пройти обязательно. Задача решена.
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
MS>Ну тогда тривиально. Берем резинку и тянем ее вдоль коридора, зацепляя за точки, через которые ломаная должна пройти обязательно. Задача решена.
Хм... Где-то должен быть подвох
Звучит более чем логично, и интуитивно это, видимо, будет очень хорошее, а то и лучшее решение.
А может есть готовое более менее формальное доказательство того, что это будет хорошим/лучшим решением?
