Помогите с алгоритмом или исходником двумерного отсечения отрезка.
-
[mzd]
Помогите с алгоритмом или исходником двумерного отсечения отрезка.
Необходим алгоритм или пример кода двумерного отсечения отрезка невыпуклым многоугольником.
-
hasherfrog
Re: Помогите с алгоритмом или исходником двумерного отсечения отрезка.
Я когда-то занимался похожим вопросом: отрезание маленьких "петелек" на невыпуклых самопересекающихся полигонах. Сразу могу сказать, что абсолютно весь алгоритм пришлось писать с нуля - в сети ничего нету :[
Могу "идею" предложить. Пару классов подкинуть. Но разобраться с моим кодом будет очень-очень сложно, там всё для автокада R2000. Даже скомпилить будет невозможно, если нет нужных библиотек/хидеров (у меня уже ддавно их нет) %[
Могу "идею" предложить. Пару классов подкинуть. Но разобраться с моим кодом будет очень-очень сложно, там всё для автокада R2000. Даже скомпилить будет невозможно, если нет нужных библиотек/хидеров (у меня уже ддавно их нет) %[
-
[mzd]
Re: Помогите с алгоритмом или исходником двумерного отсечения отрезка.
В нете нашел такой алгоритм
Цитата:
Одновременное проведение операций проверки на выпуклость и разбиение простого невыпуклого многоугольника на выпуклые обеспечивается методом переноса и поворотов окна.
Алгоритм метода при обходе вершин многоугольника против часовой стрелки состоит в следующем:
1. Для каждой i-й вершины многоугольник сдвигается для переноса упомянутой вершины в начало координат.
2. Многоугольник поворачивается против часовой стрелки для совмещения (i+1)-й вершины с положительной полуосью X.
Вектор внутреннего перпендикуляра к ребру, образованному вершинами i-й и (i+1)-й, вычисляется поворотом ребра на -90° против часовой стрелки.
3. Анализируется знак Y-координаты (i+2)-й вершины.
Если Yi+2 і 0, то в (i+1)-й вершине выпуклость.
Если Yi+2 і 0, то в (i+1)-й вершине невыпуклость.
Если имеется невыпуклость, то многоугольник разрезается на два вдоль положительной полуоси X.
Для этого вычисляется пересечение положительной полуоси X с первой из сторон. Формируются два новых многоугольника: первый многоугольник - вершины с (i+1)-й до точки пересечения - вершины 2, 3, 4, 6, 7, [7\tilde], второй многоугольник - все остальные вершины - вершины [7\tilde], 8, 0, 1.
Так как вновь полученные многоугольники могут в свою очередь оказаться невыпуклыми, алгоритм применяется к ним, пока все многоугольники не станут выпуклыми.
Погмогите загнать его в эту программу, а то с поворотами я совсем запутался.
Цитата:
Одновременное проведение операций проверки на выпуклость и разбиение простого невыпуклого многоугольника на выпуклые обеспечивается методом переноса и поворотов окна.
Алгоритм метода при обходе вершин многоугольника против часовой стрелки состоит в следующем:
1. Для каждой i-й вершины многоугольник сдвигается для переноса упомянутой вершины в начало координат.
2. Многоугольник поворачивается против часовой стрелки для совмещения (i+1)-й вершины с положительной полуосью X.
Вектор внутреннего перпендикуляра к ребру, образованному вершинами i-й и (i+1)-й, вычисляется поворотом ребра на -90° против часовой стрелки.
3. Анализируется знак Y-координаты (i+2)-й вершины.
Если Yi+2 і 0, то в (i+1)-й вершине выпуклость.
Если Yi+2 і 0, то в (i+1)-й вершине невыпуклость.
Если имеется невыпуклость, то многоугольник разрезается на два вдоль положительной полуоси X.
Для этого вычисляется пересечение положительной полуоси X с первой из сторон. Формируются два новых многоугольника: первый многоугольник - вершины с (i+1)-й до точки пересечения - вершины 2, 3, 4, 6, 7, [7\tilde], второй многоугольник - все остальные вершины - вершины [7\tilde], 8, 0, 1.
Так как вновь полученные многоугольники могут в свою очередь оказаться невыпуклыми, алгоритм применяется к ним, пока все многоугольники не станут выпуклыми.
Погмогите загнать его в эту программу, а то с поворотами я совсем запутался.
- Вложения