|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergiy Kanilo 2:5020/400 17 Mar 2002 07:04:38
To : Dmitry Pacuk
Subject : Re: многоугольник порубить
--------------------------------------------------------------------------------
"Dmitry Pacuk" <Dmitry.Pacuk@p11.f5555.n5020.z2.fidonet.org> wrote in
message news:1016276605@p11.f5555.n5020.z2.ftn...
> >> Подcкажите, пожалуйcта, как pазбить пpоизвольyю (невыпуклую,
> >> неcвязную) облаcть, огpаниченную полилинией, на выпуклые
> >> многоугольники.
>
> SK> Проходишь по своей линии и обрезаешь выступающие уголки.
> SK> Каждый такой обрез создает треугольник и уменьшает полилинию
> SK> на один отрезок. Правда, для невыпуклых полилиний надо еще
> SK> проверять не пересекает ли линия отреза эту же полилинию.
> SK> Hу а так все.
>
> Много их плучитcя. Тогда как оъединять c cоcедними? Обходить вcех cоcедей
> и пpовеpять получившееcя на выпуклоcть?
Sorry, неправильно прочитал условие. Думал нужна
обычная триангуляция.
Можно в принципе использовать подобный подход -
обходить по границе, постоянно связывая первую и
последнюю точку условной линией до тех пор пока такой
многоугольник не станет невыпуклым. Тогда шаг назад
и обрезаем его. И соответственно меняем ломанную.
Для проверки на каждом шаге достаточно проверять
всего три угла: между предпоследним звеном и последним,
последним и замыкающим, и замыкающим и первым.
Если не удается построить таким образом даже
треугольник - начинаем со следующей по линии точки.
Если вернулись в исходную - то вся ломанная - выпуклая.
и с этой ломанной заканчиваем и переходим к следующей.
Этот метод конечно не ведет к разбивке с минимальным
количеством кусков, но их будет и не очень много.
Cheers,
Serge
--- ifmail v.2.15dev5
* Origin: Giganews.Com - Premium News Outsourcing (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Re: многоугольник порубить