Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.50/6: Рейтинг темы: голосов - 6, средняя оценка - 4.50
yonder
10 / 10 / 9
Регистрация: 04.01.2013
Сообщений: 46
1

Построение графа видимости для многоугольника

21.04.2014, 12:35. Просмотров 1111. Ответов 5
Метки нет (Все метки)

Доброго времени суток! Необходимо решить задачу: найти кратчайший путь между двумя точками на плоскости, не пересекающий заданный многоугольник. Прочитал статью на хабре:
http://habrahabr.ru/post/199256/
В ней довольно хорошо написано, суть метода я понял, запрограммировал. Но у меня возникли проблемы с построением графа видимости. Там есть 2 способа: простой и сложный. Простой: это перебор всех пар вершин и ребер. Но у меня не получается нормально реализовать даже его. Автор говорит, что достаточно для каждой пары проверить, не пересекает ли соединяющий их отрезок стороны многоугольника. Но по-моему этого недостаточно. Например, тут:
Построение графа видимости для многоугольника

Отрезок пересекает 2 стороны, но точки считаются видимыми
Или, например, не получится отличить эти 2 случая(на первом отрезок внутри многоугольника, на втором: снаружи)
Построение графа видимости для многоугольника
Построение графа видимости для многоугольника

Или вот такой случай(1..4 вершины, А и В - концы маршрута)
Построение графа видимости для многоугольника

Из точки А вершину 1 видно, а 3 - нет, но алгоритм не позволяет это распознать
Думаю, это далеко не все недочеты. Помогите разобраться, пожалуйста. Возможно, я просто неправильно понял. Для нахождения пересечения отрезков использую алгоритм, где сначала находится пересечение ограничивающих прямоугольников, а потом косые произведения.
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.04.2014, 12:35
Ответы с готовыми решениями:

Построение многоугольника из треугольников
Дана последовательность точек, причём если каждую последующую точку соединить с предыдущей, а...

Построение графа из массива
Задача проста как пробка. Есть массив: array(array(1, 2, 3, ...), array(4, 5, ...), array(6, 7,...

Построение матрицы инцидентности для нагруженного ориентировочного графа
Подскажите пожалуйста как строится матрица инцидентности для нагруженного ориентировочного графа....

Нахождение фактора графа и остова графа для некоторого произвольного графа (5-6 вершин)
Форумчане прошу помощь в выполнение задания по деск. мат. Задание: Нахождение фактора графа и...

Построение многоугольника!
Всем привет! Помогите пожалуйста сделать следующее задание! Создайте приложение, позволяющее...

5
yonder
10 / 10 / 9
Регистрация: 04.01.2013
Сообщений: 46
21.04.2014, 13:23  [ТС] 2
Ага, я, кажется понял, что делать с последней ситуацией. Надо завести массив ребер и проверять пересечение только с ребрами, неинцидентными вершине. Но первые вопросы остаются в силе.

Добавлено через 19 минут
Я понял, что в первом случае ошибки нет, просто в маршрут добавится та вершина.
0
wingblack
281 / 255 / 45
Регистрация: 09.04.2013
Сообщений: 955
23.04.2014, 11:35 3
При работе с вещественными числами из-за особенностей их реализации в программировании очень тяжело встретить случай четкого равенства двух таких чисел, поэтому ситуацию когда отрезок коснется в точке другого отрезка можно считать невозможным.
Т.е. в первом случае отрезок AB либо пересекает многоугольник, тогда путь не будет прямой, либо НЕ пересекает многоугольник, тогда путь прямой.
В последнем случае то же самое.
В условии задачи сказано что путь не должен идти через многоугольник, поэтому мы не можем строить путь внутри него.
0
yonder
10 / 10 / 9
Регистрация: 04.01.2013
Сообщений: 46
23.04.2014, 20:01  [ТС] 4
Как по мне такие случаи бывают не так уж редко, хотя бы для точек с целыми координатами. Я знаю, что путь не может идти внутри многоугольника, потому хотел спросить, как определить пересекает ли отрезок между точками многоугольник или нет, поскольку, если проверять пересечения с ребрами многоугольника, то вторая и третья картинка дают одинаковый результат: "не пересекает".
0
Somebody
3104 / 1625 / 251
Регистрация: 03.12.2007
Сообщений: 4,223
Завершенные тесты: 3
23.04.2014, 21:24 5
Цитата Сообщение от yonder Посмотреть сообщение
найти кратчайший путь между двумя точками на плоскости, не пересекающий заданный многоугольник
Как я понял, многоугольник один по заданию? Тогда это из пушки по воробьям, по-моему (хотя не знаю, статью некогда читать пока). Или всё же цель - разобраться в алгоритме, а один многоугольник только для примера?
0
wingblack
281 / 255 / 45
Регистрация: 09.04.2013
Сообщений: 955
23.04.2014, 23:12 6
Цитата Сообщение от Somebody Посмотреть сообщение
Как я понял, многоугольник один по заданию? Тогда это из пушки по воробьям, по-моему (хотя не знаю, статью некогда читать пока). Или всё же цель - разобраться в алгоритме, а один многоугольник только для примера?
Для примера возьмем невыпуклый многоугольник с 1000 ребрами...
Цитата Сообщение от yonder Посмотреть сообщение
Как по мне такие случаи бывают не так уж редко, хотя бы для точек с целыми координатами
Если вычисления целочисленные, о все однозначно, если же вещественные, то число 4 на самом деле может являться числом 4.000...001 или 3.9999...974
Цитата Сообщение от yonder Посмотреть сообщение
как определить пересекает ли отрезок между точками многоугольник или нет
Например, по ссылке на хабрахабр обратить внимание на трапецеидальную карту. Если пересечение нашего отрезка с вертикальной/горизонтальной линией есть четное пересечение данной линии со всеми отрезками, то отрезок находится внутри многоугольника, если пересечение с отрезком будет нечетным - то вне многоугольника.
0
23.04.2014, 23:12
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.04.2014, 23:12

Построение многоугольника
Здравствуйте, как построить выпуклый многоугольник по беспорядочно заданным вершинам?

Построение многоугольника
Здравствуйте, как построить выпуклый многоугольник по беспорядочно заданным вершинам?

Построение многоугольника
Пожалуйста,помогите! Не знаю уже где искать... Нужна програмка,строящая многоугольник по заданным...


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

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

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