Вершины в порядке обхода по часовой стрелке - C (СИ)
Формулировка задачи:
Выпуклый многоугольник на плоскости задан своими вершинами, расположенными в произвольном порядке. Расположить вершины в порядке обхода по часовой стрелке.
Помогите с заданием пожалуйста.
Решение задачи: «Вершины в порядке обхода по часовой стрелке»
textual
Листинг программы
#include <stdlib.h>
#include <stdio.h>
typedef struct Xy
{
int x, y;
} Xy;
static const Xy *xy_origin;
int cmp_polar_angle(const void *p1, const void *p2)
{
const Xy *xy1 = p1, *xy2 = p2;
Xy
origin_xy1 = { xy1->x - xy_origin->x, xy1->y - xy_origin->y },
origin_xy2 = { xy2->x - xy_origin->x, xy2->y - xy_origin->y };
long long area =
(long long) origin_xy1.x * origin_xy2.y -
(long long) origin_xy1.y * origin_xy2.x;
return (area > 0) - (area < 0);
}
int main()
{
Xy poly[] = { { 0, 0 }, { 2, 5 }, { -3, -1 }, { 0, 9 }, { -5, 3 } };
const unsigned n = sizeof poly / sizeof *poly;
/* Find min-y point */
for (unsigned i = 1; i < n; ++i)
if (poly[i].y < poly[0].y)
{
Xy temp = poly[0];
poly[0] = poly[i];
poly[i] = temp;
}
/* Sort the vertices */
xy_origin = &poly[0];
qsort(poly + 1, n - 1, sizeof *poly, cmp_polar_angle);
/* Done */
for (unsigned i = 0; i < n; ++i)
printf("{ %d, %d } ", poly[i].x, poly[i].y);
printf("\n");
}
Объяснение кода листинга программы
- Включаются необходимые заголовочные файлы
- Объявляется структура
Xyдля представления вершин - Инициализируется переменная
xy_origin, которая содержит координаты начальной вершины - Определяется функция
cmp_polar_angleдля сравнения вершин по углу относительно начальной вершины - В функции
mainинициализируется массивpolyс координатами вершин - Вычисляется количество вершин в массиве
polyи сохраняется в переменнуюn - Находится вершина с минимальной y-координатой (это будет начальная вершина)
- Сортируются вершины массива
polyотносительно начальной вершины с использованием функцииqsortи пользовательской функцииcmp_polar_angle - Выводятся координаты каждой вершины массива
polyчерез пробел - Программа завершается