Алгоритм вращения многоугольника при его разбиении

@altair81420566 · Регистрация: 18.11.2015

Студворк — интернет-сервис помощи студентам

Привет всем. Помогите сделать лабу "Алгоритм разбиения не выпуклых многоугольников."

1. Для каждой i-й вершины многоугольник сдвигается для переноса упомянутой
вершины в начало координат.

2. Многоугольник поворачивается против часовой стрелки для совмещения (i +
1)-й вершины с положительной полуосью X.

3. Анализируется знак Y-координаты (i + 2)-й вершины.
Если Yi+2 >= 0, то в (i + 1)-й вершине выпуклость.
Если Yi+2 < 0, то в (i + 1)-й вершине не выпуклость и многоугольник
разрезается на два вдоль положительной полуоси X. Для этого вычисляется
пересечение положительной полуоси X с первой из сторон. Формируются два
новых многоугольника: первый многоугольник - вершины с (i + 1)-й до точки
пересечения.

Не могу понять именно алгоритм поворота. Дайте формулу для поворота или статью где можно подробно почитать.

@Shamil1 · 19.11.2015, 04:15

Матрица преобразования для поворота:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\begin{pmatrix}cos\varphi & sin\varphi \\ -sin\varphi & cos\varphi \end{pmatrix}$
Сам угол поворота вычислять не нужно - достаточно вычислить cos и sin из соотношения сторон прямоугольного треугольника.

@Igor3D · 19.11.2015, 09:41

Сообщение от altair81420566

Не могу понять именно алгоритм поворота. Дайте формулу для поворота или статью где можно подробно почитать.

Школьные формулы

cos(a + b) = cos(a) * cos(b) - sin(a) * sin(b);
sin(a + b) = cos(a) * sin(b) + sin(a) * cos(b);

Косинус и синус (b) - это проекции исходного единичного вектора на оси х и y, т.е. его координаты (x_old и y_old). А косинус и синус (a + b) - проекции (координаты) повернутого вектора (x_new и y_new). Итого

x_new = x_old * cos(a) - y_old * sin(a);
y_new = y_old * cos(a) + x_old * sin(a);

Обычно эти рассуждения опускаются и приводится просто матрица (пост выше). Посчитав определитель "крестиком" получите то же самое

@altair81420566 · 19.11.2015, 20:38 **[ТС]**

Косинус и синус (b) - это проекции исходного единичного вектора на оси х и y, т.е. его координаты (x_old и y_old). А косинус и синус (a + b) - проекции (координаты) повернутого вектора (x_new и y_new). Итого
x_new = x_old * cos(a) - y_old * sin(a);
y_new = y_old * cos(a) + x_old * sin(a);

А что есть cos(a) и sin(a), как их вычислить и на сколько градусов должен повернуться многоугольник?

@Igor3D · 20.11.2015, 09:20

Сообщение от altair81420566

А что есть cos(a) и sin(a), как их вычислить и на сколько градусов должен повернуться многоугольник?

Это косинус и синус угла поворота (а).

Сообщение от altair81420566

2. Многоугольник поворачивается против часовой стрелки для совмещения (i +1)-й вершины с положительной полуосью X.

Есть 2 вершины p[i] и p[i+1], тогда

C++
1
2
3
// вектор из p[i] в p[i+1]
float dx = p[i+1].x - p[i].x;
float dy = p[i+1].y - p[i].y;

Тогда угол (в радианах)

C++
1
float angle = atan2(dy, dx);

Но, как уже говорилось, сам угол не требуется, проще (техничнее) вычислить cos и sin так

C++
1
2
3
float len = sqrt(dx * dx + dy * dy);
float cosA = dx / len;
float sinA = -dy / len;

Обратите внимание что sinA c минусом, это соответствует повороту ПО часовой стрелке (а не против). Теперь повернутая вершина p[i + 2] будет

C++
1
2
3
4
dx = p[i + 2].x - p[i].x; 
dy = p[i + 2].y - p[i].y; 
x_new = dx * cosA - dy * sinA;
y_new = dy * cosA + dx * sinA;

Для проверки найдите повернутую p[i+1], ee x > 0 и y = 0

@altair81420566 · 22.11.2015, 20:05 **[ТС]**

После поворота рисуется абракадабра. Если не затруднит, укажите на ошибки.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
std::vector<Vertex> Turning(std::vector<Vertex> Vertices)
{
 
    int dx = 0;
    int dy = 0;
 
  for(int i = 0; i < Vertices.size(); i++)
  {
 
 
   if(i != (Vertices.size() - 1))
   {
     dx = Vertices[i + 1].x - Vertices[i].x;
     dy = Vertices[i + 1].y - Vertices[i].y;
   } else
     {
        dx = Vertices[0].x - Vertices[i].x;
        dy = Vertices[0].y - Vertices[i].y;
     }
   if(dx < 0)
    {
       dx = dx * (-1);
    }
    if(dy < 0)
    {
       dy = dy * (-1);
    }
 
    int len = sqrt(dx * dx + dy * dy);
 
    if(len == 0)
     {
 
     break;
 
     }
 
    int cosA = dx / len;
    int sinA = -dy / len;
 
   if(i < (Vertices.size() - 2))
   {
    dx = Vertices[i + 2].x - Vertices[i].x;
    dy = Vertices[i + 2].y - Vertices[i].y;
   } else if( i == (Vertices.size() - 2))
     {
       dx = Vertices[0].x - Vertices[i].x;
       dy = Vertices[0].y - Vertices[i].y;
     } else if( i == (Vertices.size() - 1))
       {
       dx = Vertices[1].x - Vertices[i].x;
       dy = Vertices[1].y - Vertices[i].y;
       }
   if(dx < 0)
   {
      dx = dx * (-1);
   }
   if(dy < 0)
   {
    dy = dy * (-1);
   }
 
    Vertices[i].x = dx * cosA - dy * sinA;
    Vertices[i].y = dy * cosA + dx * sinA;
  }
  return Vertices;
}

@Shamil1 · 23.11.2015, 00:36

Вращать надо Вы не рёбра, а вершины. И все - относительно одной и той же точки, на один и тот же угол. Поэтому cos и sin надо вычислять только один раз.

Добавлено через 1 минуту
Вы делаете преобразование координат - поворот. Вам сначала надо рассчитать коэффициенты для данного преобразования, а потом применить его ко всем вершинам (чтобы получить новые координаты вершин).

@Igor3D · 23.11.2015, 10:27

Сообщение от altair81420566

Если не затруднит, укажите на ошибки.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
Vertex operator - ( const Vertex & v1, const Vertex & v0 ) 
{
 Vertex v;
 v.x = v1.x - v0.x;  
 v.y = v1.y - v0.y;  
 return v;
}
 
typedef std::vector<Vertex> TVec;
 
TVec Turning( const TVec & src, size_t rotateIndex )   
{
  TVec dst(src.size());
  assert(rotateIndex < src.size());
  const Vertex & cntr = src[rotateIndex];
  Vertex vec = src[(rotateIndex + 1) % src.size()] - cntr;
 
  float len = sqrt(vec.x * vec.x + vec.y * vec.y);  // hint: Vertex::length()
  float cosA = vec.x / len;
  float sinA = -vec.y / len;
 
  for (size_t i = 0; i < src.size(); ++i)
  {
     vec = src[i] - cntr;
     dst[i].x = vec.x * cosA - vec.y * sinA;   // hint: Vertex::rotate( cosA, sinA )
     dst[i].y = vec.y * cosA + vec.x * sinA;
  }
  return dst;
}

Писал здесь, возможны ошибки

Новые блоги и статьи Все статьи Все блоги /
Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly 8Observer8 24.01.2026 Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а привычная функция main(). . .	моя боль iceja 24.01.2026 Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .	Модель сукцессии микоризы anaschu 24.01.2026 Решили писать научную статью с неким РОманом	http://iceja.net/ математические сервисы iceja 20.01.2026 Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .
http://iceja.net/ сервер решения полиномов iceja 18.01.2026 Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .	Расчёт переходных процессов в цепи постоянного тока igorrr37 16.01.2026 / * Дана цепь(не выше 3-го порядка) постоянного тока с элементами R, L, C, k(ключ), U, E, J. Программа находит переходные токи и напряжения на элементах схемы классическим методом(1 и 2 з-ны. . .	Восстановить юзерскрипты Greasemonkey из бэкапа браузера damix 15.01.2026 Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .	Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/

@altair81420566 0 / 0 / 0 Регистрация: 18.11.2015 Сообщений: 7

	Алгоритм вращения многоугольника при его разбиении 18.11.2015, 23:53. Показов 1965. Ответов 7 Метки нет (Все метки) Привет всем. Помогите сделать лабу "Алгоритм разбиения не выпуклых многоугольников." 1. Для каждой i-й вершины многоугольник сдвигается для переноса упомянутой вершины в начало координат. 2. Многоугольник поворачивается против часовой стрелки для совмещения (i + 1)-й вершины с положительной полуосью X. 3. Анализируется знак Y-координаты (i + 2)-й вершины. Если Yi+2 >= 0, то в (i + 1)-й вершине выпуклость. Если Yi+2 < 0, то в (i + 1)-й вершине не выпуклость и многоугольник разрезается на два вдоль положительной полуоси X. Для этого вычисляется пересечение положительной полуоси X с первой из сторон. Формируются два новых многоугольника: первый многоугольник - вершины с (i + 1)-й до точки пересечения. Не могу понять именно алгоритм поворота. Дайте формулу для поворота или статью где можно подробно почитать. 0

@Shamil1 Модератор 3134 / 2281 / 469 Регистрация: 26.03.2015 Сообщений: 8,877
	19.11.2015, 04:15
	Матрица преобразования для поворота: $https://www.cyberforum.ru/cgi-bin/latex.cgi?\begin{pmatrix}cos\varphi & sin\varphi \\ -sin\varphi & cos\varphi \end{pmatrix}$ Сам угол поворота вычислять не нужно - достаточно вычислить cos и sin из соотношения сторон прямоугольного треугольника. 1

@Shamil1 Модератор 3134 / 2281 / 469 Регистрация: 26.03.2015 Сообщений: 8,877
	23.11.2015, 00:36
	Вращать надо Вы не рёбра, а вершины. И все - относительно одной и той же точки, на один и тот же угол. Поэтому cos и sin надо вычислять только один раз. Добавлено через 1 минуту Вы делаете преобразование координат - поворот. Вам сначала надо рассчитать коэффициенты для данного преобразования, а потом применить его ко всем вершинам (чтобы получить новые координаты вершин). 1

Алгоритм вращения многоугольника при его разбиении

Решение