Подскажите алгоритм для опредения является ли многоугольник самопересекающимся??

Ответы:

Можно использовать тот факт, что сумма углов несамопересекающегося n-угольника равна 180*(n-2)

Leron

Ту балубиг. Неверно. Это формула для выпуклого. А бывают многоугольники невыпуклые, но тем не мене несамопересекающиеся.

Leron

По сути, задача аналогична такой: есть n отрезков. Выяснить, есть ли среди них пересекающиеся. Тут не обойтись без перебора всех пар отрезков. А выяснить, пересекается ли пара отрезков - легко.

foGa

> Leron
Ну вообще-то не все, а пары ребер, не имеющие общих вершин. А определяется это просто при помощи векторов. сначала смотриш расположение вершин одного относительно другого. Если обе вершины по одну сторону (например, справа), то отрезки точно не пересекаются. Если же по разные, то проверяешь тоже самое, но уже относительно второго отрезка. Если и в этом случае точки по разные стороны, то отрезки пересекаются, иначе - нет.

BaluBig

Leron
Для невыпуклых эта формула так же работает, но там есть нюанс с углом.

13 лет назад

RPI.su - самая большая русскоязычная база вопросов и ответов. Наш проект был реализован как продолжение популярного сервиса otvety.google.ru, который был закрыт и удален 30 апреля 2015 года. Мы решили воскресить полезный сервис Ответы Гугл, чтобы любой человек смог публично узнать ответ на свой вопрос у интернет сообщества.

Все вопросы, добавленные на сайт ответов Google, мы скопировали и сохранили здесь. Имена старых пользователей также отображены в том виде, в котором они существовали ранее. Только нужно заново пройти регистрацию, чтобы иметь возможность задавать вопросы, или отвечать другим.

Чтобы связаться с нами по любому вопросу О САЙТЕ (реклама, сотрудничество, отзыв о сервисе), пишите на почту [email protected]. Только все общие вопросы размещайте на сайте, на них ответ по почте не предоставляется.