qq_37108068 2016-12-20 04:08 采纳率: 0%
浏览 904
已结题

19号晚上九点十三分提的那个凸包问题

请大神帮忙把代码补充完整,不要网站上已有的。。请将答案回复到两个提问下,总共一百五c币
#include
#include

// 通过结构体定义"点"类型
struct Point
{ double x, y; };

// 定义"向量"类型
// 实质上和上面的"点"是同一类型
// 在需要使用向量时,可以选择 Vector 这个名字
typedef Point Vector;

/////////////////////////////////////////////

// 输出一个点的坐标
void prtpoint( Point p )
{
printf("( %.2f, %.2f )\n", p.x, p.y );
}

// 判断给定的两个点是否是同一个点
// 是则返回true ,否则返回false
// 在比较两个点时,可以使用运算符 ==
bool operator==( Point p1, Point p2 )
{
if( fabs(p1.x-p2.x)<1e-9 && fabs(p1.y-p2.y)<1e-9 )
return true;
else
return false;
}

// 计算一个向量的模
double module( Vector v )
{
return sqrt( v.x*v.x + v.y*v.y );
}

// 计算两个向量夹角的余弦值
double cosab( Vector a, Vector b )
{
return ( a.x*b.x + a.y*b.y ) / module(a) / module(b);
}

/////////////////////////////////////////////////////////////////////////////////////
int main( )
{
// 陷井坐标,可以将其它测试数据直接放入数组中
Point trap[] = { { 0, 0 },{ 1, 1 },{ 3.1, 1.3 },{ 3, 4.5 },{ 6, 2.1 },{ 2, -3.2 } };

// 记录选作边界的点
Point perimeter[100]; 

// 陷井的个数和边界点的个数
int trapnum, perinum;

// 定义两个向量 va  vb;
Vector va, vb;

int i, k;
double maxcos;//最大余弦值

// 计算trap数组中元素的个数
trapnum = sizeof(trap) / sizeof(Point);
// 选作边界的点的个数,开始为0
perinum = 0;

// 通过比较横坐标,寻找最左边的一点
// k 记录其在trap中的下标
k = 0;  // 先假设trap[0]是最左边的点
        // 如果有更靠左的点,则修改k的值
///////////////////////////////////////////
// 此处需要补充代码,确定最左边的点




///////////////////////////////////////////

perimeter[0] = trap[k]; // trap[k]作为边界的第一个点,存放在perimeter[0]中
perinum++;              // 记数

// 向量va的初始值可以赋值为y轴的单位向量
va.x = 0;   va.y = 1;

// 寻找其它点
while( 1 )
{
    // 先给maxcos一个最小的值,当有更大值出现时,对其进行修改
    maxcos = -1;    // cos(90)

    // 在所有的点中寻找下一个点
    for(i = 0;i < trapnum;i++ )
    {
        // 计算前一个边界点 perimeter[perinum-1] 与 trap[i]构成的向量 vb

        ///////////////////////////////////////////
        // 此处需要补充代码




        ///////////////////////////////////////////
        // 计算两个向量va vb的夹角余弦,然后和maxcos比较
        // 如果比maxcos大,说明夹角更小,可以作为一个候选点
        // 用k记录这个点在trap中的下标
        ///////////////////////////////////////////
        // 此处需要补充代码




        ///////////////////////////////////////////

    }

    // trap[k]被选中,判断它是否是边界的第一个点
    // 如果是说明构成一个多边形,寻找过程结束
    if(  trap[k] == perimeter[0]  )
        break;

    // 如果是一个新出现的点,把它放入边界中
    perimeter[perinum] = trap[k];
    perinum++;
    // vb成为新的 va
    va.x = vb.x;
    va.y = vb.y;
}
// 

// 输出作为边界的点的坐标
for(i = 0; i < perinum;i++)
    prtpoint(perimeter[i]);
prtpoint(perimeter[0]);


return 0;

}

  • 写回答

2条回答 默认 最新

  • 鱼弦 全栈领域优质创作者 2016-12-20 04:19
    关注

    需求不是很清楚?能不能贴一下之前的问题链接?

    评论

报告相同问题?

悬赏问题

  • ¥15 drone 推送镜像时候 purge: true 推送完毕后没有删除对应的镜像,手动拷贝到服务器执行结果正确在样才能让指令自动执行成功删除对应镜像,如何解决?
  • ¥15 求daily translation(DT)偏差订正方法的代码
  • ¥15 js调用html页面需要隐藏某个按钮
  • ¥15 ads仿真结果在圆图上是怎么读数的
  • ¥20 Cotex M3的调试和程序执行方式是什么样的?
  • ¥20 java项目连接sqlserver时报ssl相关错误
  • ¥15 一道python难题3
  • ¥15 牛顿斯科特系数表表示
  • ¥15 arduino 步进电机
  • ¥20 程序进入HardFault_Handler