Форум программистов, компьютерный форум, киберфорум
Наши страницы

Алгоритмы

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 26, средняя оценка - 4.92
galileopro
Пробующий
184 / 97 / 1
Регистрация: 28.04.2009
Сообщений: 1,040
#1

Пересечение многоугольников - Алгоритмы

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

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

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

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

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

Пересечение отрезка и окружности - Алгоритмы
На плоскости есть отрезок с координатами, и окружность с радиусом и координатами центра. Необходимо вычислить, пересекается ли окружность...

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

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

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

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

Интересно, средствами OpenGL(через Tesselator) можно ли организовать триангуляцию полигона с ограничениями? Буду копать в этом направлении ибо лень самому делать, когда уже это почти сделано за тебя.
1
snake32
1510 / 1074 / 154
Регистрация: 26.02.2009
Сообщений: 3,979
Записей в блоге: 5
16.12.2009, 10:32 #5
galileopro, почему именно через алгоритмом Леонова? Средствами OpenGL не быстрее это будет?
1
galileopro
Пробующий
184 / 97 / 1
Регистрация: 28.04.2009
Сообщений: 1,040
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
Привет! Вот еще темы с ответами:

Пересечение луча с ПЕРЕСЕКАЮЩИМИСЯ сферами - Алгоритмы
Здравствуйте Конечно пересечение луча со сферой (одной) можно нагуглить за пару минут, а можно и самому вывести. НО что делать если...

узнать, есть ли пересечение кубов - Алгоритмы
Всем доброго вечера! Нужен алгоритм для определения, есть ли у двух кубов пересечение (любое, даже касание). Кубы разных размеров,...

Пересечение отрезка и множества отрезков - Алгоритмы
Задача: Есть множество отрезков. (около 10 000 отрезков) Найти ближайший (от точки начала луча) отрезок из этого множества, который...

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


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

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

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