多边形有效边表填充算法

  • v1_329904
    了解作者
  • 27.4KB
    文件大小
  • zip
    文件格式
  • 0
    收藏次数
  • VIP专享
    资源类型
  • 0
    下载次数
  • 2022-06-14 09:42
    上传日期
多边形的有效边表填充算法,程序可运行,供计算机图形学学习者参考。
多边形有效边表填充算法.zip
  • 10110408_2
  • stdafx.cpp
    215B
  • small.ico
    23KB
  • Resource.h
    1.9KB
  • 10110408_2.ico
    23KB
  • stdafx.h
    420B
  • 10110408_2.vcxproj.filters
    1.8KB
  • 10110408_2.vcxproj.user
    143B
  • 10110408_2.h
    37B
  • targetver.h
    236B
  • 10110408_2.aps
    51KB
  • 10110408_2.cpp
    10.9KB
  • 10110408_2.vcxproj
    4.5KB
  • 10110408_2.rc
    7.4KB
  • 10110408_2.sln
    897B
内容介绍
// 10110408_2.cpp : 定义应用程序的入口点。 #include "stdafx.h" #include "10110408_2.h" #define MAX_LOADSTRING 100 // 全局变量: HINSTANCE hInst; // 当前实例 TCHAR szTitle[MAX_LOADSTRING]; // 标题栏文本 TCHAR szWindowClass[MAX_LOADSTRING]; // 主窗口类名 // 此代码模块中包含的函数的前向声明: ATOM MyRegisterClass(HINSTANCE hInstance); BOOL InitInstance(HINSTANCE, int); LRESULT CALLBACK WndProc(HWND, UINT, WPARAM, LPARAM); INT_PTR CALLBACK About(HWND, UINT, WPARAM, LPARAM); int APIENTRY _tWinMain(HINSTANCE hInstance, HINSTANCE hPrevInstance, LPTSTR lpCmdLine, int nCmdShow) { UNREFERENCED_PARAMETER(hPrevInstance); UNREFERENCED_PARAMETER(lpCmdLine); // TODO: 在此放置代码。 MSG msg; HACCEL hAccelTable; // 初始化全局字符串 LoadString(hInstance, IDS_APP_TITLE, szTitle, MAX_LOADSTRING); LoadString(hInstance, IDC_MY10110408_2, szWindowClass, MAX_LOADSTRING); MyRegisterClass(hInstance); // 执行应用程序初始化: if (!InitInstance (hInstance, nCmdShow)) { return FALSE; } hAccelTable = LoadAccelerators(hInstance, MAKEINTRESOURCE(IDC_MY10110408_2)); // 主消息循环: while (GetMessage(&msg, NULL, 0, 0)) { if (!TranslateAccelerator(msg.hwnd, hAccelTable, &msg)) { TranslateMessage(&msg); DispatchMessage(&msg); } } return (int) msg.wParam; } // 函数: MyRegisterClass() // // 目的: 注册窗口类。 // // 注释: // // 仅当希望 // 此代码与添加到 Windows 95 中的“RegisterClassEx” // 函数之前的 Win32 系统兼容时,才需要此函数及其用法。调用此函数十分重要, // 这样应用程序就可以获得关联的 // “格式正确的”小图标。 // ATOM MyRegisterClass(HINSTANCE hInstance) { WNDCLASSEX wcex; wcex.cbSize = sizeof(WNDCLASSEX); wcex.style = CS_HREDRAW | CS_VREDRAW; wcex.lpfnWndProc = WndProc; wcex.cbClsExtra = 0; wcex.cbWndExtra = 0; wcex.hInstance = hInstance; wcex.hIcon = LoadIcon(hInstance, MAKEINTRESOURCE(IDI_MY10110408_2)); wcex.hCursor = LoadCursor(NULL, IDC_ARROW); wcex.hbrBackground = (HBRUSH)(COLOR_WINDOW+1); wcex.lpszMenuName = MAKEINTRESOURCE(IDC_MY10110408_2); wcex.lpszClassName = szWindowClass; wcex.hIconSm = LoadIcon(wcex.hInstance, MAKEINTRESOURCE(IDI_SMALL)); return RegisterClassEx(&wcex); } // // 函数: InitInstance(HINSTANCE, int) // // 目的: 保存实例句柄并创建主窗口 // // 注释: // // 在此函数中,我们在全局变量中保存实例句柄并 // 创建和显示主程序窗口。 // BOOL InitInstance(HINSTANCE hInstance, int nCmdShow) { HWND hWnd; hInst = hInstance; // 将实例句柄存储在全局变量中 hWnd = CreateWindow(szWindowClass, szTitle, WS_OVERLAPPEDWINDOW, CW_USEDEFAULT, 0, CW_USEDEFAULT, 0, NULL, NULL, hInstance, NULL); if (!hWnd) { return FALSE; } ShowWindow(hWnd, nCmdShow); UpdateWindow(hWnd); return TRUE; } // // 函数: WndProc(HWND, UINT, WPARAM, LPARAM) // // 目的: 处理主窗口的消息。 // // WM_COMMAND - 处理应用程序菜单 // WM_PAINT - 绘制主窗口 // WM_DESTROY - 发送退出消息并返回 typedef struct AET //构造边表数据结构 { double x; long ymax; double k; //代替1/k struct AET *next; }AET; typedef struct Bucket//构造桶结点的数据结构 { int BucketL; struct Bucket *next; AET *p; }Bucket; int sides=7; Bucket *HeadB,*CurrentB; AET E[7],*HeadE,*CurrentE,*T1,*T2; POINT spt[7]; void Polygon(HDC hdc) { spt[0].x=150;spt[0].y=50;//定义多边形 spt[1].x=300;spt[1].y=250; spt[2].x=400;spt[2].y=50 ; spt[3].x=600;spt[3].y=450; spt[4].x=350;spt[4].y=400; spt[5].x=150;spt[5].y=600; spt[6].x=50;spt[6].y=350; ::Polygon(hdc,spt,sides); } Bucket* CreatBucket()//初始化桶 { int max,min; max=min=spt[0].y; // 求出最大的y值和最小的y值,即占用的最大扫描线数 for (int i=1; i< sides; i++) { if (spt[i].y > max) max = spt[i].y; else if (spt[i].y < min) min = spt[i].y; } for(int i=min;i<=max;i++)//建立桶结点 { if(min==i)//桶头结点 { HeadB=new Bucket;//建立桶的头结点 CurrentB=HeadB;//CurrentB为Bucket当前结点指针 CurrentB->BucketL=min; CurrentB->p=NULL;//没有连接边链表 CurrentB->next=NULL; } else//建立桶的其它结点 { CurrentB->next=new Bucket;//新建一个桶结点 CurrentB=CurrentB->next;//使CurrentB指向新建的桶结点 CurrentB->BucketL=i; CurrentB->p=NULL;//没有连接边链表 CurrentB->next=NULL; } } return HeadB; } Bucket *CreatET()//构造边表 { for(int i=0;i<sides;i++)//访问每个顶点 { int j=i+1;//边的第二个顶点,spt[i]和spt[j]构成边 if(j==sides) j=0;//保证多边形的闭合 CurrentB=HeadB;//从桶链表的头结点开始循环 if(spt[j].y>spt[i].y)//终点比起点高 { while(CurrentB->BucketL!=spt[i].y)//在桶内寻找该边的ymin { CurrentB=CurrentB->next;//移到下一个桶结点 } E[i].x=spt[i].x;//计算ET表的值 E[i].ymax=spt[j].y; E[i].k=double((spt[j].x-spt[i].x))/(spt[j].y-spt[i].y);//代表1/k E[i].next=NULL; CurrentE=CurrentB->p;//获得桶上链接边表的地址 if(CurrentB->p==NULL)//当前桶结点上没有链接边结点 { CurrentE=&E[i];//赋边的起始地址 CurrentB->p=CurrentE;//第一个边结点直接连接到对应的桶中 } else { while(CurrentE->next!=NULL)//如果当前边已连有边结点 { CurrentE=CurrentE->next;//移动指针到当前边的最后一个边结点 } CurrentE->next=&E[i];//把当前边接上去 } } if(spt[j].y<spt[i].y)//终点比起点低 { while(CurrentB->BucketL!=spt[j].y) { CurrentB=CurrentB->next; } E[i].x=spt[j].x; E[i].ymax=spt[i].y; E[i].k=double((spt[i].x-spt[j].x))/(spt[i].y-spt[j].y); E[i].next=NULL; CurrentE=CurrentB->p; if(CurrentE==NULL)//当前桶结点上没有链接边结点 { CurrentE=&E[i]; CurrentB->p=CurrentE;//第一个边结点直接链接到对应的桶中 } else //如果当前边已连有边结点 { while(CurrentE->next!=NULL) { CurrentE=CurrentE->next; } CurrentE->next=&E[i]; } } } CurrentB=NULL; CurrentE=NULL; return HeadB; } void AddEdge(AET *NewEdge)//插入临时边表 { T1=HeadE; if(T1==NULL)//边表为空,将边表置为TempEdge { T1=NewEdge; HeadE=T1; } else { while(T1->next!=NULL)//边表不为空,将TempEdge连在该边之后 { T1=T1->next; } T1->next=NewEdge; } } void EdgeOrder()//对边表进行排序 { T1=HeadE; if(T1==NULL) { return; } if(T1->next==NULL)//如果该边表没有再连边表 { return;//桶结点只有一条边,不需要排序 } else { if(T1->next->x<T1->x)//边表按x值排序 { T2=T1->next; T1->next=T2->next; T2->next=T1; HeadE=T2; } T2=HeadE; T1=HeadE->next; while(T1->next!=NULL)//继续两两比较相连的边表的x值,进行排序 { if(T1->next->x<T1->x) { T2->next=T1->next; T1->next=T1->next->next; T2->next->next=T1; T2=T2->next; } else { T2=T1; T1=T1->next; } } } } void PolygonFill(HDC hdc)//多边形填充 { HeadE=NULL; for(CurrentB=HeadB;CurrentB!=NULL;CurrentB=CurrentB->next)//访问所有桶结点 { //对每条扫描线,将该扫描线上的边结点插入带临时AET表中 for(CurrentE=CurrentB->p;CurrentE!=NULL;CurrentE=CurrentE->next)//访问桶中排序前的边结点 { AET *TempEdge
评论