Найти количество внутренних углов многоугольника, больше 180º

Question

Как узнать количество внутренних углов многоугольника, больше 180º, имея только вершины многоугольника?

Для каждой вершины я всегда хочу внутренний угол, а не внешний.

Спасибо из Бразилии.

Answer 1

Вы можете определить угол двух векторов, просто взяв скалярное произведение (скалярное произведение). Полезным свойством является то, что если векторы ортогональны, их скалярное произведение равно нулю; если их угол тупой, продукт отрицательный, в противном случае положительный. Итак, шаги, которые нужно предпринять:

• найдите первое ребро от V0 до V1 (как вектор, вы получите это, вычитая координаты), затем поверните его на 90 градусов влево (это просто преобразование (x y) в (-y x))
• найти второе ребро от V1 до V2 (не повернуто)
• возьмите скалярное произведение (это всего лишь (x1 * x2) + (y1 * y2))
• если скалярное произведение отрицательно, это поворот направо, в противном случае поворот налево
• следующий край ...
• если вы идете по вершинам против часовой стрелки, посчитайте количество правых поворотов, в противном случае количество левых поворотов
• для последней вершины вы должны вернуться к первой (т.е. использовать ребра от Vn до V0 и от V0 до V1)

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

     1  n-1
A = --- SUM( x(i)*y(i+1) - x(i+1)*y(i) )
     2  i=0

где n - количество вершин. x(n) и y(n) совпадают с x(0) и y(0) (чтобы закрыть многоугольник).

Если оно положительное, то вершины располагаются против часовой стрелки, в противном случае по часовой стрелке.

edit : При упрощении шагов поворота и скалярного произведения вы получаете формулу для двумерного перекрестного произведения, x1*y2 - x2*y1. Это упрощает первые шаги выше:

• найти первое ребро от V0 до V1 (как вектор, вычитая координаты)
• Дито для второго ребра от V1 до V2
• взять кросс произведение ((x1 * y2) - (x2 * y1))
• , если перекрестное произведение положительно, это левый поворот

Извините за запутанный первый подход.

Answer 2

1. Найдите выпуклой оболочки вершин.
2. Определите вершины, которые не лежат на выпуклой оболочке. Это ваши кандидатные вершины с> 180 внешними углами.
3. Для каждой такой вершины более подробно исследовать угол (сейчас не могу придумать никакого пути, но вы можете расширить его).

Answer 3

Находя внутренний угол двух последних векторов (как пример), нам нужно реализовать это уравнение для двух последних векторов многоугольника:

angleRadians = Math.acos ((vx1 * vx2 + vy1 * vy2) / (Math.sqrt (vx1 * vx1 + vy1 * vy1) * Math.sqrt (vx2 * vx2 + vy2 * vy2)));

это использование произведения точек векторов. Если у вас есть вопросы по этому вопросу, вот учебник

Но это не учитывает «направление намотки», сначала вы должны получить перекрестное произведение, и, если перекрестное произведение положительное, это был левый поворот, если отрицательным - правый поворот (для которого мы будем компенсировать, вычитая (ext) угол из 360.

Я включил здесь свой JS-код в качестве сущности: https://gist.github.com/3741816.

: D

Answer 4

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

Предполагая, что вы знаете связь, вам нужно будет рассчитать порядок намотки (то есть, в каком направлении точки проходят вокруг многоугольника?) Используя порядок намотки, вы можете затем взять перекрестное произведение каждой точки с соседними точками и получить обратный синус этой величины, чтобы получить угол.

Answer 5

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

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

Например,

tan(angle_to_left) = (v.y-left.x)/(v.y-left.y)
tan(angle_to_right) = (v.y-right.x)/(v.y-right.y)

Затем сложите углы вместе.

Наконец, для всех углов больше 180 увеличьте счетчик. После прохождения всех вершин ваш счетчик скажет вам, сколько внутренних углов больше 180.

Answer 6

Это вопрос, связанный с геометрией, не совсем связанный с программированием.

Если у вас есть вершины, вы можете просто найти внутренние углы с помощью тригонометрии, аналогично тому, как вы находите углы треугольника.

Используя три смежные вершины, представьте треугольник, и они найдут внутренние углы.

Например, посмотрите на многоугольник:

Мы можем построить треугольник как: