Проверка попадания точки в окружность
Очень сильно оптимизирует поиск, так называемая, хэш-функция.
Выбирается какая-нибудь хэш-функция, например, в нашем случае вполне подойдет: f(x, y) = int( (k1*x + k2*y + k3)*N), где x, y — координаты центра окружности, N, k1, k2, k3 — константы (их можно выбрать так: если окружности размещаются примерно равномерно на площади от -100.0 до 100.0 по оси x и y, то k1 = 1.0, k2=1.0, N=100, k3=250.0, при этом будет 0
Далее окружности храним в хэш таблице, в соответствии с их хэш значаниями.
Теперь допустим у нас есть координаты X, Y, и мы хотим найти соответсвующую окружность. Мы получаем хэш значение H=f(X, Y). И по этому хэш значению получаем ссылку на окружность из хэш талицы (скорость этой операции = C * log(количество окружностей), что гораздо быстрей последовательного перебора), далее мы двигаемся взад вперед по хэш-табице пока не найдем нужную окружность.
P.S. Хэш-таблицы — это своего рода упорядоченные массивы по хэш значению, реализуемые, например, с помощью бинарных деревьев (или лучше B-деревьев). Вобщем в гугле посмотри, там есть много про хэш-таблицы
А ещё можно для начала проверять попала ли точка не в круг, а в охватывающий прямоугольник — всего лишь 4 сравнения, а лишь потом проверять на попадание в круг. Это bound называется. Во всех гамах используется — ищется пересечение не с произвольным mesh’ем, а с заданным bound’ом — параллелепипед, эллипсоид. а уж потом, иногда, с треугольниками.
Попадание точки в заданную область (Алгоритм)
Пусть необходимо определить попадает ли заданная точка с координатами (x,y) в заданную область:
В данном случае, очевидно, что точка (x,y) попадает на линию графика, если у=x. Точка попадает в закрашенную область, лежит выше линии графика, если y>x. Наконец, точка (x, y) лежит ниже линии графика, если y if y>x then writeln('Да, попадает') else writeln('Нет');
Аналогично, точка (x, y) попадает в закрашенную область,
Рассмотрим попадание точки в круг. Уравнение окружности: x2+y2=r2, в представленном на рисунке случае r=1.
МКоорд
Чтобы определить координаты точки на плоскости, проведем в этой плоскости две взаимно перпендикулярные числовые оси. Одну из осей называют осью абсцисс или осью (или ), другу — осью ординат или осью (или ).
Направление осей обычно выбирают так, чтобы положительная полуось совмещалась с положительной полуосью поворотом на против часовой стрелки.
Точку пересечения осей называют началом координат и обозначают буквой . Она является началом отсчета для каждой из двух числовых осей и .
Единицы масштаба на этих осях выбираются, как правило, одинаковыми.
Возьмем на плоскости некоторую точку и опустим из нее перпендикуляры на ось и ось . Точки пресечения и этих перпендикуляров с осями называются проекциями точки на оси координат.
Точки лежит на числовой оси , поэтому ей соответствует определенное число — её координата на этой оси. Точно так же точке соответствует определенное число — ее координата на оси .
Таким образом, каждой точке , лежащей на плоскости, ставятся в соответствие два числа и , которые называются прямоугольными декартовыми координатами точки . Число называется абсциссой точки , число — её ординатой
Обратно, каждым двум числам и можно сопоставить некоторую точку плоскости, для которой является абсциссой, а — ординатой.
Теперь установлено взаимно однозначное соответствие между точками плоскости и парами чисел и , следующих в определенном порядке(сначала , затем ).
Итак, прямоугольными декартовыми координатами точки на плоскости называются координаты проекций этой точки на оси координат на этих осях.
Координаты точки записываются обычно так: . На первом месте записывается абсцисса, на втором — ордината. Иногда, для краткости, вместо "точка с координатами " говорят "точка ".
Оси координат делят плоскость на четыре четверти( квадранта). Первой четвертью считается четверть между положительной полуосью и положительной полуосью . Далее четверти нумеруются по порядку против часовой стрелки.
Как узнать лежит ли точка на окружности заданной уравнением
Аналитическая геометрия дает единообразные приемы решения геометрических задач. Для этого все заданные и искомые точки и линии относят к одной системе координат.
В системе координат можно каждую точку охарактеризовать ее координатами, а каждую линию – уравнением с двумя неизвестными, графиком которого эта линия является. Таким образом геометрическая задача сводится к алгебраической, где хорошо отработаны все приемы вычислений.
Окружность есть геометрическое место точек с одним определенным свойством (каждая точка окружности равноудалена от одной точки, называется центром). Уравнение окружности должно отражать это свойство, удовлетворять этому условию.
Геометрическая интерпретация уравнения окружности – это линия окружности.
Если поместить окружность в систему координат, то все точки окружности удовлетворяют одному условию – расстояние от них до центра окружности должно быть одинаковым и равным окружности.
Окружность с центром в точке А и радиусом R поместим в координатную плоскость.
Если координаты центра (а;b), а координаты любой точки окружности (х; у), то уравнение окружности имеет вид:
Если квадрат радиуса окружности равен сумме квадратов разностей соответствующих координат любой точки окружности и ее центра, то это уравнение является уравнением окружности в плоской системе координат.
Если центр окружности совпадает с точкой начала координат, то квадрат радиуса окружности равен сумме квадратов координат любой точки окружности. В этом случае уравнение окружности принимает вид:
Следовательно, любая геометрическая фигура как геометрическое место точек определяется уравнением, связывающим координаты ее точек. И наоборот, уравнение, связывающее координаты х и у, определяют линию как геометрическое место точек плоскости, координаты которых удовлетворяют данному уравнению.
Примеры решения задач про уравнение окружности
Задача. Составить уравнение заданной окружности
Составьте уравнение окружности с центром в точке O (2;-3) и радиусом 4.
Решение.
Обратимся к формуле уравнения окружности:
R 2 = (x- a ) 2 + (y- b ) 2
Подставим значения в формулу.
Радиус окружности R = 4
Координаты центра окружности (в соответствии с условием)
a = 2
b = -3
Получаем:
(x — 2 ) 2 + (y — ( -3 )) 2 = 4 2
или
(x — 2 ) 2 + (y + 3 ) 2 = 16 .
Задача. Принадлежит ли точка уравнению окружности
Проверить, принадлежит ли точка A(2;3) уравнению окружности (x — 2) 2 + (y + 3) 2 = 16.
Решение.
Если точка принадлежит окружности, то ее координаты удовлетворяют уравнению окружности.
Чтобы проверить, принадлежит ли окружности точка с заданными координатами, подставим координаты точки в уравнение заданной окружности.
В уравнение ( x — 2) 2 + ( y + 3) 2 = 16
подставим, согласно условию, координаты точки А(2;3), то есть
x = 2
y = 3
Проверим истинность полученного равенства
( x — 2) 2 + ( y + 3) 2 = 16
( 2 — 2) 2 + ( 3 + 3) 2 = 16
0 + 36 = 16 равенство неверно
Таким образом, заданная точка не принадлежит заданному уравнению окружности.
Определение принадлежности точки кругу с центром в начале координат
Вводятся координаты (x;y) точки и радиус круга ( r ). Определить принадлежит ли данная точка кругу, если его центр находится в начале координат.
Будем считать, что точка принадлежит кругу, если находится внутри его или на его окружности.
Из любой точки координатной плоскости можно провести отрезок к началу координат. Если длина этого отрезка больше радиуса круга, то точка лежит за пределами круга и, следовательно, не принадлежит ему. Если же отрезок, соединяющий точку и начало координат, меньше радиуса круга с центром в начале координат или равен ему, то точка будет принадлежать кругу.
Отрезок между любой точкой и нулевой точкой (началом координат) является гипотенузой прямоугольного треугольника, катеты которого равны значениям x и y координаты данной точки.
Таким образом задача сводится по-сути к двум действия:
- Нахождение длины отрезка между точкой и началом координат по теореме Пифагора (квадрат длины гипотенузы равен сумме квадратов длин катетов).
- Сравнению полученного значения с радиусом круга.
Pascal
Определение принадлежности точки кругу с центром в начале координат паскаль
Язык Си
Для gcc компилировать с ключом -lm.
Python
Определение принадлежности точки кругу с центром в начале координат Python
Как определить лежит ли точка на окружности
Вводятся координаты (x;y) точки и радиус круга ( r ). Определить принадлежит ли данная точка кругу, если его центр находится в начале координат.
Будем считать, что точка принадлежит кругу, если находится внутри его или на его окружности.
Из любой точки координатной плоскости можно провести отрезок к началу координат. Если длина этого отрезка больше радиуса круга, то точка лежит за пределами круга и, следовательно, не принадлежит ему. Если же отрезок, соединяющий точку и начало координат, меньше радиуса круга с центром в начале координат или равен ему, то точка будет принадлежать кругу.
Отрезок между любой точкой и нулевой точкой (началом координат) является гипотенузой прямоугольного треугольника, катеты которого равны значениям x и y координаты данной точки.
Таким образом задача сводится по-сути к двум действия:
- Нахождение длины отрезка между точкой и началом координат по теореме Пифагора (квадрат длины гипотенузы равен сумме квадратов длин катетов).
- Сравнению полученного значения с радиусом круга.
Задача
Даны координаты точки и радиус круга с центром в начале координат. Определить, принадлежит ли данная точка кругу.
Решение
- x, y, r — координаты точки и радиус круга;
- r_xy — длина гипотенузы (расстояния от начала координат до точки).
Алгоритм решения задачи:
Следует рассмотреть прямоугольный треугольник, один катет которого лежит на любой оси, а другой является перпендикуляром к этой оси из заданной точки. В этом случае длины катетов равны значениям x и y, а гипотенуза является отрезком, соединяющим начало координат с точкой. Если этот отрезок не больше радиуса круга, то делается вывод, что точка принадлежит кругу.
Длина гипотенузы находится по теореме Пифагора.
Определить, принадлежит ли точка с координатами (x; y) кругу радиуса R с центром в начале координат.
Пользователь вводит координаты точки и радиус круга.
Если выбрать точку на координатной плоскости, то можно увидеть, что проекции ее координат на оси x и y являются катетами прямоугольного треугольника. А гипотенуза этого прямоугольного треугольника как раз показывает расстояние от начала координат до точки. Таким образом, если длина гипотенузы будет меньше радиуса круга, то точка будет принадлежать кругу; иначе она будет находится за его пределами.
Длину гипотенузы можно вычислить по теореме Пифагора: квадрат гипотенузы равен сумме квадратов катетов.
Пример выполнения программы:
Обратите внимание, можно вводить отрицательные координаты. При возведении в квадрат все-равно будет получено положительное число.
