эллипс. точка внутри или снаружи

[photon]

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

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

[PAV]

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

[AlexDem]

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

[photon]

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

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

[AlexDem]

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

[PAV]

AlexDem писал(а):

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

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

[AlexDem]

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

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

[photon]

Всем спасибо. Работает и достаточно быстро