16. Определение выпуклости многоугольника, нормали; разбиение невыпуклых. триангуляция. - p1xelse/CG GitHub Wiki

Внутреннее и внешнее отсечение.

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

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

В основном используется для работы с алгоритмом Кируса–Бека, где надо прежде всего убедиться, что окно отсекателя является выпуклым, а потом и вычислить внутренние нормали к каждой его стороне. Факт выпуклости или невыпуклости окна можно установить путем вычисления векторных произведений его смежных сторон и ананализ знаков этих произведений: все знаки равны нулю – многоугольник вырождается в отрезок; есть числа разных знаков(как - так и +) – многоугольник не выпуклый; все знаки неотрицательные – многоугольник выпуклый, а внутренние нормали ориентированны влево от его контура; в се знаки неположительные – многоугольник выпуклый, а внутренние нормали ориентированны вправо от его контура.

Определение нормали

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

Это уравнения для общего случая, частные нужно проверять(например если A - вертикальный отрезок, то (нужно это учесть)) Теперь для многоугольника. Мы нашли нормаль. Как определить, является ли она внутренней или внешней? Нужно опять взять скалярное произведение. В этот раз найденного вектора-нормали на вектор, начало которого в произвольной точке прямой(проще всего в начале стороны) а конец - в произвольной вершине многоугольника(важно, чтобы этот вектор не совпал со стороной, нормаль к которой мы искали). Если скалярное произведение > 0, то мы нашли внутреннюю нормаль. Если < 0, то внешнюю(нужно это учесть)(если нашли внешнюю нормаль, то обе ее составляющие нужно умножить на -1 и получим внутреннюю нормаль). Так же еще на лекции много раз было сказано о том, что векторы внутренней нормали ориентированы влево от направления обхода, при условии, конечно, что вершины мы обходили против часовой стрелки. Если обходили по часовой, то они ориентированы вправо от направления обхода

Разбиение невыпуклых многоугольников

Если многоугольник оказался не выпуклым в I+2 вершине то надо найти точки пересечения сторон с осью абсцисс. Из найденных точек пересечения выбрать ближайшую к началу системы координат(в данном случае одна, обозначена как C). Как разбить такой многоугольник на выпуклые? В первый многоугольник занести вершины начиная I+ 1 и заканчивая найденной точкой пересечения. Во второй многоугольник занести все вершины, начиная с точки пересечения, не попавшие в первый многоугольник. Каждый из полученных многоугольников так же проверить на выпуклость!

Триангуляция многоугольников

Триангуляция - разбиение геометрического объекта на треугольники прим. на самом деле на симплексы - n-мерные обобщения треугольника

Вы хотите сделать триангуляцию? Я вам скажу это возможно, их есть у меня.

Как разбить выпуклый многоугольник - понятно. Нужно либо любую вершину соединить со всеми остальными(слева). Но тогда некоторое треугольники будут сильно "вытянутами"(Получаем n - 2 треугольника, где n - количество сторон). Второй вариант - выбрать произвольную точку внутри фигуры(например, центр) и соединить её со всеми вершинами(количество полученных треугольников = количеству сторон).

1. Разбить невыпуклый многоугольник на выпуклые.

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

  • Перебераем все вершины, начиная с А1, тогда вершина А6 окажется невыпуклой, выбираем эту вершину в качестве "базовой"
  • Ищем такую диагональ, которая бы соединяла вершину А6 с любой другой, и чтобы она располагалась строго внутри многоугольника или проходила только через ребра из тех вершин, которые она соединяет (пробуем соединить с первой, и не получается - выходит за пределы, а вот со второй соединить уже можно, потом с вершиной А3, потом еще можно и с А4 соединить)

  • Вернемся к первому многоугольнику, и выясним, что он все еще невыпуклый. Смотрим по порядку и выясняем, что вершина А7 невыпуклая

  • Пробуем соединить с чем-нибудь. С вершиной А1 опять не можем, зато можем с А2

  • Возвращаемся к первому многоугольнику. Он опять невыпуклый. Теперь невыпуклая вершина А9.

  • Соединяем ее с вершиной А1

  • Остается только четырехугольник А2-А7-А8-А9, соединим любые две противоположные вершины.

PROFIT

2. Дополнить невыпуклый многоугольник до выпуклого.

Тут такой же пример, вершины не пронумерованы, но поверьте, на самом деле они пронумерованы так же, как и на предыдущем примере. Просто use imagination

ВАЖНО!

Есть такой прикол, Куров в лекции говорит соединять предыдущую и следующую веришину, а потом соединил веришну А5 и А10

Есть предположение, что он имел ввиду, что нужно проверить все пары вершин, но не сказал этого

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

  • Первую взять не можем, тк диагональ между вершиной А10 и А2 будет лежать внутри. Вторую тоже взять не можем, тк диагональ будет частично лежать внутри многоугольника. ... А вот вершины А6 и А8 соединить уже можно

  • Потом соединяем вершины А8 и А10

  • Потом соединяем вершины А10 и А15

  • И на последок A4 и A10

Далее нужно выполнить отсечение сначала по изначальной фигуре, а потом по треугольникам. Они должны быть разные. Т.е если, как на примере, внешнее по основному многоугольнику, то по полученным треугольникам - внутренее.

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