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

@galileopro · Регистрация: 28.04.2009

Студворк — интернет-сервис помощи студентам

Помогите разобраться с алгоритмом Леонова. Мне нужно понять его суть, но что-то не все понятно

Я не тупой, просто сложно. Желательно написать его на сях. И еще, нужно реализовать с оптимизацией (если она возможна) мне нужно им посчитать 2 многоугольника, каждый из которых по 120 000 точек. Компьютер достаточно мощный, оперативка - максимум, который позволяют 32 бита, т. е. 4 гига.

@galileopro · 13.12.2009, 17:14 **[ТС]**

Вот информация по нему. 46.rar Процессор Core 2 Duo E7400. Да, таких многоугольников у меня 1000. Нужно попарно найти их пересечения ну хотя бы часов за 8.

@snake32 · 13.12.2009, 19:23

О, Как раз бьюсь с разностями двух полигонов....уже реализовал свой алгоритм. Интересно почитать альтернативу. Спасибо.

@snake32 · 14.12.2009, 12:24

Да...метод триангуляции - рулит!(по солвам Авторов и скрость(в среднем Q(n)) и простота реализации) Мой метод больше похож на метод О.Рурка, только работает не только с выпуклыми полигонами, правада, не всегда стабилен, т.е. когда вершина полигона Б находится на ребре полигона А может выбрать не правильное ребро для дальнейшего построения оверлеея. Другие методы не совсем понял.

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

Интересно, средствами OpenGL(через Tesselator) можно ли организовать триангуляцию полигона с ограничениями? Буду копать в этом направлении ибо лень самому делать, когда уже это почти сделано за тебя.

@snake32 · 16.12.2009, 10:32

galileopro, почему именно через алгоритмом Леонова? Средствами OpenGL не быстрее это будет?

@galileopro · 17.12.2009, 16:02 **[ТС]**

snake32, ну мне нужно было именно этим алгоритмом.

Новые блоги и статьи Все статьи Все блоги /
Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android 8Observer8 26.01.2026 Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .	Установка Android SDK, NDK, JDK, CMake и т.д. 8Observer8 25.01.2026 Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .	Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf 8Observer8 25.01.2026 Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .	Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly 8Observer8 24.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
моя боль iceja 24.01.2026 Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .	Модель сукцессии микоризы anaschu 24.01.2026 Решили писать научную статью с неким РОманом	http://iceja.net/ математические сервисы iceja 20.01.2026 Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .	http://iceja.net/ сервер решения полиномов iceja 18.01.2026 Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .

@galileopro Пробующий 185 / 98 / 10 Регистрация: 28.04.2009 Сообщений: 1,101

	Пересечение многоугольников 13.12.2009, 17:08. Показов 5383. Ответов 5 Метки нет (Все метки) Помогите разобраться с алгоритмом Леонова. Мне нужно понять его суть, но что-то не все понятно Я не тупой, просто сложно. Желательно написать его на сях. И еще, нужно реализовать с оптимизацией (если она возможна) мне нужно им посчитать 2 многоугольника, каждый из которых по 120 000 точек. Компьютер достаточно мощный, оперативка - максимум, который позволяют 32 бита, т. е. 4 гига. 0

@galileopro Пробующий 185 / 98 / 10 Регистрация: 28.04.2009 Сообщений: 1,101
	13.12.2009, 17:14 [ТС]
	Вот информация по нему. 46.rar Процессор Core 2 Duo E7400. Да, таких многоугольников у меня 1000. Нужно попарно найти их пересечения ну хотя бы часов за 8. 1

@snake32 3504 / 1687 / 236 Регистрация: 26.02.2009 Сообщений: 8,417 Записей в блоге: 6
	13.12.2009, 19:23
	О, Как раз бьюсь с разностями двух полигонов....уже реализовал свой алгоритм. Интересно почитать альтернативу. Спасибо. 1

@snake32 3504 / 1687 / 236 Регистрация: 26.02.2009 Сообщений: 8,417 Записей в блоге: 6
	14.12.2009, 12:24
	Да...метод триангуляции - рулит!(по солвам Авторов и скрость(в среднем Q(n)) и простота реализации) Мой метод больше похож на метод О.Рурка, только работает не только с выпуклыми полигонами, правада, не всегда стабилен, т.е. когда вершина полигона Б находится на ребре полигона А может выбрать не правильное ребро для дальнейшего построения оверлеея. Другие методы не совсем понял. Буду переделывать через триангуляцию. Интересно, средствами OpenGL(через Tesselator) можно ли организовать триангуляцию полигона с ограничениями? Буду копать в этом направлении ибо лень самому делать, когда уже это почти сделано за тебя. 1

@snake32 3504 / 1687 / 236 Регистрация: 26.02.2009 Сообщений: 8,417 Записей в блоге: 6
	16.12.2009, 10:32
	galileopro, почему именно через алгоритмом Леонова? Средствами OpenGL не быстрее это будет? 1

@galileopro Пробующий 185 / 98 / 10 Регистрация: 28.04.2009 Сообщений: 1,101
	17.12.2009, 16:02 [ТС]
	snake32, ну мне нужно было именно этим алгоритмом. 0