Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.89/19: Рейтинг темы: голосов - 19, средняя оценка - 4.89
galileopro
Пробующий
184 / 97 / 8
Регистрация: 28.04.2009
Сообщений: 1,042
1

Пересечение многоугольников

13.12.2009, 17:08. Просмотров 3463. Ответов 5
Метки нет (Все метки)

Помогите разобраться с алгоритмом Леонова. Мне нужно понять его суть, но что-то не все понятно Я не тупой, просто сложно. Желательно написать его на сях. И еще, нужно реализовать с оптимизацией (если она возможна) мне нужно им посчитать 2 многоугольника, каждый из которых по 120 000 точек. Компьютер достаточно мощный, оперативка - максимум, который позволяют 32 бита, т. е. 4 гига.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.12.2009, 17:08
Ответы с готовыми решениями:

Совокупности пересекающихся многоугольников на плоскости
Здравствуйте. Встала передо мной такая задача. Есть плоскость. Есть на этой...

На сколько многоугольников разбивает плоскость ломаная?
Дана последовательность точек на координатной плоскости — узлов ломаной. Нужно...

Разбиение невыпуклого многоугольника на минимально возможное количество выпуклых многоугольников
Здравствуйте! Есть у меня контур какого-то многоугольника (он может быть и без...

Пересечение отрезка и окружности
На плоскости есть отрезок с координатами, и окружность с радиусом и...

Пересечение элементов графа
Делаю рядовую программу - построение, и далее анализ графа. Не могу решить -...

5
galileopro
Пробующий
184 / 97 / 8
Регистрация: 28.04.2009
Сообщений: 1,042
13.12.2009, 17:14  [ТС] 2
Вот информация по нему. 46.rar Процессор Core 2 Duo E7400. Да, таких многоугольников у меня 1000. Нужно попарно найти их пересечения ну хотя бы часов за 8.
1
snake32
1653 / 1105 / 194
Регистрация: 26.02.2009
Сообщений: 4,103
Записей в блоге: 5
13.12.2009, 19:23 3
О, Как раз бьюсь с разностями двух полигонов....уже реализовал свой алгоритм. Интересно почитать альтернативу. Спасибо.
1
snake32
1653 / 1105 / 194
Регистрация: 26.02.2009
Сообщений: 4,103
Записей в блоге: 5
14.12.2009, 12:24 4
Да...метод триангуляции - рулит!(по солвам Авторов и скрость(в среднем Q(n)) и простота реализации) Мой метод больше похож на метод О.Рурка, только работает не только с выпуклыми полигонами, правада, не всегда стабилен, т.е. когда вершина полигона Б находится на ребре полигона А может выбрать не правильное ребро для дальнейшего построения оверлеея. Другие методы не совсем понял.

Буду переделывать через триангуляцию.

Интересно, средствами OpenGL(через Tesselator) можно ли организовать триангуляцию полигона с ограничениями? Буду копать в этом направлении ибо лень самому делать, когда уже это почти сделано за тебя.
1
snake32
1653 / 1105 / 194
Регистрация: 26.02.2009
Сообщений: 4,103
Записей в блоге: 5
16.12.2009, 10:32 5
galileopro, почему именно через алгоритмом Леонова? Средствами OpenGL не быстрее это будет?
1
galileopro
Пробующий
184 / 97 / 8
Регистрация: 28.04.2009
Сообщений: 1,042
17.12.2009, 16:02  [ТС] 6
snake32, ну мне нужно было именно этим алгоритмом.
0
17.12.2009, 16:02
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.12.2009, 16:02

Пересечение луча с фигурами
Здравствуйте Есть N простых фигур/тел в пр-ве: кубов и сфер. Каждая может...

Блок-схема. Пересечение линий
Препод говорит персекание линий не приемлимо. Я не могу найти другой способ...

Функция на пересечение двух отрезков
кто может помочь с написанием функции на пересечение двух отрезков . Язык...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru