Алгоритмы, методы, исходники / Форум

Алгоритмы, методы, исходники / Форум (http://forum.algolist.ru/)
-   Математические алгоритмы (http://forum.algolist.ru/algorithm-maths/)
-   -   Выпуклые многоугольники (http://forum.algolist.ru/algorithm-maths/3832-vypuklye-mnogougolniki.html)

Kosmosnsk 21.05.2010 18:44

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

Каким способом можно решить первый вопрос (лежит ли один из них строго внутри другого)? буду признателен если кто нибудь объяснит как это сделать на Си:o

MBo 21.05.2010 19:02

>лежит ли один из них строго внутри другого
Проверить, что все вершины лежат по одну сторону от отрезков-сторон второго. Это делается через знак векторного произведения

Kosmosnsk 21.05.2010 20:06

Цитата:

Сообщение от MBo (Сообщение 12142)
Это делается через знак векторного произведения

а можно поподробнее?

MBo 21.05.2010 21:51

http://algolist.ru/maths/geom/datastruct.php
http://algolist.ru/maths/geom/polygon/

prografix 22.05.2010 10:36

Цитата:

Сообщение от MBo
Это делается через знак векторного произведения

Строго говоря в плоском случае это произведение не векторное, а тоже скалярное. Чтобы отличить его от обычного скалярного произведения употребляют термины внутреннее ( обычное ) и внешнее. Но часто нзывают его векторным по аналогии с трёхмерным случаем, где оно действительно векторное.

Alexey Gusakov 22.05.2010 17:49

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

MBo 22.05.2010 19:17

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


Часовой пояс GMT +4, время: 17:54.