Question

c语言 给出任意多边形顶点,这些定点连起来是一个凸多边形，如何对它进行填充？希望有源程序。

我的目的是对二值图片进行处理，使多边形内部像素值全为255。如果你们有求出二值图像的凸包并对其填充的代码就更好了。没有的话，就给我一个已知多边形定点坐标，对多边形进行填充的程序吧，大谢！

Answer 1

// 点
struct point
{

float x,y; //x y 坐标
};

// 多边形结构体
struct polygon
{

int num; // 点的数目

float offset_x,offset_y; // 偏移

float left,right,top,bottom; // 多边形 上/下/左/右区域

struct point *points; //组成多边形的点
};

// 生成多变形
// 点必须是有序的，按多边形的顶点顺时针给出
// p 组成多边形的点
// size 点的数量
int gen_polygon_clockwise(const struct point* p,int size,struct polygon *poly)
{

int i ;

struct point *p_adr = (point *)malloc(sizeof(struct point) * size);

poly->num = size;

for (i = 0;i < size;i++) {

p_adr[i].x = p[i].x;

p_adr[i].y = p[i].y;

if (i == 0) {

poly->left = p[i].x;

poly->right = p[i].x;

poly->bottom = p[i].y;

poly->top = p[i].y;

} else {
// 确定区域的上/下/左/右 坐标

if (p[i].x < poly->left) {

poly->left = p[i].x;

}

if (p[i].x > poly->right) {

poly->right = p[i].x;

}

if (p[i].y < poly->top) {

poly->top = p[i].y;

}

if (p[i].y > poly->bottom) {

poly->bottom = p[i].y;

}

}

}

poly->points = p_adr;

return 0 ;
}

void free_polygon(struct polygon *poly)
{

free(poly->points);
}

// 点是顺时针给出的
// 判断点是否在直线的左/右区域
// 判断一个点是否在一个区域里，主要是根据该点和组成多边形的直线的关系来判断
int is_point_local_line_region_clockwise(float x1,float x2,float y1,float y2,float x,float y)
{

float w,h,tmp;

// 下面的代码，就不解释了，你【顺时针】画一个多边行，然后在任意画一个点，然后
// 判断组成多边形的每条直线和点的关系就清楚了,主要还是根据该点是在直线的左侧还是
// 右侧(上侧/下侧)来判断一个点是否在多边行的里面
//
// 直线倾率为无穷大

if (x1 == x2) {

if (y1 > y2) {

if (x < x1) {

return 0;

}

} else {

if (x > x1) {

return 0 ;

}

}

}

// 直线倾率为0

if (y1 == y2) {

if (x1 > x2) {

if (y > y1) {

return 0;

}

} else {

if (y < y1) {

return 0;

}

}

}

w = x2 - x1;

h = y2 - y1;

// 直线上的点
// 直线的倾率 直线的点倾式(y = k(x - x1) + y1)

tmp = h/w * (x -x1) + y1;

if (x1 > x2) {

if (y > tmp) {

return 0;

}

} else {

if (y < tmp) {

return 0;

}

}

return 1;
}

// 判断一个点是否在多边行里面
// 在多边形区域里则返回非0值，否则，返回0值
int is_point_in_polygon(float x,float y,const struct polygon *poly)
{

int i ;

if (x < poly->left || x > poly->right ||

y < poly->top || y > poly->right) {

return 0;

}

for (i = 0; i < poly->num - 1;i++) {

if (!is_point_local_line_region_clockwise(poly->points[i].x,

poly->points[i + 1].x,

poly->points[i].y,

poly->points[i + 1].y,x,y)) {

return 0 ;

}

}

if (!is_point_local_line_region_clockwise(poly->points[i].x,

poly->points[0].x,

poly->points[i].y,

poly->points[0].y,

x,y)) {

return 0 ;

}

return 1;
}

#define RESOLUTION_X 100

// 填充多边形
// buffer 填充的二维数组
void fill_poly(const struct polygon *poly,char buffer[][RESOLUTION_X])
{

int x,y,w,h,i,j;

x = (int)poly->left + poly->offset_x;

y = (int)poly->top + poly->offset_y;

w = (int)(poly->right - poly->left);

h = (int)(poly->bottom - poly->top);

for (i = y;i < y + h;i++) {

for (j = x;j < x + w;j++) {

if (is_point_in_polygon(j,i,poly)) {

buffer[i][j] = 255;

}

}

}
}

int main()
{

char buffer[100][100];

struct polygon poly;

struct point points[8];

poly.offset_x = 0;

poly.offset_y = 0 ;

points[0].x = 50;

points[0].y = 50 - 30;

points[1].x = 50 + 21;

points[1].y = 50 - 21;

points[2].x = 50 + 30;

points[2].y = 50;

points[3].x = 50 + 21;

points[3].y = 50 + 21;

points[4].x = 50;

points[4].y = 50 + 30;

points[5].x = 50 - 21;

points[5].y = 50 + 21;

points[6].x = 50 - 30;

points[6].y = 50 ;

points[7].x = 50 - 21;

points[7].y = 50 - 21;

memset(buffer,0,sizeof(buffer));

gen_polygon_clockwise(points,8,&poly);

fill_poly(&poly,buffer);

for (int i = 0;i < 100;i++) {

for (int j = 0;j < 100;j++) {

if (buffer[i][j]) {

std::cout << "*";

} else {

std::cout << " " ;

}

}

std::cout << std::endl;

}

return 0;
}

####
你看对你有没有帮助
浮点坐标到整数坐标只是简单的类型转换