Как узнать попадает ли точка в окружность (3 видео)

Алгоритм определения попадания точки в контур на основе комплексного анализа

Привет всем Хабра людям. Хочу представить уважаемым читателям пример, когда сухая и далекая от жизни в нашем понимании высшая математика дала не плохой практический результат.

Содержание

Задача для алгоритма
Алгоритм на C++:
Пример
Определение принадлежности точки кругу с центром в начале координат
Pascal
Язык Си
Python
Уравнение окружности.
Примеры решения задач про уравнение окружности
Задача. Составить уравнение заданной окружности
Задача. Принадлежит ли точка уравнению окружности
📸 Видео

Сначала немного воспоминаний

Было это в бытность мою студентом одного из технических Вузов в 90-е, курсе наверно втором. Попал я как-то на олимпиаду по программированию. И вот на этой самой олимпиаде и было задача: задать координаты треугольника, тестовой точки на плоскости, и определить принадлежит ли эта точка области треугольника. В общем, плевая задачка, но тогда я ее так и не решил. Но после задумался – над более общей задачей – принадлежность полигону. Повторюсь – была середина 90 –х, интернета не было, книжек по компьютерной геометрии не было, а были лекции по вышке и лаборатория 286 –х с турбо паскалем. И вот так совпали звезды, что как раз в то время когда я размышлял над проблемой, на вышке нам читали теорию комплексного переменного. И одна формула (о ней ниже) упала на благодатную почву. Алгоритм был придуман и реализован на паскале (к сожалению мой полутора гиговый винт погиб и унес в небытие этот код и кучу других моих юношеских наработок). После института я попал работать в один НИИ. Там мне пришлось заниматься разработкой ГИС для нужд работников института и собственной одной из задачей было определение попадания объектов в контур. Алгоритм был переписан на С++ и отлично зарекомендовал себя в работе.

Задача для алгоритма

Определить:

принадлежит ли точка области D, ограниченной полигоном.

Вывод формул для последующего написания алгоритма ни в коем случае не претендует на математическую полноту и точность, а лишь демонстрирует инженерный (потребительский подход) к Царице ~~полей~~ наук.

Интегральная формула Коши

Пояснение с ~~рабоче-крестьянской~~ инженерной точки зрения:
— граница Г наш заданный контур,
— z0 -тестируемая точка
— f(z) — комплексная функция от комплексного аргумента нигде в контуре не обращается в бесконечность.

Те есть, чтобы установить принадлежность точки контуру, нам необходимо вычислить интеграл и сравнить его со значением функции в данной точки. Если они совпадают, то точка лежит в контуре. Замечание: интегральная теорема коши гласит, что если точка не лежит в контуре, те подынтегральное выражение нигде не обращается в бесконечность, то интеграл равен нулю. Это упрощает дело – нужно лишь вычислить интеграл и проверить его на равенство нулю: равен нулю точка не контура, отличен — лежит в контуре.
Займемся вычислением интеграла. За f(z) примем простую функцию 1. Не нарушая общности можно за z0 принять точку 0 (всегда можно сдвинуть координаты).

Избавляемся от мнимой единицы в знаменателе подынтегральной части и расщепим интеграл на действительную и мнимую части:

Получилось два криволинейных интеграла II рода.
Вычислим первый

Выполнятся условие не зависимости интеграла от пути, следовательно, первый интеграл равен нулю и его вычислять не нужно.

С мнимой частью такой фокус не проходит. Вспоминаем, что наша граница состоит из отрезков прямых, получаем:

Где Гi- это отрезок (xi,yi)- (xi+1,y i+1)
Вычислим i-ый интеграл. Для этого запишем уравнение i-го отрезка в параметрическом виде

Подставим в интеграл

и после громоздких и нудных преобразований получим следующую прельстивую формулу:

Окончательно получаем

Алгоритм на C++:

T – тип точки, например:
struct PointD
<
double x,y;
>;

Пример

Пример работы алгоритма написан с применением самой на мой взгляд великой библиотеки 2D графики:Anti-Grain Geometry (AGG) .

Управление:
клик левой кнопкой – добавление новой точки контура
правой кнопкой — замыкание контура
левой с зажатым Shift-ом – перенос тестовой точки

Господа, кому интересно, привожу более быстрый алгоритм. Уже не мой.
Отдельное и огромное спасибо forgotten за статейку.
template bool pt_in_polygon2(const T &test,const std::vector &polygon)
<

static const int q_patt[2][2]= < , >;

Видео:10 класс, 11 урок, Числовая окружностьСкачать

Определение принадлежности точки кругу с центром в начале координат

Вводятся координаты (x;y) точки и радиус круга ( r ). Определить принадлежит ли данная точка кругу, если его центр находится в начале координат.

Будем считать, что точка принадлежит кругу, если находится внутри его или на его окружности.

Из любой точки координатной плоскости можно провести отрезок к началу координат. Если длина этого отрезка больше радиуса круга, то точка лежит за пределами круга и, следовательно, не принадлежит ему. Если же отрезок, соединяющий точку и начало координат, меньше радиуса круга с центром в начале координат или равен ему, то точка будет принадлежать кругу.

Отрезок между любой точкой и нулевой точкой (началом координат) является гипотенузой прямоугольного треугольника, катеты которого равны значениям x и y координаты данной точки.

Таким образом задача сводится по-сути к двум действия:

Нахождение длины отрезка между точкой и началом координат по теореме Пифагора (квадрат длины гипотенузы равен сумме квадратов длин катетов).
Сравнению полученного значения с радиусом круга.

Видео:Определение принадлежности точки окружностиСкачать

Pascal

Определение принадлежности точки кругу с центром в начале координат паскаль

Видео:Как искать точки на тригонометрической окружности.Скачать

Язык Си

Для gcc компилировать с ключом -lm.

Видео:Точки на числовой окружностиСкачать

Python

Определение принадлежности точки кругу с центром в начале координат Python

Видео:Программирование на С++. Урок 10. Попадает ли точка в заштрихованную областьСкачать

Уравнение окружности.

Аналитическая геометрия дает единообразные приемы решения геометрических задач. Для этого все заданные и искомые точки и линии относят к одной системе координат.

В системе координат можно каждую точку охарактеризовать ее координатами, а каждую линию – уравнением с двумя неизвестными, графиком которого эта линия является. Таким образом геометрическая задача сводится к алгебраической, где хорошо отработаны все приемы вычислений.

Окружность есть геометрическое место точек с одним определенным свойством (каждая точка окружности равноудалена от одной точки, называется центром). Уравнение окружности должно отражать это свойство, удовлетворять этому условию.

Геометрическая интерпретация уравнения окружности – это линия окружности.

Если поместить окружность в систему координат, то все точки окружности удовлетворяют одному условию – расстояние от них до центра окружности должно быть одинаковым и равным окружности.

Окружность с центром в точке А и радиусом R поместим в координатную плоскость.

Если координаты центра (а;b), а координаты любой точки окружности (х; у), то уравнение окружности имеет вид:

Если квадрат радиуса окружности равен сумме квадратов разностей соответствующих координат любой точки окружности и ее центра, то это уравнение является уравнением окружности в плоской системе координат.

Если центр окружности совпадает с точкой начала координат, то квадрат радиуса окружности равен сумме квадратов координат любой точки окружности. В этом случае уравнение окружности принимает вид:

Следовательно, любая геометрическая фигура как геометрическое место точек определяется уравнением, связывающим координаты ее точек. И наоборот, уравнение, связывающее координаты х и у, определяют линию как геометрическое место точек плоскости, координаты которых удовлетворяют данному уравнению.

Видео:Точка O – центр окружности, на которой лежат точки ... | ОГЭ 2017 | ЗАДАНИЕ 10 | ШКОЛА ПИФАГОРАСкачать

Примеры решения задач про уравнение окружности

Задача. Составить уравнение заданной окружности

Составьте уравнение окружности с центром в точке 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 равенство неверно

Таким образом, заданная точка не принадлежит заданному уравнению окружности.