AZEN-SGG/MSUStudentWork
1
0
Fork 0
Code Issues Pull requests Projects Releases Packages Wiki Activity Actions
Page: Вычислительная Геометрия
Pages
Home Makefile Автотест Вычислительная Геометрия Обработка последовательностей СИ
0 Вычислительная Геометрия
Sergey edited this page 2024-12-21 20:13:18 +03:00
Unescape Escape
Table of Contents
This file contains ambiguous Unicode characters

This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

Вычислительная Геометрия

Вычислительная геометрия предполагает работу с геометрическими объектами (точками, отрезками, многоугольниками), которые удобно представлять структурами в C. Данный подход повышает уровень абстракции: вместо разрозненных чисел мы оперируем наглядными сущностями вроде point и circle, что упрощает реализацию и чтение кода.

Кратко о Структурах в C

Структура — это составной тип, объявляемый с помощью ключевого слова struct. Пример простого определения структуры:

struct point {
    double x;
    double y;
};

  • После объявления структуры компилятор «знает» её внутреннее устройство (какие поля и какого типа она содержит) и может выделять под неё память.

  • Чтобы использовать структуру, создаём переменную (или несколько):

    struct point p;       // переменная p типа struct point
p.x = 3.14;           // обращение к полю x
p.y = 2.71;           // обращение к полю y

  • Возможна инициализация при объявлении:

    struct point p = {3.14, 2.71};

  • В крупных программах структуры обычно выносятся в отдельные заголовочные файлы (.h), а их методы/функции, работающие с ними, — в исходные файлы (.c). Это позволяет поддерживать код модульным и переиспользуемым.

Пример:

typedef struct {
    double x;
    double y;
} point;

Теперь вместо struct point можно писать просто point.

Задачи по Вычислительной Геометрии

Ниже приведён список основных задач, относящихся к вычислительной геометрии (см. официальное условие). Всего их 10, но здесь мы делаем акцент на двух из них:

  1. Ломаная, самопересечения (не рассмотрено).
  2. Проверка выпуклости многоугольника (не рассмотрено).
  3. Расположение точки относительно многоугольника (не рассмотрено).
  4. [a, b] на прямой и его принадлежность объединению отрезков (не рассмотрено).
  5. Расстояние между многоугольниками (не рассмотрено).
  6. Минимальный охватывающий круг для набора точек.
  7. Максимальное объединение отрезков (не рассмотрено).
  8. Растущие круги (не рассмотрено).
  9. Выпуклая оболочка (не рассмотрено).
  10. Построение нового многоугольника путём смещения сторон.

Ссылки на Решения

Далее рассмотрим их подробнее.

Задача №6: Минимальный Охватывающий Круг

Идея: Дан набор точек на плоскости; требуется найти круг наименьшего радиуса, содержащий все эти точки.

Используемые Структуры

typedef struct {
    double x;
    double y;
} point;

typedef struct {
    point center;
    double radius;
} circle;
  • point описывает координаты (x,y).
  • circle хранит координаты центра и радиус.

Также вводятся вспомогательные структуры:

typedef struct {
    point * array; 
    int length;
} points;

Она упрощает работу с динамическим массивом точек.

Алгоритм Вельзля (Welsz)

Основная функция может называться MEC (Minimum Enclosing Circle). Суть:

  1. Если мы прошли по всем точкам и собрали так называемый «множество опорных точек» (не более 3), то строим «примитивный» круг по этим опорным точкам (2 точки задают окружность через их серединный отрезок, 3 точки — через окружность, описанную вокруг треугольника).
  2. Если очередная точка не лежит в текущем круге, она становится частью опорного множества, и мы перестраиваем круг.
  3. Процесс итеративно продолжается, пока не будем уверены, что все точки учтены.

В коде это отражается в рекурсивной функции:

circle MEC(point * I, int ilen, point * N, int nlen) {
    // I — все точки, N — опорные точки
    // ilen, nlen — их количества
}

При обнаружении «выпадающей» точки алгоритм добавляет её в массив опорных точек, а затем перестраивает окружность «с нуля» по меньшему набору.

Как Строится Окружность по Трём Точкам

Если в опорном множестве три точки (A, B, C), мы ищем центр (пересечение серединных перпендикуляров) и радиус:

point getCenter(point * warp) {
    // Возвращает координаты центра описанной окружности
}

circle byThreePoints(point * warp) {
    point center = getCenter(warp);
    double radius = distance(center, warp[0]);
    return (circle){center, radius};
}
  • distance(...) вычисляет длину отрезка.
  • getCenter(...) — формулы для нахождения пересечения перпендикуляров.

Надёжный Алгоритм (Hope)

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

Отличие:

  • Алгоритм Вельзля `MEC` — быстрая эвристика, дающая результат за меньшее время.
  • Алгоритм hope последовательно перебирает комбинации и точно находит минимальный круг, потенциально затрачивая больше вычислительных ресурсов.

Тестовые Наборы

В папке 6Ex есть разные входные файлы:

  • e: 1 1 1 1 1 1 1 1
    Проверяет поведение, когда все точки совпадают.
  • foi: 0 0 0 2 2 0 1 1
    Мешанина из нескольких точек внутри и на границах.
  • i: 1 0 -1 0
    Пара точек, круг через две точки.
  • n: 0
    Вероятно, пустая последовательность или нештатная ситуация.
  • o: 0 0
    Одна точка в нуле.
  • r: 0 0 2 0
    Две точки на оси Ox.
  • t: 0 0 0 2 2 0
    Три вершины прямоугольного треугольника.
  • tr: 0 0 1 0 2 0
    Проверка коллинеарных точек.
  • v: 0 0 0 1 0 2
    Ещё три коллинеарные точки на оси Oy.

Таким образом, мы проверяем случаи совпадения точек, пустых входов, разные комбинации расположений (на одной прямой, образующие треугольник и т.д.).

Вывод: Для наглядного результата координаты круга, выводимые программой, можно проверить, визуализировав их в графическом редакторе (например, Desmos).

Задача №10: Смещение Многоугольника

Идея: У нас есть многоугольник, заданный последовательностью точек. Нужно построить новый многоугольник, как если бы стороны исходного многоугольника «отодвинулись» (или сместились) перпендикулярно наружу/внутрь на расстояние h.

Ключевые Структуры

typedef struct {
	double x;
	double y;
} point;

typedef struct {
	point * arr;
	int len;
} points;

typedef struct {
	points pts; // массив точек, задающих многоугольник
} polygon;

Макросы и Препроцессор

В коде часто используются макросы. Например:

#define eps 1.e-6
#define ARR(TYPE, NAME) \
    typedef struct { \
        TYPE * arr; \
        int len; \
    } NAME
  • ARR(TYPE, NAME) — препроцессорная «заготовка» для описания структуры «динамический массив из TYPE». При компиляции макросы просто подменяются компилятором на соответствующие инструкции.

Пример:

ARR(point, points); // вместо этого компилятор видит развёрнутый код

Таким образом, мы быстро объявляем тип points без ручного прописывания каждой структуры.

Логика Решения

  1. Подготовка (repairPolygon): удаляем дублирующиеся точки и коллинеарные участки, чтобы многоугольник не имел подряд идущих вырожденных сторон.
  2. Поиск нормалей (getVectors): для каждой стороны (заданной двумя соседними точками) находится перпендикуляр (нормаль).
    normal AB = (B_y - A_y, A_x - B_x) и нормируем его (делим на длину).
  3. Смещение вершин: каждая вершина вносит вклад в две стороны. Мы складываем два перпендикуляра, умножая их на shift. Так происходит «двойное добавление» (по одному на каждую сторону, которая сходится к вершине).
  4. Формирование нового набора точек: создаём polygon со смещёнными координатами.

Тонкости

  • Обработка пограничных случаев: если многоугольник имеет менее 3 точек, он некорректен.
  • Нулевое смещение (если |shift| < eps) — бывает бессмысленно продолжать.
  • Вектор «вырожденной» стороны (нулевая длина) может приводить к ошибкам нормировки; функция isNull помогает отсечь такие случаи.

Тестовые Наборы

Сценарии:

  • Входные данные с почти совпадающими точками → проверка repairPolygon.
  • Слишком малое число точек (проверка на допустимость).
  • Большое значение shift (проверка, что стороны смещаются корректно).

Заключение

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

  • Мы используем структуры (point, line, polygon и т.д.) для наглядности и более высокого уровня абстракции.
  • Благодаря функциям (например, getPolygon(), MEC(), byThreePoints()) мы прячем низкоуровневые детали (циклы, проверки, арифметику) и думаем уже «геометрическими» сущностями.
  • Макросы помогают сократить повторяющийся шаблонный код, а препроцессор расширяет их ещё до компиляции.

↑ Наверх