|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Oleg Shmidt 2:5020/400 13 Jun 2001 17:54:32
To : Yura Schapov
Subject : Re: Алгоритм разделения горизонтальных линий полигоном ?
--------------------------------------------------------------------------------
Hello Yura,
[skip]
YS> Как я сам это представляю:
YS> Пусть полигон задан anticlockwize векторами. Т.е. слева от вектора
YS> полуплоскость принадлежит полигону (+), если он (вектор) смотрит вверх.
YS> (+^-) Определяем верхнюю и нижнюю границы по Y. В цикле 0..MaxY определяем
YS> точки пересечения горизонтальной линии Y, с линиями, образующими полигон
YS> (scan conversion), и смотрим знаки, например: (-+) (+-) (-+) (+-) Линии
YS> соединяют положительные полуплоскости: (-+)--(+-) (-+)--(+-) Вот, примерно,
YS> так. Единственная проблема - если полигон задан неправильно =(
Да, спасибо. Я примерно так и делал, но :) при более подробном рассмотрении
задачи,
что мне в конечном итоге нужно. Просто линии, оказались неприемлемой
абстракцией.
Так что вопрос мой снимается.
YS> Встречная просьба к all: посоветуйте где поискать алгоритм быстрой
YS> триангуляции таких полигонов... =)
Я собственно не специалист в этом. Я откуда-то скачивал zip с именем geompack в
нем
есть реализации алгоритмов триангуляции на фортране. Я не разбирался, но кажется
что
и для concave с отверстиями (по моему сначала делается Convex Decomposition).
Hиже адрес какой-то из его редми. Если этого там нет, напиши я это тебе отмылю.
See also ftp://menaik.cs.ualberta.ca/pub/geompack by Barry Joe for
various triangulation algorithms that, among other things, can produce
the Delaunay triangulation.
--
Отправлено через сервер Talk.Ru - http://www.talk.ru
--- ifmail v.2.15dev5
* Origin: Talk.Ru (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
