Разделы презентаций


геометрия презентация, доклад

Содержание

Точки и вектораЛюбую геометрическую задачу можно решить оперируя только точками и векторами.Отрезок можно представить как 2 точки. Ломаную – как последовательный набор точек. Любой многоугольник – это замкнутая ломаная. Прямую или

Слайды и текст этой презентации

Слайд 1геометрия
Школа::Кода
Олимпиадное программирование

2020-2021 Таганрог

геометрияШкола::КодаОлимпиадное программирование2020-2021 Таганрог

Слайд 2Точки и вектора
Любую геометрическую задачу можно решить оперируя только точками

и векторами.
Отрезок можно представить как 2 точки. Ломаную – как

последовательный набор точек. Любой многоугольник – это замкнутая ломаная.
Прямую или луч можно представить как точку и направляющий вектор.
Окружность или сферу – как точку, задающую центр, и радиус-вектор.
Для решения задач определяются структуры, описывающие точку и вектора, после чего реализуется алгоритм, который уже не содержит в себе координатного метода.
Точки и вектораЛюбую геометрическую задачу можно решить оперируя только точками и векторами.Отрезок можно представить как 2 точки.

Слайд 3Реализация вектора 1
Создадим структуру Vector. Сделаем её шаблонной так, как

некоторые задачи решаются в целых числах, а некоторые в вещественных.

Шаблонность добавляет универсальности но обычно не нужна в условиях соревнования.
Реализация вектора 1Создадим структуру Vector. Сделаем её шаблонной так, как некоторые задачи решаются в целых числах, а

Слайд 4Реализация вектора 2
Одной из характеристик вектора является его длина, которая

равна sqrt(x2 + y2). Заметим, что даже если сам вектор

имеет целочисленные координаты, его длина, скорее всего, имеет вещественное значение. Однако в некоторых задачах достаточно узнавать квадрат длины.

Слово const после имени метода позволяет его вызывать у констант типа данной структуры.

Реализация вектора 2Одной из характеристик вектора является его длина, которая равна sqrt(x2 + y2). Заметим, что даже

Слайд 5Реализация вектора 3
Сумма двух векторов – это вектор начало которого

совпадает с началом первого, а конец – с концом второго,

отложенного от конца первого.
Разность двух векторов – это вектор, который начинается в конце второго и заканчивается в конце первого, если первый и второй отложить от одной точки.

Унарный минус меняет направление вектора на обратное.

Реализация вектора 3Сумма двух векторов – это вектор начало которого совпадает с началом первого, а конец –

Слайд 6Реализация вектора 4
Скалярное произведение векторов a и b – это

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

ними. Зная координаты векторов, скалярное произведение можно вычислить как a.x * b.x + a.y * b.y в двухмерном пространстве или a.x * b.x + a.y * b.y + a.z * b.z в трёхмерном пространстве.
Векторное произведение векторов a и b в трёхмерном пространстве – это вектор c направленный перпендикулярно плоскости, задаваемой данными векторами, длина которого равна произведению длин этих векторов на синус угла между ними. В двухмерном пространстве векторное произведение – это число, равное a.x * b.y - a.y * b.x. По знаку этого числа можно определить, как по отношению к вектору a повёрнут вектор b (векторное произведение > 0 – против часовой стрелки, < 0 – по часовой стрелке, 0 – коллинеарные).
Реализация вектора 4Скалярное произведение векторов a и b – это число, равное произведению длин этих векторов на

Слайд 7Реализация вектора 4
Произведения вектора a на число b – это

вектор с, коллинеарный вектору а, его длина равна длине а,

умноженной на b, а направление совпадает с а, если k > 0, иначе является противоположным. Для того чтобы получить произведение вектора на число нужно каждую координату вектора умножить на это число.

a

b

a^b < 0 b^a > 0

Реализация вектора 4Произведения вектора a на число b – это вектор с, коллинеарный вектору а, его длина

Слайд 8Реализация вектора 5
Для удобства будет не лишним переопределить и операторы

потокового ввода-вывода.
Деление вектора a на число b – это операция,

эквивалентная произведению вектора а на число 1/b.
Реализация вектора 5Для удобства будет не лишним переопределить и операторы потокового ввода-вывода.Деление вектора a на число b

Слайд 9Реализация вектора 6
В качестве вспомогательных шагов часто может понадобиться получить

вектор в вещественных числах (если изначально он в целых), нормализовать

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

Слайд 10Реализация вектора 7
Для того что бы повернуть вектор на определённый

угол нужно умножить матрицу поворота на этот вектор.
Стандартные функции С++

работают с радианами.
Реализация вектора 7Для того что бы повернуть вектор на определённый угол нужно умножить матрицу поворота на этот

Слайд 11Проекция вектора на вектор
a
b
c
alpha
Вектор с – проекция вектора а на

вектор b.
Длина вектора с равна произведению длины вектора а на

косинус угла alpha. Она относиться к длине b как некоторый коэффициент k = |a|*cos(alpha)/|b|.
Тогда c = b * k.
Если вспомнить, что a * b = |a| * |b| * cos(alpha), то можно определить k как a * b / |b|2.
Проекция вектора на векторabcalphaВектор с – проекция вектора а на вектор b.Длина вектора с равна произведению длины

Слайд 12Реализация вектора 8
Метод ProjectionK возвращает коэффициент, на который нужно умножить

вектор, у которого вызван метод, чтобы получить проекцию на него

вектора, который является аргументом.
Метод Projection возвращает вектор-проекцию вектора v1 на вектор, у которого вызван метод.

Реализация вектора 8Метод ProjectionK возвращает коэффициент, на который нужно умножить вектор, у которого вызван метод, чтобы получить

Слайд 13Реализация точки 1
Структура точки довольно похожа на структуру вектора. В

некоторых случаях из точки может понадобиться получить вектор. Операторы ввода-вывода

переопределяются аналогичным образом.
Реализация точки 1Структура точки довольно похожа на структуру вектора. В некоторых случаях из точки может понадобиться получить

Слайд 14При прибавлении к точке вектора получается новая точка.
Соответственно, при вычитании

из одной точки другой получается вектор.
Реализация точки 2
В рамках соревнований,

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

Слайд 15Нахождение угла между двумя векторами
Разделив векторное произведение векторов на произведение

их длин получим синус угла между ними.
Разделив скалярное произведение

векторов на произведение их длин получим косинус угла между ними.
Нахождение угла между двумя векторамиРазделив векторное произведение векторов на произведение их длин получим синус угла между ними.

Слайд 16Немного прекода от себя…

Немного прекода от себя…

Слайд 17Полярный угол точки
Полярный угол точки – это угол между вектором,

с началом в точке пересечения координатных осей и концом в

этой точке, и осью Х.
Самая точная функция для нахождения полярного угла – это atan2(double Y, double X). Она возвращает значения в диапазоне [-π; π).

Сравнение вещественных чисел на равенство / неравенство

Так как вычисления в вещественных числах происходят с некоторой погрешностью, нельзя гарантировать, что результат вычислений будет равен ожидаемому числу со 100% точностью, а значит эти числа нельзя сравнивать через ‘==‘ или ‘!=‘.
Корректная проверка вещественных чисел на равенство: fabs(a - b) <= EPS (fabs(a - b) > EPS – проверка на неравенство).

Полярный угол точкиПолярный угол точки – это угол между вектором, с началом в точке пересечения координатных осей

Слайд 18Алгоритм нахождения ориентированной площади многоугольника
Пусть даны вершина N-угольника в порядке

обхода.
Заведём переменную res, изначально равную нулю.
Переберём все вершины. На каждом

шаге будем рассматривать ребро между вершинами i и i+1 прибавлять к результату удвоенную площадь трапеции, образуемой данным ребром, нормалями к оси Х и самой осью: res += (pi+1.x - pi.x) * (pi+1.y + pi.y).
В конце возьмём результат по модулю и разделим пополам, т.к. изначально суммировали удвоенную площадь. Это делается для увеличения точности подсчётов. Если координаты точек даны целыми числами, то до последнего шага вычисления можно проводить не прибегая к вещественным числам.
Алгоритм нахождения ориентированной площади многоугольникаПусть даны вершина N-угольника в порядке обхода.Заведём переменную res, изначально равную нулю.Переберём все

Слайд 19Алгоритм нахождения ориентированной площади многоугольника
Y
X
1
2
3
4
5
6
7
8
9

Алгоритм нахождения ориентированной площади многоугольникаYX123456789

Слайд 20Уравнение прямой
Каноническое уравнение прямой имеет вид a*x + b*y +

c = 0.
Пусть известны коэффициенты уравнения задающего прямую, и нужно

найти точку и направляющий вектор для описания этой прямой.

Y

X

p

v

v.x

v.y

v

Рассмотрим прямую, параллельную заданной и проходящую через начало координат. Она имеет такой же направляющий вектор v и коэффициент c = 0. Получаем, что a*v.x + b*v.y = 0 Откуда v.x = b и v.y = -a

Если прямая не вертикальная (b != 0), то в качестве p.x возьмём 0, тогда уравнение прямой принимает вид b*p.y + c = 0, откуда p.y = -c/b. Иначе возьмём 0 в качестве p.y, тогда p.x = -c/a

Уравнение прямойКаноническое уравнение прямой имеет вид a*x + b*y + c = 0.Пусть известны коэффициенты уравнения задающего

Слайд 21Уравнение прямой 2
Пусть известна точка p и направляющий вектор v,

задающие прямую. Требуется найти коэффициенты канонического уравнения для этой прямой.
Y
X
p
v
v.x
v.y
Подставим

в уравнение a*x + b*y + c = 0 коэффициенты a, b и координаты p, получим: -v.y*p.x + v.x*p.y + c = 0, откуда с = p.x*v.y - p.y*v.x = p.ToVector() ^ v

v

Рассмотрим прямую, параллельную заданной и проходящую через начало координат. Она имеет такой же направляющий вектор v и коэффициент c = 0. Получаем, что a*v.x + b*v.y = 0 Откуда a = -v.y и b = v.x

Уравнение прямой 2Пусть известна точка p и направляющий вектор v, задающие прямую. Требуется найти коэффициенты канонического уравнения

Слайд 22Реализация функций

Реализация функций

Обратная связь

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

Email: Нажмите что бы посмотреть 

Что такое TheSlide.ru?

Это сайт презентации, докладов, проектов в PowerPoint. Здесь удобно  хранить и делиться своими презентациями с другими пользователями.


Для правообладателей

Яндекс.Метрика