四边形填充
程序员文章站
2022-04-01 18:42:22
...
四边形填充算,除了比较笨的洪流法外,就是扫描线法了
基本算法是:
(1) 求交,计算扫描线与多边形的交点
(2) 交点排序,对第2步得到的交点按照x值从小到大进行排序;
(3) 颜色填充,对排序后的交点两两组成一个水平线段,以画线段的方式进行颜色填充;
(4) 是否完成多边形扫描?如果是就结束算法,如果不是就改变扫描线,然后转第1步继续处理;
这里有详细的介绍:
多边形区域填充算法--扫描线填充算法(有序边表法)https://blog.csdn.net/dirtyman_/article/details/79878903
对于四边形填充,这里基于扫描线算法,进一步优化,去掉了有序表。
主要优化方法,是对算法第一步[计算扫描线与多边形的交点], 根据上下两条扫描线的相关性,使用上一条扫描线的起始点x和线段的斜率计算下一条扫描线的起始点。
伪代码如下:
void fillArea(olm::Pointf(&points)[4], uint8_t* map, int width, int height, int col,MsImage* binmap){
struct _Line{
float k;
float ymax;
float x;
};
_Line lines[4];
// 找一个y最小的点,及最小的y和最大的y
float ymin = points[0].y_;
float ymax = points[0].y_;
int mid = 0;
for(int i=0;i<4;i++){
if(points[i].y_<ymin){
ymin = points[i].y_;
mid = i;
}
if(points[i].y_>ymax){
ymax = points[i].y_;
}
}
printf("top point mid: %d\n", mid);
// 以此点为线段起点,顺时针为4条边命名
for (int i = 0; i < 4; i++) {
int id0 = (mid + i) % 4;
int id1 = (mid + i + 1) % 4;
lines[id0].k = (points[id0].y_ - points[id1].y_) / -(points[id0].x_ - points[id1].x_);
lines[id0].ymax = std::max(points[id0].y_, points[id1].y_);
lines[id0].x = points[id0].x_;
printf("xxx (%d,%d) 1/k:%.3f, ymax: %f \n", id0, id1, lines[id0].k, lines[id0].ymax);
}
int l0 = (mid+3)%4;
int l1 = mid;
printf("xxx l0: %d, l1: %d \n", l0,l1);
float x0 ,x1;
//初始起始点为最顶的点
int y = points[mid].y_;
x0 = x1 = points[mid].x_;
printf("xxx y: %d, x: %.3f, %.3f \n",y, x0, x1);
getchar();
for(;y<ymax+0.5;y++){
// h 条扫描线
//计算水平线 y=y'与四边形的交点(1,或两个交点)
int sx = std::min(x0,x1)+0.5;
int ex = std::max(x0,x1)+0.5;
for(int x = sx;x<ex;x++){
map[x+y*width] = col;
}
if(y>=ymax){
break;
}
//下一条扫描线,如果换到了另一条边上,更新边索引(为了更新斜率倒数)
if((y+1)>lines[l0].ymax){
l0--;
l0=(l0+4)%4;
}
if((y+1)>lines[l1].ymax){
l1++;
l1=(l1+4)%4;
x1 = lines[l1].x;
}
x0 -= 1/lines[l0].k;
x1 -= 1/lines[l1].k;
printf("xxx l:%d,%d x: %.3f, %.3f \n",l0,l1,x0, x1);
// MsEncodeFile(binmap, "bin.pgm", 85);
// getchar();
}
}
上一篇: DP(优化专题-四边形不等式优化一)
推荐阅读
-
CorelDRAW网状填充工具绘制花朵
-
Coreldraw x5怎么绘制表格并填充颜色?
-
通过T_sql语句向其中一次填入一条数据或一次填入多条数据的方式填充数据
-
如何使用CorelDRAW为对象填充图案 图案填充的操作方法和应用技巧介绍
-
SQL Server误区30日谈 第25天 有关填充因子的误区
-
Coreldraw x5怎么绘制表格并填充颜色?
-
根据灰度值填充字符-单文件单线程版
-
基于Android中的 AutoCompleteTextView实现自动填充
-
AE怎么给文字填充图案? ae使用Alpha遮罩制作艺术字的教程
-
html5 Canvas画图教程(4)—未闭合的路径及渐变色的填充方法