Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.50/4: Рейтинг темы: голосов - 4, средняя оценка - 4.50
 Аватар для Morhuhan
0 / 0 / 0
Регистрация: 27.10.2020
Сообщений: 30

Слияние выпуклых оболочек

07.04.2023, 13:37. Показов 800. Ответов 6
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Пытаюсь реализовать функцию merge_hulls, которая должна осуществлять слияние оболочек P1 и P2. Алгоритм следующий:
1) Нахожу внутреннюю точку p из P1
2) Проверяю, принадлежит ли эта точка оболочке P2
3.1) Если принадлежит, то просто сливаю P1 и P2 в упорядоченный список и применяю к нему обход Грехама
3.2) Если не принадлежит, то пытаюсь использовать следующий подход:
Можно представить, что в точке p находится точечный источник света. Тогда граница P2 распадается на общую и затененную цепи. Очевидно, что вершины освещенной цепи могут быть удалены. Оставшаяся (затененная) цепь P2 (вместе с граничными точками) и граница P1 представляют собой два упорядоченных списка, соответствующих шестиугольникам. За время O (n) их можно объединить в один список точек P1 u P2, упорядоченный по возрастанию.

Подскажите, как можно наиболее безболезненно реализовать шаг 3.2), может быть у этого метода есть название? Буду рад помощи. Вот что я пока написал:

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
ConvexHull merge_hulls(ConvexHull P1, ConvexHull P2) {
 
    ConvexHull merged_hull;
 
    // Найти некоторую внутреннюю точку p многоугольника P1.
    point p = find_internal_point(P1);
 
    // Определить, является ли точка p внутренней точкой P2.
    if (isInside(p, P2)) {
 
        // Получаем упорядоченный список вершин P1 и P2
        int size1 = P1.getSize();
        int size2 = P2.getSize();
        point* points = new point[size1 + size2];
 
        for (int i = 0; i < size1; i++) {
            points[i] = P1.getPoints()[i];
        }
        for (int i = 0; i < size2; i++) {
            points[size1 + i] = P2.getPoints()[i];
        }
        quicksort_points(points, 0, size1 + size2 - 1);
 
        // Применяем обход Грехема к упорядоченному списку вершин
        merged_hull = graham_alg(points, size1 + size2);
        delete[] points;
 
    }
 
    // Если p не является внутренней точкой P2, применяем описанный шаг
    else {
 
 
 
    }
 
    return merged_hull;
}
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
07.04.2023, 13:37
Ответы с готовыми решениями:

Построение минимальных выпуклых оболочек
За дня два...в субботу защита, нужно еще оформить мне все. Нужно всего хотя бы два алгоритма! Любых!) в консольном приложении....очень...

Построение минимальных выпуклых оболочек, алгоритм Грэхема
Построение минимальных выпуклых оболочек. алгоритма Грэхема подскажите где ошибка. import _random def rotate(A,B,C): return...

Простое слияние, естественное слияние, многофазная сортировка
Дан текстовый файл, в котором записана последовательность целых чисел. написать программу сортировки с помощью алгоритмов внешней...

6
Заблокирован
07.04.2023, 15:49
Цитата Сообщение от Morhuhan Посмотреть сообщение
которая должна осуществлять слияние оболочек P1 и P2
Наверное стоило начать с пояснения что собой представляют "оболочки".
Ну ждите эксперта по "оболочкам".
0
 Аватар для Morhuhan
0 / 0 / 0
Регистрация: 27.10.2020
Сообщений: 30
07.04.2023, 17:12  [ТС]
Выпуклое множество — такое множество точек, что, для любых двух точек множества, все точки на отрезке между ними тоже принадлежат этому множеству.

Выпуклая оболочка множества точек — такое выпуклое множество точек, что все точки фигуры также лежат в нем.

Минимальная выпуклая оболочка множества точек — это минимальная по площади выпуклая оболочка.

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

Выпуклую оболочку реализует класс ConvexHull

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
class ConvexHull {
public:
 
    // Конструктор, принимающий массив точек и его размер
    ConvexHull(point* points, int size) {
        _size = size;
        _points = new point[size];
        for (int i = 0; i < size; i++) {
            _points[i] = point(points[i].x, points[i].y); // глубокое копирование
        }
    }
 
    // Конструктор по умолчанию
    ConvexHull() {
        _size=0;
        _points = nullptr;
    }
 
    // Метод для получения массива точек
    point* getPoints() const {
        return _points;
    }
 
    // Метод для получения размера массива точек
    int getSize() const {
        return _size;
    }
 
    void print_hull() {
        for (int i = 0; i < _size; i++) {
            printf("%f %f\n", _points[i].x, _points[i].y);
        }
    }
 
    void print_in_file(const char* filename) {
 
        ofstream outfile(filename);
 
        for (int i = 0; i < _size; i++) {
            outfile << _points[i].x << " " << _points[i].y << endl;
        }
    }
 
private:
 
    point* _points; // Указатель на массив точек
    int _size; // Размер массива точек
};
0
 Аватар для Наталья8
518 / 368 / 65
Регистрация: 09.03.2016
Сообщений: 3,880
07.04.2023, 17:56

Да ну на хрен...
Жизнь прожил, а про такую хрень, в первый раз слышу.
0
 Аватар для zayats80888
6352 / 3523 / 1428
Регистрация: 07.02.2019
Сообщений: 8,995
07.04.2023, 18:23
Цитата Сообщение от Morhuhan Посмотреть сообщение
Подскажите, как можно наиболее безболезненно реализовать шаг 3.2)
Не особо понятно, чем он выделяется на фоне 3.1, точнее, что там за магическая внутренняя точка.
Если вы хотите оптимизировать объединение непересекающихся оболочек, то можно поступить следующим образом:
1) спроецировать вершины на ось, перпендикулярную той, что соединяет геометрические центры оболочек (точнее, найти пары вершин для каждой оболочки с "максимальной" и "минимальной" проекцией).
2) далее соединить ребром вершины с "максимальными"("минимальными") проекциями.
3) для той оболочки, у которой "максимум"("минимум") "меньше"("больше"), проверяем условие "выпуклости" для "нового" и "следующего" ребра и, если нет, заменяем вершину нового ребра следующей вершиной этой оболочки, с учетом порядка обхода и изначального выбора ориентации оси проекции.
4) отбросить "внутренние цепочки" между новыми ребрами.

Все выше написанное не имеет математического обоснования и чисто интуитивно.
0
Вездепух
Эксперт CЭксперт С++
 Аватар для TheCalligrapher
12923 / 6792 / 1818
Регистрация: 18.10.2014
Сообщений: 17,187
08.04.2023, 09:48
Цитата Сообщение от Morhuhan Посмотреть сообщение
Слияние выпуклых оболочек
Что такое "слияние выпуклых оболочек"? Новая выпуклая оболочка? Или просто объединение исходных оболочек?

Цитата Сообщение от Morhuhan Посмотреть сообщение
Оставшаяся (затененная) цепь P2 (вместе с граничными точками) и граница P1 представляют собой два упорядоченных списка, соответствующих шестиугольникам.
О каких шестиугольниках идет речь? Откуда взялись именно шестиугольники?
0
 Аватар для Morhuhan
0 / 0 / 0
Регистрация: 27.10.2020
Сообщений: 30
08.04.2023, 12:27  [ТС]
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
Что такое "слияние выпуклых оболочек"? Новая выпуклая оболочка? Или просто объединение исходных оболочек?
Новая выпуклая оболочка, так как сначала нужно получить упорядоченный список всех точек из P1 и P2, а затем применить к нему обход Грехема, который создает из него выпуклую оболочку.

Цитата Сообщение от TheCalligrapher Посмотреть сообщение
О каких шестиугольниках идет речь? Откуда взялись именно шестиугольники?
Извиняюсь, тут речь идет о n-угольнике, я не заметил когда копировал
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
08.04.2023, 12:27
Помогаю со студенческими работами здесь

Пересечение линейных оболочек
Кто нибудь подскажет как найти пересечение линейных оболочек векторов е1= (1,0,1,2) е2=(0,1,1,0) и u1=(1,-1,0,2) u2=(0,1,0,1) ...

Найти базисы линейных оболочек
Приветствую, необходимо решить задачу следующего вида: Пусть L и M - линейные оболочки столбцов матриц A и B соответственно ...

Производительность BASH и подобных оболочек
Доброго времени суток уважаемые! Недавно встала необходимость написать пару дюжин скриптов обработки вывода программ (Linux). Иначе...

Сравнение данных оболочек базовых типов
Добрый день! Потихоньку занимаюсь изучением Java и натыкаюсь на некоторые странности. Не могли бы вы мне объяснит следующий момент. ...

Окно выбора оболочек показывает пустой список
Доброго времени суток! Установил ubuntu 16.04 LTS, поверх нее оболочку gnome3, все прошло успешно, но после перезагрузки список выбора...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
Новые блоги и статьи
PhpStorm 2025.3: WSL Terminal всегда стартует в ~
and_y87 14.12.2025
PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .
Как объединить две одинаковые БД Access с разными данными
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук
volvo 07.12.2025
Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Programma_Boinc 20.11.2025
Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
Ломающие изменения в C#.NStar Alpha
Etyuhibosecyu 20.11.2025
Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .
Мысли в слух
kumehtar 18.11.2025
Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .
Создание Single Page Application на фреймах
krapotkin 16.11.2025
Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru