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

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

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

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

Пересечение эллипса и прямоугольника
Собств., всё сказано назв. темы. Нужен алгоритм, определяющий пересекаются или нет заданные эллипс и прямоугольник. Эллипс всё равно чем задан: объемлющим прямоугольником или каноническим уравнением, подойдут оба варианта.
  #2  
Старый 26.12.2009, 14:10
Местный

Отправить личное сообщение для prografix Посмотреть профиль Найти все сообщения от prografix
 
Регистрация: 03.11.2006
Адрес: Москва
Сообщений: 167

Пусть эллипс задан уравнением f ( x, y ) = 1. Тогда найдём точку которая лежит в прямоугольнике и минимизирует функцию f ( x, y ). Такую точку можно найти при помощи множителей Лагранжа. Если в этой точке целевая функция меньше 1 - это означает, что эллипс и прямоугольник пересекаются. Если больше, то нет. А если равна нулю, то они касаются.

Последний раз редактировалось prografix, 26.12.2009 в 14:45.
  #3  
Старый 26.12.2009, 23:48
Пользователь

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

Можно проще.
Для каждой стороны прямоугольника рассмотрите уравнение содержащей её прямой. Подставьте его в уравнение эллипса, избавляясь от одной из координат (например, y). Это вам даст квадратное уравнение относительно второй координаты (x). Решая его, находите точки пересечения рассматриваемой прямой и эллипса. Эти точки определяют отрезок прямой лежащий целиком внутри эллипса. Остатется только проверить пересекается ли этот отрезок с отрезком, представляющим сторону данного прямоугольника.
  #4  
Старый 27.12.2009, 12:10
Местный

Отправить личное сообщение для prografix Посмотреть профиль Найти все сообщения от prografix
 
Регистрация: 03.11.2006
Адрес: Москва
Сообщений: 167

В этом случае надо будет ещё проверить не лежит ли эллипс внутри прямоугольника.
Насчёт того, что это проще, сомневаюсь. В моём подходе все уравнения линейные, а здесь квадратные.
  #5  
Старый 28.12.2009, 16:44
Местный

Отправить личное сообщение для prografix Посмотреть профиль Найти все сообщения от prografix
 
Регистрация: 03.11.2006
Адрес: Москва
Сообщений: 167

Для определения пересекаются ли эллипс и прямоугольник предлагаю такой алгоритм:
1) Проверить лежит ли центр эллипса в прямоугольнике. Если да, то они пересекаются.
2) Иначе надо проверить на пересечение одну или две стороны прямоугольника. Это можно сделать способом, который предлагал maxal или искать минимум целевой функции на отрезке, как предлагал я.
 


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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
пересечение отрезков гость Реализация, исходники, языки 3 18.02.2011 13:17
Определение координаты прямоугольника Vitkov Вычислительная геометрия 1 23.01.2009 06:21
Нахождение охватывающего прямоугольника для точек в пространстве гость Математические алгоритмы 1 22.07.2008 04:06
Нахождение прямоугольника максимальной площади гость Задачи 13 15.05.2008 20:49
разбиение прямоугольника helium Вычислительная геометрия 5 03.03.2007 11:24