Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 21.05.2010, 18:44
Новичок

Отправить личное сообщение для Kosmosnsk Посмотреть профиль Найти все сообщения от Kosmosnsk
 
Регистрация: 21.05.2010
Сообщений: 2

Выпуклые многоугольники
Два выпуклых многоугольника заданы на плоскости перечислением координат вершин в порядке обхода границы. Проверить лежит ли один из них строго внутри другого и определить площади многоугольников.

Каким способом можно решить первый вопрос (лежит ли один из них строго внутри другого)? буду признателен если кто нибудь объяснит как это сделать на Си
  #2  
Старый 21.05.2010, 19:02
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

>лежит ли один из них строго внутри другого
Проверить, что все вершины лежат по одну сторону от отрезков-сторон второго. Это делается через знак векторного произведения
  #3  
Старый 21.05.2010, 20:06
Новичок

Отправить личное сообщение для Kosmosnsk Посмотреть профиль Найти все сообщения от Kosmosnsk
 
Регистрация: 21.05.2010
Сообщений: 2

Сообщение от MBo Посмотреть сообщение
Это делается через знак векторного произведения
а можно поподробнее?
  #4  
Старый 21.05.2010, 21:51
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

http://algolist.ru/maths/geom/datastruct.php
http://algolist.ru/maths/geom/polygon/
  #5  
Старый 22.05.2010, 10:36
Местный

Отправить личное сообщение для prografix Посмотреть профиль Найти все сообщения от prografix
 
Регистрация: 03.11.2006
Адрес: Москва
Сообщений: 167

Сообщение от MBo
Это делается через знак векторного произведения
Строго говоря в плоском случае это произведение не векторное, а тоже скалярное. Чтобы отличить его от обычного скалярного произведения употребляют термины внутреннее ( обычное ) и внешнее. Но часто нзывают его векторным по аналогии с трёхмерным случаем, где оно действительно векторное.
  #6  
Старый 22.05.2010, 17:49
Alexey Gusakov

 
Сообщений: n/a

Можно и побыстрее. Проверять влоб через векторные произведения долго - это O(mn), где m, n - размеры многоугольников.
Можно с помощью бинпоиска проверять лежит ли точка внутри выпуклого многоугольника за логарифм, поэтому задача решается за O(m log n). С помощью бинарного поиска надо находить наибольшее k, для которого точка лежит левее, вектора 1,k.
  #7  
Старый 22.05.2010, 19:17
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Вообще эта задача решается за линейное время O(m+n)
(например, алгоритм O'Rourke для пересечений).
Собственно, выбор метода зависит от размерности задачи, и от способности автора топика реализовать его.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
деление многоугольника на выпуклые многоугольники httpd Вычислительная геометрия 14 16.12.2008 23:18
опять многоугольники Green Вычислительная геометрия 0 04.03.2008 21:30
Многоугольники Nymph666 Вычислительная геометрия 4 14.01.2008 11:03