Найти выпуклую оболочку заданного множества точек на плоскости

@dendikk · Регистрация: 16.02.2020

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

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

@TheCalligrapher · 10.04.2020, 19:07

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

Может нужно переустановить Dev-C++?

Что у вас написано в закладке "Программы" настроек Dev-C++? Покажите скриншот.

@dendikk · 10.04.2020, 21:12 **[ТС]**

Вот

@TheCalligrapher · 10.04.2020, 21:28

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

Вот

Короче, не ясно, что происходит. "Переустанавливать" Dev-C++ не обязательно. Можно просто как я - взять портабельную версию Dev-C++ и попробовать там.

@dendikk · 10.04.2020, 21:49 **[ТС]**

Да,в портабельной версии заработало. А что именно делает второй код? Просто я вижу в коде заданные точки вами,и они в другой последовательности выводятся. Я думал,что задача состоит в том,что задано много точек на площади и нужно обвести их по крайним точкам и таким образом образуется многоугольник.

@TheCalligrapher · 11.04.2020, 02:16

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

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

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

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

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

Добавлено через 3 часа 59 минут
... И проверка показывает, что нет, алгоритм по ссылке приспособлен (оптимизирован) именно для решения задачи по ссылке. Строить выпуклую оболочку произвольного набора точек он не умеет.

@TheCalligrapher · 11.04.2020, 03:25

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

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
#include <stdlib.h>
#include <stdio.h>
 
typedef struct Xy
{
  int x, y;
} Xy;
 
int cmp_yx(const void *p1, const void *p2)
{
  const Xy *xy1 = p1, *xy2 = p2;
  int cmp;
 
  if ((cmp = (xy1->y > xy2->y) - (xy1->y < xy2->y)) != 0)
    return cmp;
 
  if ((cmp = (xy1->x > xy2->x) - (xy1->x < xy2->x)) != 0)
    return cmp;
 
  return 0;
}
 
int turn(const Xy *xy1, const Xy *xy2, const Xy *xy3)
{
  Xy v1 = { xy2->x - xy1->x, xy2->y - xy1->y }, v2 = { xy3->x - xy2->x, xy3->y - xy2->y };
  long long area = (long long) v1.x * v2.y - (long long) v1.y * v2.x;
  return (area < 0) - (area > 0);
}
 
unsigned add_vertex(Xy chain[], unsigned top, const Xy *xy, int bad_turn)
{
  chain[++top] = *xy;
 
  unsigned sub_top = top - 1;
  while (sub_top > 0 && 
         turn(&chain[sub_top - 1], &chain[sub_top], &chain[top]) == bad_turn)
    --sub_top;
 
  chain[++sub_top] = chain[top];
  return sub_top;
}
 
#define N 100u 
 
int main()
{
  Xy poly[N];
  
  for (unsigned i = 0; i < N; ++i)
  {
    poly[i].x = rand() % 1000;
    poly[i].y = rand() % 1000;
  }
 
  /* Sort */
 
  qsort(poly, N, sizeof *poly, cmp_yx);
 
  /* Build chains */
 
  Xy left_chain[N], right_chain[N];
  unsigned left_top = -1, right_top = -1;
 
  left_chain[++left_top] = poly[0];
  right_chain[++right_top] = poly[0];
 
  for (unsigned i = 1; i < N; ++i)
  {
    left_top = add_vertex(left_chain, left_top, &poly[i], -1);
    right_top = add_vertex(right_chain, right_top, &poly[i], +1);
  }
 
  /* Done */
 
  for (unsigned i = 0; i <= left_top; ++i)
    printf("%d, %d\n", left_chain[i].x, left_chain[i].y);
  printf("\n");
  
  for (unsigned i = right_top; i != -1u; --i)
    printf("%d, %d\n", right_chain[i].x, right_chain[i].y);
  printf("\n");
}

@TheCalligrapher · 11.04.2020, 11:21

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

@dendikk · 11.04.2020, 13:00 **[ТС]**

Понял,спасибо за помощь!

@dendikk · 15.04.2020, 11:00 **[ТС]**

TheCalligrapher, вопрос,а возможно ли написать этот код без структур? Оказывается нам еще структуры в коде использовать нельзя.

@TheCalligrapher · 15.04.2020, 11:09

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

озможно ли написать этот код без структур?

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

C
1
typedef int Xy[2];

Там где раньше писалось xy->x и xy->y теперь будет (*xy)[0] и (*xy)[1].

xy.x и xy.y теперь превратятся в xy[0] и xy[1].

poly[i].x и poly[i].y теперь превратятся в poly[i][0] и poly[i][1].

И т.д. и т.п.

Также: массивы в С нельзя копировать присваиванием, то есть везде, где в коде нужно такое копирование придется просто поэлементно скопировать два элемента или сделать memcpy.

Например:

C
1
left_chain[++left_top] = poly[0];

превратится в

C
1
memcpy(left_chain[++left_top], poly[0], sizeof(Xy));

Все.

@dendikk · 15.04.2020, 11:47 **[ТС]**

TheCalligrapher, поменял почти всё правильно вроде как,вот только в некоторых местах ошибки. Одна общая ошибка с определением типа в строке 9 опять же таки,и в строке 28 в функции add_vertex 1 аргумент имеет не верный тип на сколько я понял.

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
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
 
typedef int Xy[2];
 
int cmp_yx(const void *p1, const void *p2)
{
  const *xy1 =(const int *) p1, *xy2 =(const int *) p2;
  int cmp;
 
  if ((cmp = ((*xy1)[1] > (*xy2)[1]) - ((*xy1)[1] < (*xy2)[1]) != 0))
    return cmp;
 
  if ((cmp = ((*xy1)[0] > (*xy2)[0]) - ((*xy1)[0] < (*xy2)[0]) != 0))
    return cmp;
 
  return 0;
}
 
int turn(const *xy1, const *xy2, const *xy3)
{
  Xy v1 = { (*xy2)[0] - (*xy1)[0], (*xy2)[1] - (*xy1)[1] }, v2 = { (*xy3)[0] - (*xy2)[0], (*xy3)[1] - (*xy2)[1] };
  long long area = (long long) v1[0] * v2[1] - (long long) v1[1] * v2[0];
  return (area < 0) - (area > 0);
}
 
unsigned add_vertex( int chain[], unsigned top, const *xy, int bad_turn)
{
  chain[++top] = *xy;
 
  unsigned sub_top = top - 1;
  while (sub_top > 0 && 
         turn(&chain[sub_top - 1], &chain[sub_top], &chain[top]) == bad_turn)
    --sub_top;
 
  chain[++sub_top] = chain[top];
  return sub_top;
}
 
#define N 100u 
 
int main()
{
  Xy poly[N];
  
  for (unsigned i = 0; i < N; ++i)
  {
    poly[i][0] = rand() % 1000;
    poly[i][1] = rand() % 1000;
  }
 
  /* Sort */
 
  qsort(poly, N, sizeof *poly, cmp_yx);
 
  /* Build chains */
 
  Xy left_chain[N], right_chain[N];
  unsigned left_top = -1, right_top = -1;
 
  memcpy(left_chain[++left_top], poly[0], sizeof(Xy));
  memcpy(right_chain[++right_top], poly[0], sizeof(Xy));
 
  for (unsigned i = 1; i < N; ++i)
  {
    left_top = add_vertex(left_chain, left_top, &poly[i], -1);
    right_top = add_vertex(right_chain, right_top, &poly[i], +1);
  }
 
  /* Done */
 
  for (unsigned i = 0; i <= left_top; ++i)
    printf("%d, %d\n", left_chain[i][0], left_chain[i][1]);
  printf("\n");        
  
  for (unsigned i = right_top; i != -1u; --i)
    printf("%d, %d\n", right_chain[i][0], right_chain[i][1]);
  printf("\n");
}

@TheCalligrapher · 15.04.2020, 12:04

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

поменял почти всё правильно

Нет, не правильно. Вы отовсюду зачем-то выкосили упоминание типа Xy. Зачем???

@dendikk · 15.04.2020, 12:11 **[ТС]**

Да,ошибку понял.Я думал оно всё связано с структурой.Забыл что в коде был добавлен массив с названием Ху.
Вот,переделал:

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
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
 
typedef int Xy[2];
 
int cmp_yx(const void *p1, const void *p2)
{
  const Xy *xy1 =(const Xy *) p1, *xy2 =(const Xy *) p2;
  int cmp;
 
  if ((cmp = ((*xy1)[1] > (*xy2)[1]) - ((*xy1)[1] < (*xy2)[1]) != 0))
    return cmp;
 
  if ((cmp = ((*xy1)[0] > (*xy2)[0]) - ((*xy1)[0] < (*xy2)[0]) != 0))
    return cmp;
 
  return 0;
}
 
int turn(const Xy *xy1, const Xy *xy2, const Xy *xy3)
{
  Xy v1 = { (*xy2)[0] - (*xy1)[0], (*xy2)[1] - (*xy1)[1] }, v2 = { (*xy3)[0] - (*xy2)[0], (*xy3)[1] - (*xy2)[1] };
  long long area = (long long) v1[0] * v2[1] - (long long) v1[1] * v2[0];
  return (area < 0) - (area > 0);
}
 
unsigned add_vertex(Xy chain[], unsigned top, const Xy *xy, int bad_turn)
{
  chain[++top] = *xy;
 
  unsigned sub_top = top - 1;
  while (sub_top > 0 && 
         turn(&chain[sub_top - 1], &chain[sub_top], &chain[top]) == bad_turn)
    --sub_top;
 
  chain[++sub_top] = chain[top];
  return sub_top;
}
 
#define N 100u 
 
int main()
{
  Xy poly[N];
  
  for (unsigned i = 0; i < N; ++i)
  {
    poly[i][0] = rand() % 1000;
    poly[i][1] = rand() % 1000;
  }
 
  /* Sort */
 
  qsort(poly, N, sizeof *poly, cmp_yx);
 
  /* Build chains */
 
  Xy left_chain[N], right_chain[N];
  unsigned left_top = -1, right_top = -1;
 
  memcpy(left_chain[++left_top], poly[0], sizeof(Xy));
  memcpy(right_chain[++right_top], poly[0], sizeof(Xy));
 
  for (unsigned i = 1; i < N; ++i)
  {
    left_top = add_vertex(left_chain, left_top, &poly[i], -1);
    right_top = add_vertex(right_chain, right_top, &poly[i], +1);
  }
 
  /* Done */
 
  for (unsigned i = 0; i <= left_top; ++i)
    printf("%d, %d\n", left_chain[i][0], left_chain[i][1]);
  printf("\n");        
  
  for (unsigned i = right_top; i != -1u; --i)
    printf("%d, %d\n", right_chain[i][0], right_chain[i][1]);
  printf("\n");
}

Только выбивает ошибку в 37 рядке: invalid array assignment
И в 30 тоже такая же ошибка.

@TheCalligrapher · 15.04.2020, 12:21

Я же вам уже сказал, что присваивание массивов не будет компилироваться и его нужно везде заменить на memcpy.

@dendikk · 15.04.2020, 12:30 **[ТС]**

Переделал,работает,но точек стало в разы больше. Где то ошибка?

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
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
 
typedef int Xy[2];
 
int cmp_yx(const void *p1, const void *p2)
{
  const Xy *xy1 =(const Xy *) p1, *xy2 =(const Xy *) p2;
  int cmp;
 
  if ((cmp = ((*xy1)[1] > (*xy2)[1]) - ((*xy1)[1] < (*xy2)[1]) != 0))
    return cmp;
 
  if ((cmp = ((*xy1)[0] > (*xy2)[0]) - ((*xy1)[0] < (*xy2)[0]) != 0))
    return cmp;
 
  return 0;
}
 
int turn(const Xy *xy1, const Xy *xy2, const Xy *xy3)
{
  Xy v1 = { (*xy2)[0] - (*xy1)[0], (*xy2)[1] - (*xy1)[1] }, v2 = { (*xy3)[0] - (*xy2)[0], (*xy3)[1] - (*xy2)[1] };
  long long area = (long long) v1[0] * v2[1] - (long long) v1[1] * v2[0];
  return (area < 0) - (area > 0);
}
 
unsigned add_vertex(Xy chain[], unsigned top, const Xy *xy, int bad_turn)
{
  memcpy(chain[++top], *xy, sizeof(Xy));
 
 
 
  unsigned sub_top = top - 1;
  while (sub_top > 0 && 
         turn(&chain[sub_top - 1], &chain[sub_top], &chain[top]) == bad_turn)
    --sub_top;
    
  memcpy(chain[++sub_top], chain[top], sizeof(Xy));
  
  return sub_top;
}
 
#define N 100u 
 
int main()
{
  Xy poly[N];
  
  for (unsigned i = 0; i < N; ++i)
  {
    poly[i][0] = rand() % 100;
    poly[i][1] = rand() % 100;
  }
 
  /* Sort */
 
  qsort(poly, N, sizeof *poly, cmp_yx);
 
  /* Build chains */
 
  Xy left_chain[N], right_chain[N];
  unsigned left_top = -1, right_top = -1;
 
  memcpy(left_chain[++left_top], poly[0], sizeof(Xy));
  memcpy(right_chain[++right_top], poly[0], sizeof(Xy));
 
  for (unsigned i = 1; i < N; ++i)
  {
    left_top = add_vertex(left_chain, left_top, &poly[i], -1);
    right_top = add_vertex(right_chain, right_top, &poly[i], +1);
  }
 
  /* Done */
 
  for (unsigned i = 0; i <= left_top; ++i)
    printf("%d, %d\n", left_chain[i][0], left_chain[i][1]);
  printf("\n");        
  
  for (unsigned i = right_top; i != -1u; --i)
    printf("%d, %d\n", right_chain[i][0], right_chain[i][1]);
  printf("\n");
}

@TheCalligrapher · 15.04.2020, 12:58

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

Где то ошибка?

qsort непраивльно сортирует из-за того, что вы сломали cmp_yx. У вас теперь неправильно расставлены скобки в

C
1
2
3
4
5
  if ((cmp = ((*xy1)[1] > (*xy2)[1]) - ((*xy1)[1] < (*xy2)[1]) != 0))
    return cmp;
 
  if ((cmp = ((*xy1)[0] > (*xy2)[0]) - ((*xy1)[0] < (*xy2)[0]) != 0))
    return cmp;

Запишите лучше отдельно, чтобы меньше потенциала для путаницы было:

C
1
2
3
4
5
6
7
  cmp = ((*xy1)[1] > (*xy2)[1]) - ((*xy1)[1] < (*xy2)[1]);
  if (cmp != 0)
    return cmp;
 
  cmp = ((*xy1)[0] > (*xy2)[0]) - ((*xy1)[0] < (*xy2)[0]);
  if (cmp != 0)
    return cmp;

@dendikk · 15.04.2020, 13:08 **[ТС]**

Спасибо вам ещё раз,всё работает.

@alexu_007 · 21.06.2020, 17:32

В функции int cmp_yx(const void *p1, const void *p2)

D:\prog_Qt_4.7\_uchebnye\Geometry\Triang le_in_kvadr\triangle_in_kvad\widget.cpp: 47: ошибка: invalid conversion from 'const void*' to 'const Xy*'

Пошарил в сети, там функция qsort так же вызывается без аргументов, а в реализации функции стоят void. Но у меня ругается. Что ей не так?

@TheCalligrapher · 21.06.2020, 21:15

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

Но у меня ругается. Что ей не так?

В сообщении #5 уже дан ответ на этот вопрос.

D:\prog_Qt_4.7\_uchebnye\Geometry\Triang le_in_kvadr\triangle _in_kvad\widget.cpp???

@alexu_007 · 21.06.2020, 23:11

То есть в Qt qsort работать не будет?

Новые блоги и статьи Все статьи Все блоги /
Часы электронные Uhbif79 12.08.2026 Выкладываю программу часов. Программа позволяет: 1. Использовать системное время и дату, 2. Есть возможность вводить время и дату вручную. 3. Реализованы 2 будильника: начало и конец рабочего дня. . . .	Часы с будильником на основе класса QLCDNumber Uhbif79 12.08.2026 Всем добрый день, выкладываю программу часов с будильником на основе класса QLCDNumber. Здесь я пробовал самостоятельно создавал классы, впервые столкнулся с видимостью переменной одного класса из. . .	Установка MinGW GCC 16.2 и CMake 8Observer8 10.08.2026 VK Видео: https:/ / vkvideo. ru/ video-240781534_456239017 YouTube: eY5-5PyI9NM Текстовая версия	Неделя из жизни имитационной модели склада: мои кривые руки растут, откуда надо anaschu 10.08.2026 Неделя из жизни имитационной модели склада: как я почти написал неправильную логику и что с этим делать Работаю сейчас над учебно-рабочим проектом: строю в AnyLogic имитационную модель процессов. . .
Калькулятор для расчета родства russiannick 07.08.2026 1. Задача: Создать калькулятор для расчета родства. Родственных связей существует 8 ступеней, такие как: p - отец P - мать q - муж Q - жена b - брат B - сестра s - сын S - дочь	Мир по моей воле kumehtar 07.08.2026 Когда-то кажется, что всё просто. Ты весь такой светлый. Причиняешь добро. Борешься за справедливость в этом тёмном мире. Потом начинаешь замечать одну неприятную вещь. Почти каждый хороший. . .	Кредитный калькулятор Maks 05.08.2026 Решение задачи по прикладной информатике средствами 1С. Задача: Напишите приложение-калькулятор, которое помогает рассчитывать параметры кредита для аннуитетного и дифференцированного видов. . .	У нас сейчас поговорку "Опять 25" нужно переделать на "Опять +35". kumehtar 04.08.2026 С ностальгией вспоминаю времена моего детства, когда у нас и правда +25 - была максимальная температура летом. Раньше +25 °C реально казались вершиной жары, когда можно было весь день пропадать на. . .

@dendikk 0 / 0 / 0 Регистрация: 16.02.2020 Сообщений: 93

	Найти выпуклую оболочку заданного множества точек на плоскости 08.04.2020, 19:56. Показов 10905. Ответов 41 Метки геометрическое моделирование, множество, точки на плоскости (Все метки) Здравствуйте! Помогите решить задачу: Задано множество точек на плоскости. Найти выпуклую оболочку этого множества, то есть выпуклый многоугольник с вершинами в некоторых точках этого множества, который охватывает все его точки. С множеством столкнулся впервые,пытался понять что-то из интернета-пока что не очень понятно 0

@dendikk 0 / 0 / 0 Регистрация: 16.02.2020 Сообщений: 93
	10.04.2020, 21:12 [ТС]
	Вот Миниатюры 0

@dendikk 0 / 0 / 0 Регистрация: 16.02.2020 Сообщений: 93
	10.04.2020, 21:49 [ТС]
	Да,в портабельной версии заработало. А что именно делает второй код? Просто я вижу в коде заданные точки вами,и они в другой последовательности выводятся. Я думал,что задача состоит в том,что задано много точек на площади и нужно обвести их по крайним точкам и таким образом образуется многоугольник. 0

@TheCalligrapher Вездепух 13211 / 6844 / 1824 Регистрация: 18.10.2014 Сообщений: 17,316
	11.04.2020, 11:21
	... Для ее корректной работы требуется, чтобы во входном массиве не было одинаковых точек. В коде выше это не проверяется, т.е. предполагается что и так "повезет". 0

@dendikk 0 / 0 / 0 Регистрация: 16.02.2020 Сообщений: 93
	11.04.2020, 13:00 [ТС]
	Понял,спасибо за помощь! 0

@dendikk 0 / 0 / 0 Регистрация: 16.02.2020 Сообщений: 93
	15.04.2020, 11:00 [ТС]
	TheCalligrapher, вопрос,а возможно ли написать этот код без структур? Оказывается нам еще структуры в коде использовать нельзя. 0

@TheCalligrapher Вездепух 13211 / 6844 / 1824 Регистрация: 18.10.2014 Сообщений: 17,316
	15.04.2020, 12:21
	Я же вам уже сказал, что присваивание массивов не будет компилироваться и его нужно везде заменить на `memcpy`. 1

@dendikk 0 / 0 / 0 Регистрация: 16.02.2020 Сообщений: 93
	15.04.2020, 13:08 [ТС]
	Спасибо вам ещё раз,всё работает. 0

@alexu_007 737 / 704 / 110 Регистрация: 29.05.2015 Сообщений: 4,331
	21.06.2020, 17:32
	В функции int cmp_yx(const void p1, const void p2) D:\prog_Qt_4.7\_uchebnye\Geometry\Triang le_in_kvadr\triangle_in_kvad\widget.cpp: 47: ошибка: invalid conversion from 'const void' to 'const Xy' Пошарил в сети, там функция qsort так же вызывается без аргументов, а в реализации функции стоят void. Но у меня ругается. Что ей не так? 0

@alexu_007 737 / 704 / 110 Регистрация: 29.05.2015 Сообщений: 4,331
	21.06.2020, 23:11
	То есть в Qt qsort работать не будет? 0

Найти выпуклую оболочку заданного множества точек на плоскости

Решение