Форум программистов, компьютерный форум, киберфорум
C для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/3: Рейтинг темы: голосов - 3, средняя оценка - 4.67
3 / 3 / 5
Регистрация: 07.12.2013
Сообщений: 189
1

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

23.04.2016, 11:31. Показов 523. Ответов 1
Метки нет (Все метки)

Всем привет. Задача - найти выпуклую оболочку множества (крайние точки множества, образующие выпуклый многоугольник - я решил делать через gift wrapping).
Суть:
Находим нижнюю точку, потом ищем точку, с которой (и с осью x) она образует наименьший угол, эту точку мы записываем в переменную point_now и повторяем поиск минимального угла, так пока следующей точкой не станет . Но что-то пошло не так. Я не понимаю, почему оно не работает(даже не дописаная).
Заранее спасибо.

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
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
#include <time.h>
#include <math.h>
int main()
{
    int masX[50], masY[50], i, j;
    srand(time(NULL)); 
    for (i=0; i<6; i++)
    {
        masX[i]=rand()%10;
        masY[i]=rand()%10;
        printf("(%d; %d)\n", masX[i], masY[i]);
    }
    int lowest,id_lowest;
    lowest=*masY;
    for (i=0; i<6; i++)
    if(masY[i]<lowest) 
    {
    lowest=masY[i];
     id_lowest=i;
    }
    printf("%d\n", id_lowest);
    double minangle=10, angle;
    int point_nowX = masX[id_lowest],point_nowY=masY[id_lowest], point_testX, point_testY, id_minangle=-1;
    for (j=0; j<6; j++)
    {
        minangle=10;
        if (j!=0)
        {
        point_nowX=masX[id_minangle];
        point_nowY=masY[id_minangle];
        printf("POINT NOW - (%d; %d)\n", point_nowX, point_nowY);
      }
      for (i=0; i<6; i++)
      {
        if (i==id_lowest) continue;
        
        if (i==id_minangle && id_minangle!=-1) continue;
       
          angle=atan((double)abs(masY[i]-point_nowY)/(double)abs(masX[i]-point_nowX));
        
        if (masY[i]==point_nowY && masX[i]>point_nowX) angle=0;
        if (masY[i]==point_nowY && masX[i]<point_nowX) angle=2*1.57;
          printf("%lf= ", angle);
          if (masX[i]<=point_nowX && masY[i]>=point_nowY) angle+=1.57;
        
        else if (masX[i]<=point_nowX && masY[i]<=point_nowY) angle+=2*1.57;
        
          if (masX[i]>point_nowX && masY[i]<point_nowY) angle+=3*1.57;
        
          printf("%lf\n", angle);
        
          if (angle<minangle)
        {
            minangle=angle;
            id_minangle=i;
          }
      }
      printf("minangle = %lf in (%d; %d) with id %d\n", minangle, masX[id_minangle], masY[id_minangle], id_minangle);
    }
}
Добавлено через 21 час 16 минут
up.

Добавлено через 19 часов 24 минуты
И все же, хотя бы в строке 42 формула правильна?
0

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

Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
23.04.2016, 11:31
Ответы с готовыми решениями:

Найти выпуклую оболочку множества
Задано множество N точек. Ai=1..N.Найти выпуклую оболочку этого множества,т.е. те точки,которые...

Заданное множество точек на плоскости. Найти выпуклую оболочку этого множества
Заданное множество точек на плоскости. Найти выпуклую оболочку этого множества, то есть выпуклый...

Дано n точек на плоскости. Построить их выпуклую оболочку - минимальную выпуклую фигуру, их содержащую
Дано n точек на плоскости. Построить их выпуклую оболочку - минимальную выпуклую фигуру, их...

Задано множество точек в трехмерном пространстве, найти выпуклую оболочку наименьшего объема
Задано множество точек в трехмерном пространстве. Найти его выпуклую оболочку, то есть множество...

1
3 / 3 / 5
Регистрация: 07.12.2013
Сообщений: 189
25.04.2016, 18:49  [ТС] 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
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
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
 
int main()
{
    int masX[50], masY[50], i,j;
    
    srand(time(NULL));
    
    for (i=0; i<6; i++)
    {
        masX[i]=rand()%10;
        masY[i]=rand()%10;
        printf("(%d; %d)\n", masX[i], masY[i]); 
    }
    
    int lowest, lowest_id, dop_masX[50], dop_masY[50], id_minangle;
    double minangle, angle;
    
    lowest_id=0;
    
    lowest=masY[0];
    
    for (i=0; i<6; i++)
    if (masY[i]<lowest) 
    {
    lowest = masY[i];
    
    lowest_id=i;
    }
    dop_masX[0]=masX[lowest_id];
    
    dop_masY[0]=masY[lowest_id];
    
    printf("Lowest = %d\n", lowest_id);
    //printf("0 element = (%d;%d)\n", *masX, *masY);
    i=0;
    
    minangle=acos(0)-atan(double(abs(masX[i]-masX[lowest_id]))/double(abs(masY[i]-masY[lowest_id]))); //определяется арккотангенс, т.к с арктангенсом были проблемы, работает 1 раз, начальное значение
    
    if (masX[i]<=masX[lowest_id]) minangle=3.14-minangle; // если во второй четверти - 2пи - угол, иначе не работает)
    
        if (masY[i]==masY[lowest_id]) masX[i]>masX[lowest_id] ? minangle=0 : minangle=1.57*2; //если совпадает ордината, определяем, справа или слева
    
    printf("Minangle = %lf\n", minangle);
    
    for (j=1; j<6; j++)
    {
        printf("\n\n\n");
        
        minangle=acos(0)-atan(double(abs(masX[j]-masX[lowest_id]))/double(abs(masY[j]-masY[lowest_id]))); //все тоже самое, каждую итерацию расчитываем минимальный угол
        
        if (masX[j]<=masX[lowest_id]) minangle=3.14-minangle;
        
        if (masY[j]==masY[lowest_id]) masX[j]>masX[lowest_id] ? minangle=0 : minangle=1.57*2;
    //  if (j!=1) minange
    for (i=0; i<6; i++)
    {
        
        if (i==lowest_id) continue; //нет смысла проверять низшую точку
        
        if (masX[i]==-1 && masY[i]==-1) continue; //пропуск "удаленных" точек
        
        angle=acos(0)-atan(double(abs(masX[i]-masX[lowest_id]))/double(abs(masY[i]-masY[lowest_id]))); // для сравнения с внешним
        
        printf("%d - %d / %d - %d\n", masX[i], masX[lowest_id], masY[i], masY[lowest_id]); //отладка
        
        if (masX[i]<=masX[lowest_id]) angle=3.14-angle; 
        
        if (masY[i]==masY[lowest_id]) masX[i]>masX[lowest_id] ? angle=0 : angle=1.57*2;
        
        printf("angle[%d] = %lf\n",i, angle);
        
        if (angle<minangle) //минимальный угол 
        {
        
        minangle=angle;
        
        id_minangle=i;
        }
    }
    
    dop_masX[j]=masX[id_minangle];
    //запись в конечный, отсортированый массив
    dop_masY[j]=masY[id_minangle];
    if (j==5) //Маленький костыль - на практике почему-то не записывает последнюю точку, это что бы наверняка :)
    {
        for (int k=0; k<6; k++) 
        {
        if (masX[k]!=-1)
        {
        dop_masX[j]=masX[k];
    
        dop_masY[j]=masY[k];
        }
    
        }
    
    }
    masX[id_minangle]=-1; //велосипед на квадратных колесах, ведь удалить элемент массива нельзя, тогда будем игнорить
    
    masY[id_minangle]=-1;
    
    printf("Min = %lf with id %d\n", minangle, id_minangle);
    
    }
    
    for (i=0; i<6; i++)
    printf("(%d; %d)\n", dop_masX[i], dop_masY[i]);
}
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
25.04.2016, 18:49

Построить выпуклую замкнутую оболочку
Построить выпуклую замкнутую оболочку y=1-x^(4/5)

пжста найдите ошибку в задаче на выпуклую оболочку
Здравствуйте,уже 2 дня не могу найти ошибку в коде,валится на 5 тесте. Задача: Даны точки(их...

Найти линейную оболочку векторов
Найти линейную оболочку векторов - элементов векторного пространства (2,2) - матриц: A=...

Найти проекцию вектора на линейную оболочку
дан вектор x = (14,16,2,5) . Нужно найти проекцию вектора x на L = (a,b) где a = (7,3,1,2) b =...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.