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

@smay · Регистрация: 07.12.2013

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

C

#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 формула правильна?

@smay · 25.04.2016, 18:49 **[ТС]**

Последний раз апаю, может сейчас повезет.
Вот "новый" код. Работает почти. Где ошибка - не понимаю.

C

#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]);
}

Опции темы