0 / 0 / 0
Регистрация: 20.09.2018
Сообщений: 70
1

Соединить конечное множество точек на плоскости замкнутой линией с вершинами в этих точках

12.11.2018, 13:51. Показов 4249. Ответов 32

Author24 — интернет-сервис помощи студентам
Нужна помощь со сборкой задачи.

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

Если кто не знает, в полярной системе координат также как и в декартовой есть две координаты: полярный радиус и полярный угол. Полярный радиус это расстояние от точки О - полюса до заданной точки Полярный угол это угол между полупрямой ОХ(полупрямой, т.к нет отрицательных значений, это как обычная декартова ОХ, но без отрицательных значений) и полярным вектором от точки О до заданной точки. Отсчитывается против часовой стрелки.

Я написал функцию для расчёта полярных координат из декартовых, работает, но пока только для каких-то отстранённых значений. Полярный радиус рассчитывается в радианах.
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
#include "stdafx.h"
#include <iostream>
#include <cmath>
using namespace std;
 
void conv(double& x1, double y1)
{
    double rad = sqrt(x1*x1 + y1*y1),
        ygol = acos(x1 / rad);
    x1 = rad;
    y1 = ygol;
}
 
int main()
{
    setlocale(LC_ALL, "Russian");
    double a, b;
    cin >> a >> b;
    conv(a, b);
    cout << a;
    cout << b;
    system("pause");
    return 0;
}
Я думаю, что надо создать многомерный массив и потом отсортировать его два раза. Сначала по значениям углов, которые будут записаны вторыми элементами во вложенных массивах, а потом по значениям радиусов. Только вот сортировку я ещё не проходил(и многомерные массивы тоже), так что думаю. Осложняется задача тем, что всё должно задаваться с клавиатуры - число точек и их координаты. И вот тут надо бы ещё как-то задать названия точек Т1, Т2 там. Как блин это сделать? Как присвоить имена вложенным массивам, при условии, что изначально их число не определено?
Потом ещё веселее: подозреваю, с указателями на вложенные массивы-точки для функции будет та ещё заморочка.

Помогите пожалуйста, скоро сдавать.

Добавлено через 1 час 17 минут
Так, я уточнил у препода, кол-во точек задать константой, ибо конечное написано в условии. Одной проблемой меньше.
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
12.11.2018, 13:51
Ответы с готовыми решениями:

Задано множество точек в трехмерном пространстве. Найти минимум радиусов шаров с центрами в этих точках, содержащих ровно n точек этого множества
Задано множество точек в трехмерном пространстве. Найти минимум радиусов шаров с центрами в этих...

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

Геометрия (Найти все четырёхугольники, являющиеся выпуклыми, с вершинами в этих точках)
Дано N точек на плоскости.Найти все четырёхугольники, являющиеся выпуклыми, с вершинами в этих...

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

32
0 / 0 / 0
Регистрация: 20.09.2018
Сообщений: 70
13.11.2018, 04:41  [ТС] 21
Author24 — интернет-сервис помощи студентам
TheCalligrapher, Именно вставками? Я не находил. Можно ссылочку?
0
Вездепух
Эксперт CЭксперт С++
11688 / 6367 / 1723
Регистрация: 18.10.2014
Сообщений: 16,050
13.11.2018, 04:57 22
Цитата Сообщение от Ygg Посмотреть сообщение
Кликните здесь для просмотра всего текста
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <iostream>
#include <cmath>
#include <time.h>
 
struct Point
{
    int ind;     // исходный индекс точки, что бы сохранить порядок при сортировке
    double x;    // координата X
    double y;    // координата Y
    double a;    // угол в градусах
    double r;    // радиус
 
    void conv() // посчитать <a> и <r>
    {
        r = sqrt(x*x + y*y);
 
        if (r == 0.0)
        {
            a = 0.0;
        }
        else
        {
            a = 180.0 * acos(x / r) / acos(-1.0);
            if (y < 0)
                a += 180;
        }
    }
 
    int compare(Point &right) // сравнить this (левый операнд) с указанной структурой <right> (правый операнд)
    {
        if (a < right.a)
            return -1; // меньше
        if (a > right.a)
            return 1; // больше
 
        // углы равны, сравниваем радиус
 
        if (r < right.r)
            return -1; // меньше
        if (r > right.r)
            return 1; // больше
 
        return 0; // точки совпадают
    }
};
 
#define POINTS_COUNT 5
 
int main()
{
    srand((unsigned int)time(0));
 
    Point points[POINTS_COUNT];
 
    // инициализация
    for (int i = 0; i < POINTS_COUNT; i++)
    {
        points[i].ind = i;
        points[i].x = 200 * rand() / RAND_MAX - 100;
        points[i].y = 200 * rand() / RAND_MAX - 100;
 
        points[i].conv();
        std::cout << i+1 << ") (x=" << points[i].x << ", y=" << points[i].y << ") - (a=" << points[i].a << ", r=" << points[i].r << ")" << std::endl;
    }
 
    // сортировка
    for (int i = 0; i < POINTS_COUNT-1; i++)
    {
        for (int j = i+1; j < POINTS_COUNT; j++)
        {
            if (points[i].compare(points[j]) > 0)
            {
                Point temp = points[i];
                points[i] = points[j];
                points[j] = temp;
            }
        }
    }
 
    // результат сортировки
    std::cout << std::endl;
    for (int i = 0; i < POINTS_COUNT; i++)
    {
        std::cout << points[i].ind + 1 << ") a=" << points[i].a << ", r=" << points[i].r << std::endl;
    }
    std::cout << std::endl;
 
    system("pause");
    return 0;
}
Но это решение полностью игнорирует тот факт, что в задаче требуется построить замкнутую (!) ломаную без самопересечений. Решение неправильное, что очевидно на примере { { 2, 5 }, { 2, 2 }, { 6, 3 }, { 5, 0 } }. Построенная этим кодом ломаная получается самопересекающейся.
0
0 / 0 / 0
Регистрация: 20.09.2018
Сообщений: 70
13.11.2018, 05:00  [ТС] 23
TheCalligrapher, Я понимаю, но мне бы хоть так сделать! Всю ночь провозился, так и не смог вставками сделать, а надо обязательно.

Добавлено через 1 минуту
Если подобрать определенные точки, выдает нормальное решение, этого мне хватит, с нас особо не дерут, но надо сначала сделать эти чёртовы вставки.
0
Вездепух
Эксперт CЭксперт С++
11688 / 6367 / 1723
Регистрация: 18.10.2014
Сообщений: 16,050
13.11.2018, 05:13 24
Цитата Сообщение от else aaa Посмотреть сообщение
Всю ночь провозился, так и не смог вставками сделать, а надо обязательно.
Здесь я тоже вынужден вас разочаровать. Границы между примитивными алгоритмами сортировки довольно размыты, но с канонической точки зрения вот это

Цитата Сообщение от Ygg Посмотреть сообщение
C++
1
2
3
4
5
6
7
8
9
10
11
12
for (int i = 0; i < POINTS_COUNT-1; i++)
* * {
* * * * for (int j = i+1; j < POINTS_COUNT; j++)
* * * * {
* * * * * * if (points[i].compare(points[j]) > 0)
* * * * * * {
* * * * * * * * Point temp = points[i];
* * * * * * * * points[i] = points[j];
* * * * * * * * points[j] = temp;
* * * * * * }
* * * * }
* * }
- это как раз таки одна из вариаций сортировки выбором (которая даже приближает ее к сортировке пузырьком), а отнюдь не сортировка вставками.
0
0 / 0 / 0
Регистрация: 20.09.2018
Сообщений: 70
13.11.2018, 10:30  [ТС] 25
TheCalligrapher, Так я же говорю, что это не вставки. Я так и не допер, как их делать. Так есть на форуме подобные решения вставками? Поиск ничего не даёт.

Добавлено через 25 минут
TheCalligrapher, По факту, вопрос в том, как сформировать условие для аогритма сортировки вставками. Как заставить его выбирать нужный элемент с помощью структуры условий.

Добавлено через 1 час 44 минуты
SuperKir, TheCalligrapher, Вообще, можно преобразовать условие от решения пузырьком к решению вставками?

Добавлено через 3 часа 4 минуты
Чёт не нашёл я решение этой задачи на С++ на форуме. Ладно, делать нечего, будем решать. Ygg,
Что бы избежать пересечения можно просто найти минимумы и максимумы координат X и Y по заданным точкам. Получить среднее CX=(Xmin+Xmax)/2 и CY=(Ymin+Ymax)/2. А при расчёте полярных координат (a и r) вычесть среднее из координат (x и y) каждой точки.
Если я каким-то чудом допру, как решать, то чтобы вот это сработало, я должен рассчитать все координаты, потом найти среди них максимумы и минимумы, и отсортировать уже с помощью среднего, я правильно понял? А как мне объяснить этот алгоритм?
0
2376 / 833 / 317
Регистрация: 10.02.2018
Сообщений: 1,961
13.11.2018, 11:07 26
Лучший ответ Сообщение было отмечено else aaa как решение

Решение

1) Угол не правильно я считал, нужно было не прибавлять 180, а вычесть из 360.
2) Сортировка вставками
3) Среднее не подойдёт, с ним всё ещё возможны коллизии. Лучше центр масс посчитать.
4) Тест от TheCalligrapher
Кликните здесь для просмотра всего текста
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <iostream>
#include <cmath>
#include <time.h>
 
struct Point
{
    int ind;     // исходный индекс точки, что бы сохранить порядок при сортировке
    double x;    // координата X
    double y;    // координата Y
    double a;    // угол в градусах
    double r;    // радиус
 
    void conv(double xc = 0.0, double yc = 0.0) // посчитать <a> и <r>
    {
        r = sqrt((x - xc)*(x - xc) + (y - yc)*(y - yc));
 
        if (r == 0.0)
        {
            a = 0.0;
        }
        else
        {
            a = 180.0 * acos((x - xc) / r) / acos(-1.0);
            if ((y - yc) < 0)
                a = 360 - a;
        }
    }
 
    int compare(Point &right) // сравнить this (левый операнд) с указанной структурой <right> (правый операнд)
    {
        if (a < right.a)
            return -1; // меньше
        if (a > right.a)
            return 1; // больше
 
        // углы равны, сравниваем радиус
 
        if (r < right.r)
            return -1; // меньше
        if (r > right.r)
            return 1; // больше
 
        return 0; // точки совпадают
    }
};
 
#define POINTS_COUNT 4
 
int main()
{
    srand((unsigned int)time(0));
 
    Point points[POINTS_COUNT] = { { 0, 2, 5 },{ 1, 2, 2 },{ 2, 6, 3 },{ 3, 5, 0 } };
 
    // геометрический центр (центр масс)
    double xc = 0;
    double yc = 0;
    // инициализация
    for (int i = 0; i < POINTS_COUNT; i++)
    {
        points[i].ind = i;
        //points[i].x = 200 * rand() / RAND_MAX - 100;
        //points[i].y = 200 * rand() / RAND_MAX - 100;
 
        xc += points[i].x;
        yc += points[i].y;
    }
    xc /= POINTS_COUNT;
    yc /= POINTS_COUNT;
    std::cout << "xc=" << xc << " yc=" << yc << std::endl;
 
    // полярные координаты относительно центра масс
    for (int i = 0; i < POINTS_COUNT; i++)
    {
        points[i].conv(xc, yc);
        std::cout << i + 1 << ") (x=" << points[i].x << ", y=" << points[i].y << ") - (a=" << points[i].a << ", r=" << points[i].r << ")" << std::endl;
    }
 
    // сортировка (вставками)
    for (int i = 1; i < POINTS_COUNT; i++)
    {
        for (int j = i; (j > 0) && (points[j].compare(points[j - 1]) < 0); j--)
        {
            Point temp = points[j-1];
            points[j-1] = points[j];
            points[j] = temp;
        }
    }
 
    // результат сортировки
    std::cout << std::endl;
    for (int i = 0; i < POINTS_COUNT; i++)
    {
        std::cout << points[i].ind + 1 << " ";
    }
    std::cout << std::endl << std::endl;
 
    system("pause");
    return 0;
}
1
0 / 0 / 0
Регистрация: 20.09.2018
Сообщений: 70
13.11.2018, 11:26  [ТС] 27
Ygg, Чёрт, я даже не знаю, как Вас благодарить. Геометрический центр масс...Так, изучу. Но я много что не понял. Объясните, пожалуйста.
C++
1
#define POINTS_COUNT 4
Это я так понял макрос. Мы их не изучали. Если задам константой, ничего страшного?
C++
1
Point points[POINTS_COUNT] = { { 0, 2, 5 },{ 1, 2, 2 },{ 2, 6, 3 },{ 3, 5, 0 } };
Здесь мы задаём точки.
C++
1
2
3
4
5
6
7
8
9
10
// инициализация
    for (int i = 0; i < POINTS_COUNT; i++)
    {
        points[i].ind = i;
        //points[i].x = 200 * rand() / RAND_MAX - 100;
        //points[i].y = 200 * rand() / RAND_MAX - 100;
 
        xc += points[i].x;
        yc += points[i].y;
    }
А здесь что-то рандомно им присваиваем. Или что?
C++
1
2
3
4
5
6
7
8
9
for (int i = 1; i < POINTS_COUNT; i++)
    {
        for (int j = i; (j > 0) && (points[j].compare(points[j - 1]) < 0); j--)
        {
            Point temp = points[j-1];
            points[j-1] = points[j];
            points[j] = temp;
        }
    }
Я до такой сортировки вставками сам допёр, но боялся её использовать. В методичках написано, что в вставках обычно один цикл for. То есть ничего страшного, если их два?
Ну и...Можете пояснить всё, что связано с этим центром масс? По теории я про него прочитаю, я имею в виду в алгоритме. Он уж больно много где, сложно понять его функцию. при том что я даже не знаю, что это такое.
0
2376 / 833 / 317
Регистрация: 10.02.2018
Сообщений: 1,961
13.11.2018, 11:42 28
1) Макрос можно заменить константой.
2) Задаются тестовые точки. Первое число индекс, потом X, потом Y, потом всё повторяется для следующей точки.
3) Рандомное задание точек осталось от прошлой версии. Тут оно не используется и закоментированно, не убрано совсем что бы можно было быстро вернуться к прошлой реализации.
4) Для вставок на вики один for и вложенный в него while. Я как-то так написал, можете сделать по своему.
5) Геометрический центр - просто среднее по координатам. Суммируются координаты всех точек, а потом сумма делится на количество точек. Что бы перенести центр отсчёта в геометрический центр точек нужно вычесть его координаты из координат точек. Но я решил не трогать исходные координаты и просто сделал нужные вычитания в процессе вычисления полярных координат.
1
0 / 0 / 0
Регистрация: 20.09.2018
Сообщений: 70
13.11.2018, 11:52  [ТС] 29
Ygg, Спасибо за всё, не буду больше Вас мучить. Пойду разбираться, начну с блок-схемы.
0
Вездепух
Эксперт CЭксперт С++
11688 / 6367 / 1723
Регистрация: 18.10.2014
Сообщений: 16,050
13.11.2018, 21:16 30
Цитата Сообщение от Ygg Посмотреть сообщение
3) Среднее не подойдёт, с ним всё ещё возможны коллизии. Лучше центр масс посчитать.
Не совсем понял, что вы называете "средним". Центр масс в данном случае - это и есть усреднение координат точек. Если под "средним" вы имеете в виду то, что вы описали выше (т.е. центр охватывающего прямоугольника), то было бы интересно посмотреть, что за "коллизии" вы нашли.

По идее, любая точка, лежащая внутри выпуклой оболочки исходного набора, должна подходить в качестве начала координат при решении данной задачи. Центр охватывающего прямоугольника, если я что-то не упускаю, всегда удовлетворяет этому требованию.
0
2376 / 833 / 317
Регистрация: 10.02.2018
Сообщений: 1,961
13.11.2018, 22:55 31
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
По идее, любая точка, лежащая внутри выпуклой оболочки исходного набора, должна подходить в качестве начала координат при решении данной задачи. Центр охватывающего прямоугольника, если я что-то не упускаю, всегда удовлетворяет этому требованию.
Такой вот случай мне надумался. Но и его можно обойти, если чуть изменить алгоритм обхода.
Миниатюры
Соединить конечное множество точек на плоскости замкнутой линией с вершинами в этих точках  
0
Вездепух
Эксперт CЭксперт С++
11688 / 6367 / 1723
Регистрация: 18.10.2014
Сообщений: 16,050
13.11.2018, 23:18 32
Цитата Сообщение от Ygg Посмотреть сообщение
Такой вот случай мне надумался. Но и его можно обойти, если чуть изменить алгоритм обхода.
"Такой случай" может возникнуть практически при любом алгоритме выбора начала координат. (Разумеется, можно поставить задачу выбрать начало координат так, чтобы ни на одном полярном радиусе не было более одной вершины, но это на самом деле не нужно.) Правильная обработка ситуаций, когда несколько точек лежат на одном полярном радиусе - одна из деталей, которым нужно уделить внимание в данном алгоритме.

Я думаю, тут сработает такое правило:

При обработке текущего полярного радиуса в нашем упорядочении возможна ситуация, когда либо предыдущий полярный радиус, либо следующий полярный радиус отстоит от текущего ровно на 180°. Тогда

- если следующий полярный радиус отстоит на 180°, то вершины на текущем полярном радиусе (если их больше одной) надо соединять в порядке "к началу координат".

- если предыдущий полярный радиус отстоит на 180°, то вершины на текущем полярном радиусе (если их больше одной) надо соединять в порядке "от начала координат".

- в остальных случаях вершины на текущем полярном радиусе (если их больше одной) можно соединять в любом направлении.
0
2376 / 833 / 317
Регистрация: 10.02.2018
Сообщений: 1,961
14.11.2018, 00:03 33
Мне всё же кажется, что геометрический центр избавляет от необходимости изменять алгоритм обхода. По сложности же вычислений геометрический цент и центр охватывающего прямоугольника сопоставимы. Так что я предпочёл первый вариант, как менее сложный.
0
14.11.2018, 00:03
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
14.11.2018, 00:03
Помогаю со студенческими работами здесь

Построить множество треугольников с вершинами в заданных точках согласно условию
Прошу помочь с одним заданием по С++, начали изучать не так давно, поэтому не особо разбираюсь,...

Дана точка A(x; y) на координатной плоскости. Определить, принадлежит ли она треугольнику с вершинами в точках .
Дана точка A(x; y) на координатной плоскости. Определить, принадлежит ли она треугольнику с...

Соединить конечное множество точек на плоскости замкнутой линией без самопересечений с вершинами в этих точках.
Соединить конечное множество точек на плоскости замкнутой линией без самопересечений с вершинами...

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


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

Или воспользуйтесь поиском по форуму:
33
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru