2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.



Начать новую тему Ответить на тему
 
 эллипс. точка внутри или снаружи
Сообщение10.07.2007, 20:47 
Экс-модератор
Аватара пользователя


23/12/05
12062
Думаю, что это очень просто, но для меня - надо искать, а многие завсегдатаи, уверен, мне сходу скажут ответ.

Имеется эллипс с центром в $(x_0;y_0)$, оси ориентированы вдоль осей декартовых координат, полуоси эллипса соответственно равны $r_x$ и $r_y$. И имеется точка с координатами $(x;y)$. Как проще всего (в смысле алгоритма - это условие надо проверять для большого числа точек) определить находится ли данная точка внутри эллипса?

 Профиль  
                  
 
 
Сообщение10.07.2007, 21:11 
Супермодератор
Аватара пользователя


29/07/05
8248
Москва
Если не ошибаюсь, то уравнение эллипса можно записать в виде $(x-x_0)^2/r_x^2+(y-y_0)^2/r_y^2=1$. Подставляешь точку и готово.

 Профиль  
                  
 
 
Сообщение10.07.2007, 21:17 
Заблокирован
Аватара пользователя


07/08/06

3474
Ещё можно придумать такую вещь, если эллипс один и зафиксирован на плоскости. Если так, то большинство точек можно отбросить на предварительном проходе, если построить гистограмму - мысленно разделить этот эллипс на $n$ вертикальных сегментов и для каждого из сегментов заранее посчитать и поместить в массив 2 значения: $y_a$ и $y_b$. Все значения, меньшие по модулю $y_a$ (для заданной координаты $x$) автоматически принадлежат эллипсу, те, что больше по модулю $y_b$ - автоматически не принадлежат, а с остальными - разбираться поштучно...

 Профиль  
                  
 
 
Сообщение10.07.2007, 22:42 
Экс-модератор
Аватара пользователя


23/12/05
12062
PAV, спасибо, я отталкивался от канонической формы записи, но так, как вы написали, будет удобнее

AlexDem, эллипсов много натыкано

 Профиль  
                  
 
 
Сообщение11.07.2007, 12:01 
Заблокирован
Аватара пользователя


07/08/06

3474
Всё равно - если ускорение очень важно, предварительная кластеризация точек поможет. Например, можно разбить плоскость на клетки и для каждой из клеток заранее определить, каким эллипсам эта клетка (или её часть) принадлежит...

 Профиль  
                  
 
 
Сообщение11.07.2007, 12:07 
Супермодератор
Аватара пользователя


29/07/05
8248
Москва
AlexDem писал(а):
Всё равно - если ускорение очень важно, предварительная кластеризация точек поможет. Например, можно разбить плоскость на клетки и для каждой из клеток заранее определить, каким эллипсам эта клетка (или её часть) принадлежит...


Это не бесспорно. Для принятия решения по формуле нужно провести несколько арифметических операций. Не уверен, что метод кластеризации окажется быстрее. Нужно определить, в какую клетку попадает точка, это может потребовать определенного числа сравнений. Нужно также помнить, что при этом возникает много точек ветвления программы, а это замедляет работу. Чем меньше в процедуре условных операторов, тем она быстрее работает.

 Профиль  
                  
 
 
Сообщение11.07.2007, 12:09 
Заблокирован
Аватара пользователя


07/08/06

3474
Да, конечно, - тут нужно смотреть и на количество точек, и эллипсов, и плотность заполнения. Но - как вариант.

Клетка, в которую точка попадает, вычисляется по координатам без сравнений. Но сама процедура построения клеток может потребовать много времени - это зависит от условий задачи.

 Профиль  
                  
 
 
Сообщение11.07.2007, 16:33 
Экс-модератор
Аватара пользователя


23/12/05
12062
Всем спасибо. Работает и достаточно быстро

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 8 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group