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

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

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

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

Вычисление пересечения
Приветсвую всех.

Цель темы: найти оптимальный алгоритм определения точного пересечение геометрических объектов в 2D, 3D, реализуемый средствами C++.

Условия задачи:
Точноть вычислений координат double(32 знака).
На рисунке приведён случай пересечения 3-х прямых.



Условные обозначения:
A - точка пересечения прямых 1 и 2;
B - точка пересечения прямых 1 и 3;
C - точка пересечения прямых 2 и 3;
Окружности - окрестности соответсвующих точек

Проблема:
Для данной задачи мы получаем:
при грубое упрощение - 1 точка пересечения 3-х прямых

Вопрос:
Каким способом, не увеличивая точности, можно найти пересечения этих прямых, сохраняя все точки пересечения?

P.S.Я рассмотрел простой случай. Прочитав несколько алгоритмов нахождения пересечения геом. объектов не нашел ни в одном решения данной проблемы. Проблемы возникают при пересечении объектов в пространстве: пересечение почти параллельных прямых(ничтожно малый угол, количество прямых в пространстве >2), окрестности нескольких точек пересекаются получая n-угольник(n - количество точек).

Может кто-нибудь находил в интернете статьи на данную тему? Буду рад любой информации.

Последний раз редактировалось vilza, 29.01.2009 в 05:28.
  #2  
Старый 29.01.2009, 05:41
гость

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

Не совсем понятно что именно вам нужно... Нужно определить, пересекаются ли n прямых в одной и той же точке d-мерного пространства?

Если возникают проблемы с точностью вычислений, то почему бы не отказаться от арифметики с плавающей точкой, и перейти исключительно на целочисленную арифметику (т.е. заменить double на рациональные дроби, возможно с использованием длинное арифметики аля gmp)?
  #3  
Старый 29.01.2009, 14:48
гость

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

Эта проблема общеизвестна и не решается универсально.
Она наз: Robust geometric computations
Прежде всего определите погрешность во входных данных и обеспечте вычсления в 10^3 более точные.
А вообще нужен целый ряд приемов для устойчивсти. Почитайте.
  #4  
Старый 29.01.2009, 18:57
Новичок

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

Спасибо, я не знал как называется эта проблема.

Переформулирую вопрос:
Мне и хотелось узнать кто и конкретно как, решал эту проблемы для своих случаев. Я ищу наиболее быстрый и общий случай решения.

На рисунке я привел пример пересечения 3-х прямых на максимальной точности вычислений для типа double. Я нашел 3 точки пересечения, но для компьютера они могут быть равносильны как 1-ой, так и 2-м точкам, что сразу меняет всю картину происходящего, соответсвенно возникает погрешность при использовании этих данных в дальнейшем.

Последний раз редактировалось vilza, 29.01.2009 в 18:59.
  #5  
Старый 29.01.2009, 19:29
гость tot, chto vtoroj

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

Вот Вы пишете: "Я нашел 3 точки пересечения". Уже отсюда начинаются вопросы: как были заданы прямые, как Вы считали пересечение, с какой точностью оно Вам необходимо, в какой задаче, т.е. на каком топологическом фоне... и т.д.
Статей на эту тему море, попытки систематического изложения тоже встречаются.
Все это по-английски и найти не трудно. Почти всех серьезных выч.геометров сносит в эту тему.
  #6  
Старый 30.01.2009, 04:02
Новичок

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

1) Я привел всего лишь пример, и хотел наиболее наглядно показать что я ищу.

2) Статьи нашел, читаю.

Для "гость tot, chto vtoroj" - Огромное спасибо за название проблемы на английском, очень помогло. И, если вы с этим материалом работали и вам не трудно, выделите на ваш взгляд статьи, наиболее удачные по количеству и качеству изложенного материала - может быть назовете авторов.
  #7  
Старый 30.01.2009, 13:41
гость tot, chto vtoroj

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

Видите ли, я практик, ответственного совета дать не могу, да и ссылки не храню, м.б. зря. Все подходящие идеи адаптировал под свои проблемы. Вряд ли я буду Вам полезен. Впрочем вот это, кажется, серьзный обзор :
http://portal.acm.org/citation.cfm?id=1344898
Но Вы его, скорее всего, уже нашли.
Успехов.
  #8  
Старый 30.01.2009, 16:58
Новичок

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

Спасибо. Да, действительно, уже нашел.
 


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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Определить точки пересечения эллипсов like-nix Математические алгоритмы 3 13.10.2008 18:15
Вычисление площади пересечения двух прямоугольников mark_tyler Вычислительная геометрия 1 31.08.2008 04:10
площадь пересечения многоугольников Artemon Вычислительная геометрия 1 20.03.2008 13:45
Вычисление выражений Andrew Математические алгоритмы 1 27.08.2007 00:45
проверка пересечения dex Вычислительная геометрия 1 27.02.2007 07:52