Вычислительная геометрия
Векторное произведение векторов
Модуль векторного произведения равен площади параллелограмма или удвоенной площади треугольника, построенного на перемножаемых векторах A BC DK
Проекция векторного произведения x y Ось z направлена к нам
Площадь Как найти площадь n-угольника? Модуль суммы, а не сумма модулей!!! Проводить векторы можно из любой точки, не обязательно из вершины
Если многоугольник не выпуклый Это тоже работает А если вычислять сумму модулей?
Точка и прямая Даны координаты точек A, B, C. Как расположена точка C относительно прямой AB: выше прямой; ниже прямой; на прямой? B A. C Вектор направлен к нам – точка выше прямой от нас – точка ниже прямой равен нулю – точка на прямой
Точка и отрезок Пересекает ли прямая AB отрезок CD? A B C D Ответ. Нет, если оба конца отрезка расположены по одну сторону от прямой.
Два отрезка Пересекаются ли отрезки AB и CD? A B C D A B C D A B A B C D C D Ответ. Пересекаются, если одновременно выполняются условия 1.Прямая AB пересекает отрезок CD 2.Прямая CD пересекает отрезок AB 3.Пересекаются ограничивающие прямоугольники A B Ограничивающий прямоугольник
Направление обхода В каком порядке: по часовой стрелке или против – заданы вершины многоугольника? (ABCD, ADCB) Вариант решения 1.Найти выпуклую вершину 2.Провести из неё векторы в 2 соседние 3.Найти векторное произведение проведённых векторов Одной из выпуклых вершин будет самая нижняя. Если самых нижних несколько, то самая левая из них. A B C D
Выпуклый? Заданы координаты вершин простого многоугольника в направлении обхода по или против часовой стрелки. Определить, является ли он выпуклым. Ответ. Если, обходя многоугольник вдоль границы, всё время поворачиваем в одну сторону (всё время направо или всё время налево), то многоугольник выпуклый. Осторожно со звёздами!