Chinaunix首页 | 论坛 | 博客
  • 博客访问: 2609681
  • 博文数量: 258
  • 博客积分: 9440
  • 博客等级: 少将
  • 技术积分: 6998
  • 用 户 组: 普通用户
  • 注册时间: 2009-05-03 10:28
个人简介

-- linux爱好者,业余时间热衷于分析linux内核源码 -- 目前主要研究云计算和虚拟化相关的技术,主要包括libvirt/qemu,openstack,opennebula架构和源码分析。 -- 第五届云计算大会演讲嘉宾 微博:@Marshal-Liu

文章分类

全部博文(258)

文章存档

2016年(1)

2015年(4)

2014年(16)

2013年(22)

2012年(41)

2011年(59)

2010年(40)

2009年(75)

分类: C/C++

2012-03-13 21:01:02

  1. 今天突然发现自己csdn的草稿箱中有几篇以前写过的文章,发出来与大家分享!


  2. /*
  3.  * =====================================================================================
  4.  *
  5.  * Filename: FillPolygon.c
  6.  *
  7.  * Description: comments
  8.  *
  9.  * Version: 1.0
  10.  * Created: 08/17/2010 08:43:12 PM
  11.  * Revision: none
  12.  * Compiler: gcc
  13.  *
  14.  * Author: dylan (comments), ustc_dylan@yahoo.cn
  15.  * Company: University of Technology and Science of China
  16.  *
  17.  * =====================================================================================
  18.  */

  19. #include <stdio.h>

  20. typedef struct _Edge
  21. {
  22. int x;
  23. float dx;
  24. int ymax;
  25. struct _Edge *next;
  26. }Edge;

  27. typedef struct _Point
  28. {
  29. int x;
  30. int y;
  31. }Point;

  32. static Edge *edges[480], *active;

  33. void InsertEdge(Edge *list, Edge *edge)
  34. {
  35. Edge *p, *q = list;

  36. p = q->next;

  37. while(p != NULL)
  38. {
  39. if(edge->x < p->x)
  40. p = NULL;
  41. else
  42. {
  43. q = p;
  44. p = p->next;
  45. }
  46. }

  47. edge->next = q->next;
  48. q->next = edge;

  49. }

  50. void MakeEdgeRec(Point lower, Point upper, int yComp, Edge *edge, Edge *edges[])
  51. {
  52. edge->dx = (float)(upper.x - lower.x)/(upper.y - lower.y);
  53. edge->x = lower.x;

  54. if(upper.y < yComp)
  55. edge->ymax = upper.y - 1;
  56. else
  57. edge->ymax = upper.y;

  58. InsertEdge(edges[lower.y],edge);

  59. }

  60. int yNext(int k, int num, Point *pts)
  61. {
  62. int j;
  63. if((k + 1) > (num - 1))
  64. j = 0;
  65. else
  66. j = k + 1;

  67. while(pts[k].y == pts[j].y)
  68. if((j + 1) > (num - 1))
  69. j = 0;
  70. else
  71. ++j;

  72. return (pts[j].y);
  73. }

  74. void BuildEdgeList(Point *pts, int num, Edge *edges[])
  75. {
  76. Edge *edge;

  77. Point v1,v2;
  78. int i, yPrev = pts[num-2].y;
  79. v1.x = pts[num-1].x;
  80. v1.y = pts[num-1].y;
  81.  

  82. for( i = 0; i < num; ++i)
  83. {
  84. v2 = pts[i];
  85. if(v1.y != v2.y)
  86. {
  87. edge = (Edge *)malloc(sizeof(Edge));
  88. edge = (Edge *)malloc(sizeof(Edge));

  89. if(v1.y < v2.y)
  90. MakeEdgeRec(v1,v2,yNext(i,num,pts),edge,edges);
  91. else
  92. MakeEdgeRec(v2,v1,yPrev,edge,edges);

  93. }

  94. yPrev = v1.y;
  95. v1 = v2;

  96. }

  97. }

  98.  

  99. void BuildActiveList(int scan, Edge *active, Edge *edge[])
  100. {

  101. Edge *p, *q;

  102. p = edges[scan]->next;

  103. while(p)
  104. {
  105. q = p->next;
  106. InsertEdge(active, p);
  107. p = q;
  108. }

  109. }

  110.  

  111. void FillScan(int scan, Edge *active)
  112. {
  113. Edge *p1, *p2;

  114. int i;

  115. p1 = active->next;
  116. while(p1)
  117. {
  118. p2 = p1->next;

  119. for( i = p1->x; i < p2->x; ++i)
  120. printf(".");
  121. p1 = p2->next;

  122. }

  123. }

  124.  

  125. void DeleteAfter(Edge *q)
  126. {

  127. Edge *p = q->next;

  128. q->next = p->next;

  129. free(p);

  130. }

  131.  

  132. void UpdateActiveList(int scan, Edge *active)
  133. {

  134. Edge *q=active, *p = active->next;

  135.  

  136. while(p)
  137. {

  138. if(scan >= p->ymax)
  139. {

  140. p = p->next;

  141. DeleteAfter(q);

  142. }
  143. else
  144. {

  145. p->x = p->x + p->dx;

  146. q = p;

  147. p = p->next;
  148. }

  149. }

  150. }

  151.  

  152. void ResortActiveList(Edge *active)
  153. {

  154. Edge *q, *p = active->next;

  155. active->next = NULL;

  156.  

  157. while(p)
  158. {

  159. q = p->next;

  160. InsertEdge(active, p);

  161. p = q;

  162. }

  163. }

  164.  

  165. void ScanLineFillPolygon(Point *pts, int num)
  166. {

  167. int i,scan,scanmax=0,scanmin = 480;

  168.  

  169. /* 扫描线的边界*/

  170. for( i = 0; i < num -1; ++i)
  171. {

  172. if(pts[i].y > scanmax)
  173. scanmax = pts[i].y;
  174. if(pts[i].y < scanmin)
  175. scanmin = pts[i].y;

  176. }

  177.  

  178. /* 初始化边表*/

  179. for( scan = scanmin; scan < scanmax; ++scan )
  180. {

  181. edges[scan] = (Edge *) malloc(sizeof(Edge));

  182. edges[scan]->next = NULL;

  183. }

  184.  

  185. BuildEdgeList(pts,num,edges);

  186.  

  187. active = (Edge *)malloc(sizeof(Edge));

  188. active->next = NULL;

  189. for(scan = scanmin; scan <=scanmax; scan++)
  190. {

  191. BuildActiveList(scan,active,edges);

  192. if(active->next)
  193. {

  194. FillScan(scan,active);

  195. UpdateActiveList(scan,active);

  196. ResortActiveList(active);

  197. }

  198. }

  199.  

  200. }

  201. int main()
  202. {



  203. Point pts[] = {{100,40},{220,140},{280,80},{350,300},

  204.                {200,380},{50,280},{100,40},};

  205.  

  206. int num = sizeof(pts)/sizeof(Point);

  207.  

  208. //initgraph(&gdriver, &gmode, "");

  209. ScanLineFillPolygon(pts,num);

  210. return 0;

  211. }
阅读(6537) | 评论(1) | 转发(2) |
给主人留下些什么吧!~~

lifavor2016-04-26 12:13:34

结构体 Edge 里的 int x; 应该定义为 float 型与 float dx; 对应,不然的更新 aet 表的 p->x = p->x + p->dx; 时会产生累计误差, 另 279行for循环的等号导致 边表NET 最后一次  p = edges[scan]->next;崩,  也即指针不判空直接取next不是好的编程风格