Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 20.01.2013, 15:59   #1
_PROGRAMM_
Участник клуба
 
Аватар для _PROGRAMM_
 
Регистрация: 30.07.2009
Сообщений: 1,601
По умолчанию Пересечение линии и полигона.

Добрый день. Нашел наиболее понятный простому смертному алгоритм для определения пересечения линии и полигона в пространстве.
Цитата:
1) Выяснив, что линия пересекается с плоскостью, нужно получить точку пересечения. Для этого
нужно использовать формулу Dot product. Коротко, чтобы найти точку пересечения, нужно найти кратчайшую
дистанцию от линии до плоскости, потом двигатся от любой точки линии вдоль вектора линии.

2) Найдя точку пересечения, нужно проверить, находится ли эта точка внутри полигона. Одно то, что
линия пересекает плоскость, ещё не значит, что она пересекает полигон на этой плоскости.
Плоскость бесконечна, а полигон может быть на большом расстоянии от линии. Чтобы проверить это,
создаем векторы от точки пересечения до каждой вершины полигона. Сделав это, складываем
углы между этими векторами. Мы создаем 2 вектора за раз, что дает нам треугольник, и считаем
только внутренние углы. После создания векторов ко всем углам складываем их углы и смотрим,
дают ли они в сумме 360. Если да - то точка находится внутри полигона.
http://masandilov.ru/opengl/line-poly-collision
Возник один вопрос, пока я еще не начал реализацию. Во время расчетов значения углов скорее всего будут округлятся при cos acos, sqrt(Стандарт IEEE 754). Возникает вероятность того, что в итоге может не получится ровно 360(cos acos, корень), а проверки типа 359<x<361 могут повлечь за собой ошибки(баги). Как поступать в ситуациях такого рода?

В мире нет вечных двигателей, зато есть вечные тормоза...

Блог
_PROGRAMM_ вне форума Ответить с цитированием
Старый 20.01.2013, 16:42   #2
_PROGRAMM_
Участник клуба
 
Аватар для _PROGRAMM_
 
Регистрация: 30.07.2009
Сообщений: 1,601
По умолчанию

Решение.
Первое и очевидное это то, что угол не получится больше 360, поэтому можно проверять так x >=360
Второе. Точно учитывать погрешность не получится т.к. это IEEE 754. Можно умножить 360(2pi) на коэффициент, например 0.9999. Спасает от маленьких неточностей.
ИТОГО: условие нужно делать так. if (angle >= 2*pi*0.9999).

В мире нет вечных двигателей, зато есть вечные тормоза...

Блог
_PROGRAMM_ вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц



Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
метод contains для полигона LBlonde Общие вопросы по Java, Java SE, Kotlin 0 08.03.2012 15:52
проверить линии на пересечение HoBu4eK Общие вопросы Delphi 2 26.01.2012 18:18
Копирование полигона Николая Ленин Общие вопросы Delphi 5 04.06.2011 22:07
Поворот полигона Николая Ленин Общие вопросы Delphi 9 02.06.2011 23:05
площадь полигона boomeer Помощь студентам 5 17.10.2010 14:17