基本图形生成算法PPT学习教案

1、会计学1基本图形生成算法基本图形生成算法第1页/共38页ABCDEPABCDEP第2页/共38页)()(PAPBPBPAPBPBPAPAzzxxzzxxzzxxzzxxT当TBP斜率，为顺时针角当T0时，AP斜率BP斜率，为逆时针角zxABPzxBAP第3页/共38页ABCDEPABCDEP交点数=偶数（包括0）点在多边形之外交点数=奇数点在多边形之内zx左闭右开第4页/共38页第5页/共38页第6页/共38页01 2 3 4 5 6 71234567yx88 9 10扫描线5P4P1P2P3P5扫描线2I1I2I3I4利用图形的空间连贯性和扫描线的连贯性第7页/共38页01234567123

2、4567yx012345671234567yxP1P2P3P4012345671234567yx012345671234567yxP1P2P3P4第8页/共38页102021-10-15543210P1P2P3P4I1I2I3I4P5扫描线5扫描线4扫描线3扫描线2扫描线1I5I6计数0次计数1次计数2次第9页/共38页第10页/共38页x =1/k第11页/共38页第12页/共38页yx0123456789101112345678P6P4P1P5P2P3新边表8.57.56.55.54.53.52.51.50.5528.5-1.5711082075-32.533P4P5P5P6P3P4P6P

3、1P1P2P2P3活性边表活性边表5-32.533P1P2P2P3y=1.5207.833P6P1P2P3y=2.5207.1108P6P1P3P4y=3.5528.P4P51108P3P45-1.57P5P6207.P6P1y=5.5728.P4P51108P3P43.5-1.57P5P6207.P6P1y=6.5528.P4P51108P3P4y=7.5第13页/共38页算法：(对每一条扫描线i)第14页/共38页第15页/共38页P5P1P2P3P4P5P1P2P3P4P5P1P2P3P4P5P1P2P3P4P5P1P2P3P4(a)(b)(c)(d)(e)第16页/共38页第17页/共

4、38页P5P1P2P3P4P5P1P2P3P4P5P1P2P3P4P5P1P2P3P4P5P1P2P3P4(a)(b)(c)(d)(e)P4栅栏线第18页/共38页202021-10-15Flood-fill algorithmBoundary-fill algorithm第19页/共38页4连通区域边界填充算法的填充结果8连通区域边界填充算法的填充结果第20页/共38页第21页/共38页6754S9328S247938479484795684796847978479847994794796754S9328S799缺点？第22页/共38页第23页/共38页第24页/共38页全为边界像素、或已填充的像全为边界像素、或已填充的像素，若为非边界、未填充的像素，若为非边界、未填充的像素，则素，则把每一区间的最右像素把每一区间的最右像素取为种子像素入栈取为种子像素入栈第25页/共38页第26页/共38页第27页/共38页第28页/共38页第29页/共38页第30页/共38页第31页/共38页第32页/共38页第33页/共38页1111算术平均1 22142121加权平均第34页/共38页362021-10-15点有限区域直线有宽度第35页/共38页372021-10-158级灰度