gpt4 book ai didi

凸包长度(C)

转载 作者:行者123 更新时间:2023-11-30 19:36:17 25 4
gpt4 key购买 nike

我正在编写一个程序来计算 2D 点的凸包长度。

输入中有许多点n,然后是每个点的坐标。

例如:

6
-8 -3
-6 1
-5 -2
-3 1
-3 4
2 18

输出只是凸包的长度。

到目前为止,我的代码如下所示:

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

typedef struct point
{
double x;
double y;
}POINT,VECTOR;

POINT b[1000];
VECTOR normal;
int n;

int upper_lower(int i, VECTOR ab, double c) {
double x, y,result;
y = b[i].y;
x = normal.x*b[i].x;
result = -(x + c) / normal.y;
if (y>result) return 1;
if (y == result) return 0;
else
return -1;


}

int ccw(VECTOR v,VECTOR v2)
{
double cp;

cp = v2.x*v.y - v2.y*v.x;

if (cp == abs(cp)) return 1;
else
return -1;


}

double vector_length(VECTOR v)
{
return sqrt(pow(v.x, 2) + pow(v.y, 2));

}

int cmp_points(const void *p1, const void *p2)
{
const POINT *pt1 = p1;
const POINT *pt2 = p2;

// do primary compare on x
if (pt1->x > pt2->x)
return 1;
if (pt1->x < pt2->x)
return -1;

// pt1->x == pt2->x - do secondary compare on y...
if (pt1->y > pt2->y)
return 1;
if (pt1->y < pt2->y)
return -1;

// pt1 == pt2
return 0;
}

int main()
{
int i,poloha,upper[1000],lower[1000],h=0,d=0;
scanf("%d", &n);
if (n <= 0 && n > 1000) return 0;
for (i = 0; i < n; i++)
{
scanf("%lf %lf", &b[i].x, &b[i].y);
}
qsort(b, n, sizeof(POINT), cmp_points);

//split in half
VECTOR ab;
double c;
ab.x = b[n - 1].x - b[0].x;
ab.y = b[n - 1].y - b[0].y;
normal.x = -ab.y;
normal.y = ab.x;
c = -normal.x*b[0].x - (normal.y*b[0].y);
for (i = 0; i < n; i++)
{
poloha = upper_lower(i,ab,c);
if (poloha == 1) upper[h++] = i;
if (poloha == -1) lower[d++]=i;
if (poloha == 0)
{
upper[h++] = i;
lower[d++] = i;
}

}
int j = 0;
double v, length = 0;
VECTOR v1, v2, v3,v4;
v3.x = 0; v3.y = 0;
//lower part
for (i = 0; ; i++)
{
int in = 0;
if (lower[i + 2] < 0)
{
v1.x = b[lower[i + 1]].x - b[lower[0]].x;
v1.y = b[lower[i + 1]].y - b[lower[0]].y;

v2.x = b[lower[i]].x - b[lower[i + 1]].x;
v2.y = b[lower[i]].y - b[lower[i + 1]].y;

lenght += vector_length(v1);
length += vector_length(v2);
break;
}
v1.x = b[lower[i + 1]].x - b[lower[i]].x;
v1.y = b[lower[i + 1]].y - b[lower[i]].y;

v2.x = b[lower[i + 2]].x - b[lower[i]].x;
v2.y = b[lower[i + 2]].y - b[lower[i]].y;
in = ccw(v1, v2);
if (in == 1)
{
length += vector_length(v1);
v3 = v2;
v4 = v1;
}
if (in == -1)
{
length -= vector_length(v4);
if (v3.x != 0 && v3.y != 0)
{
length += vector_length(v3);
v3.x = 0; v3.y = 0;
}
else
{
length += vector_length(v2);

}


}
}

printf("%.3lf", length);

return 0;
}

问题是,在我尝试计算长度的最后一部分......我只是不知道如何完成它......无论我尝试什么,它都不会像我想要的那样工作。大家能给我一些建议吗?

最佳答案

我看不到标准答案,所以这是算法:

大致选择点云中心的一个点。然后按与中心的角度径向对点进行排序。最顶端的点必须位于凸包中,因此将其定义为角度为 0.0 且位于列表中的第一个点。

现在就去吧。将点 2 放入“暂定”船体列表中。然后检查点3。如果角度P1-P2-P3是凹角(相对于中心点),则从列表中删除P2,如果是凸角,则保留它。继续这样,回溯并删除凹点。您的“暂定”列表中只需要两点,一旦有了三点,它们就变得确定了。

当你转了一圈并回到 P1 时你就停下来了。

关于凸包长度(C),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/41140905/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com