動(dòng)態(tài)幾何中高效的圖形跟蹤算法設(shè)計(jì)與實(shí)現(xiàn)

1、動(dòng)態(tài)幾何中高效的圖形跟蹤算法設(shè)計(jì)與實(shí)現(xiàn)摘要：圖形跟蹤是動(dòng)態(tài)幾何軟件中的重要功能，文章分析了動(dòng)態(tài)幾何中圖形跟蹤功能的實(shí)現(xiàn)原理，設(shè)計(jì)并實(shí)現(xiàn)了一種高效的圖形跟蹤算法，以解決原有算法效率低的問(wèn)題，通過(guò)實(shí)驗(yàn)比較表明新算法具有良好運(yùn)行效率。關(guān)鍵此：動(dòng)態(tài)幾何；圖形跟蹤；超級(jí)畫(huà)板中圖分類(lèi)號(hào)：TP393文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1009-3044(2011)28-6909-04DesignandImplementationofEfficientAlgorithmofGraphicTraceinDyamicGeomoetryWANGYing1,RAOYong-sheng2,SUMu-hong1(1.SouthChi

2、naInstituteofSoftwareEngineering,Guangzhou510006,China;2.CollegeofComputerScience&Educationalsoftware,GuangzhouUniversity,Guangzhou510006,China)Abstract:Graphictraceisanimportantfunctionofdynamicgeometrysoftware.Inthispaper,weanalyzetheprincipleofgraphictraceindynamicgeometry,thendesignandimplem

3、entanefficientalgorithm.Theexperimentalcomparisonshowsthatthenewalgorithmhasgoodefficiency.Keywords:dynamicgeometry;graphictrace;supersmartplatform在計(jì)算機(jī)上做由的幾何圖形，如果在變化和運(yùn)動(dòng)中能保持其幾何關(guān)系不變，叫做動(dòng)態(tài)幾何圖形，有關(guān)動(dòng)態(tài)幾何作圖的理論和應(yīng)用的學(xué)科，就是動(dòng)態(tài)幾何1O跟蹤是動(dòng)態(tài)幾何軟件中的一個(gè)重要功能。在動(dòng)態(tài)幾何中，一般是對(duì)幾何圖形進(jìn)行跟蹤，當(dāng)圖形移動(dòng)、變化時(shí)，程序會(huì)記錄被跟蹤的幾何圖形所有經(jīng)過(guò)的位置的痕跡，即跟蹤幾何圖形留下的痕跡，

4、并在屏幕上顯示。跟蹤的幾何意義很簡(jiǎn)單，但卻非常有用，簡(jiǎn)單的幾何圖形通過(guò)跟蹤即能產(chǎn)生非常豐富、有趣的圖形，不僅可以豐富動(dòng)態(tài)幾何圖形，而且有助于揭示隱藏在圖形背后的幾何原理。例如：作圓AB,在圓AB上任取一點(diǎn)C（此時(shí)，點(diǎn)C可在圓AB上運(yùn)動(dòng)），以點(diǎn)C為圓心，作圓CB,跟蹤圓CB,并作點(diǎn)C的動(dòng)畫(huà)按鈕。執(zhí)行動(dòng)畫(huà)按鈕，使點(diǎn)C在圓AB上均勻運(yùn)動(dòng)一周，則會(huì)產(chǎn)生如圖2的“蘋(píng)果曲線”。1跟蹤原理目前國(guó)際上動(dòng)態(tài)幾何軟件較為流行的有超級(jí)畫(huà)板2、幾何畫(huà)板3、Cinderella4、Cabri5、Geogebra6等。圖1示例的制作使用的軟件就是“超級(jí)畫(huà)板”，超級(jí)畫(huà)板目前是我國(guó)最著名、使用最廣泛的動(dòng)態(tài)幾何軟件。下面以超級(jí)

5、畫(huà)板為例來(lái)分析跟蹤功能的實(shí)現(xiàn)原理。在超級(jí)畫(huà)板中，將被跟蹤的一個(gè)幾何對(duì)象留下的痕跡作為新對(duì)象保存，即產(chǎn)生跟蹤對(duì)象，然后進(jìn)行繪制，因此有多少幾何對(duì)象被跟蹤就將產(chǎn)生多少個(gè)跟蹤對(duì)象。當(dāng)幾何圖形發(fā)生變化時(shí)，被跟蹤的幾何對(duì)象每留下一條痕跡，就會(huì)在其跟蹤對(duì)象的列表中增加一條數(shù)據(jù)，以保存幾何對(duì)象的痕跡，當(dāng)重新顯示圖形時(shí)，則需要一個(gè)個(gè)地繪制跟蹤對(duì)象痕跡列表中的所有記錄?；谶@種原理，跟蹤對(duì)象會(huì)隨著時(shí)間的增長(zhǎng)，列表中數(shù)據(jù)越來(lái)越多，從而需要更多的空間來(lái)保存跟蹤痕跡；同時(shí)重新顯示該對(duì)象時(shí)，也需要更多的時(shí)間來(lái)重繪，導(dǎo)致整體效率降低。在圖1的跟蹤示例中，點(diǎn)C運(yùn)動(dòng)設(shè)置為：運(yùn)動(dòng)頻率為100,最小值為0,最大值為2*pi,時(shí)間

6、為1毫秒。即點(diǎn)在圓周上運(yùn)動(dòng)一圈分100次完成，每一次的時(shí)間為1毫秒，則理論上運(yùn)動(dòng)一圈需要100毫秒，圓CB的跟蹤對(duì)象會(huì)增加100個(gè)圓的痕跡，因此如果運(yùn)動(dòng)1分鐘，則有10000個(gè)圓的痕跡，保存以及繪制的時(shí)間就相當(dāng)可觀了。實(shí)際上每運(yùn)動(dòng)一次，程序都要重新繪制相關(guān)的圖形，當(dāng)跟蹤對(duì)象的痕跡不斷增多時(shí)，1毫秒不能完成重新計(jì)算和繪制的工作，所以實(shí)際上的效果并不能體現(xiàn)由1毫秒運(yùn)動(dòng)1次。若不修改動(dòng)畫(huà)按鈕的屬性（即默認(rèn)設(shè)置：運(yùn)動(dòng)頻率為100,最小值為0,最大值為2*pi,時(shí)間為1毫秒），剛開(kāi)始執(zhí)行動(dòng)畫(huà)，點(diǎn)C的運(yùn)動(dòng)速度很快，視覺(jué)上點(diǎn)C是連續(xù)運(yùn)動(dòng)的，然而當(dāng)運(yùn)動(dòng)經(jīng)過(guò)一段時(shí)間后（如點(diǎn)C在圓周上運(yùn)動(dòng)兩周，不同計(jì)算機(jī)配置情況

7、有所不同），視覺(jué)上，點(diǎn)C的運(yùn)動(dòng)則是間斷的，程序運(yùn)行較緩慢，從另一個(gè)應(yīng)用程序切換到超級(jí)畫(huà)板不能立即響應(yīng)，有一定的延時(shí)，如果連續(xù)運(yùn)動(dòng)幾十秒左右，應(yīng)用程序的切換幾乎會(huì)導(dǎo)致超級(jí)畫(huà)板無(wú)法響應(yīng)，造成假死機(jī)情況。實(shí)際上，如果對(duì)復(fù)雜的圖形進(jìn)行跟蹤，如函數(shù)曲線、軌跡，情況會(huì)更糟糕，因?yàn)楦檶?duì)象中保存的將是若干條函數(shù)曲線、軌跡的痕跡，計(jì)算比圓要復(fù)雜更多。2跟蹤新算法的原理基于上述原理實(shí)現(xiàn)的跟蹤功能，會(huì)導(dǎo)致程序效率降低，為避免這個(gè)問(wèn)題，考慮不給每個(gè)對(duì)象的跟蹤生成新對(duì)象，而是所有的跟蹤都用一個(gè)對(duì)象來(lái)保存及繪制，可以通過(guò)程序動(dòng)態(tài)地創(chuàng)建位圖，并與指定的環(huán)境相關(guān)的設(shè)備兼容，在該位圖中就可以繪制各圖形，實(shí)現(xiàn)圖形跟蹤的保存及繪

8、制。也就是說(shuō)，可以只用一個(gè)位圖對(duì)象用來(lái)保存所有被跟蹤對(duì)象留下的全部痕跡：一旦程序中有對(duì)象被跟蹤，則生成一個(gè)位圖對(duì)象，當(dāng)圖形發(fā)生移動(dòng)變化，被跟蹤對(duì)象產(chǎn)生新的痕跡，則在該位圖對(duì)象上繪制，圖形變化完成后，所有痕跡都被繪制在位圖對(duì)象上，而顯示所有跟蹤，僅需要將位圖對(duì)象在繪圖設(shè)備上顯示。在這種設(shè)計(jì)方案中，每當(dāng)有新痕跡產(chǎn)生，就將其繪制在位圖對(duì)象上，相當(dāng)于把痕跡保存在位圖中，因此無(wú)論有多少痕跡，程序真正保存的僅僅是一個(gè)位圖對(duì)象，它的大小是固定的，且所用空間非常少。而繪制所有跟蹤的工作也僅僅是繪制該位圖對(duì)象，也不會(huì)因?yàn)楦櫤圹E多少而受到影響，因?yàn)轱@示一個(gè)固定像素位圖的工作量不會(huì)因?yàn)閳D片內(nèi)容不同而不同，即所作的

9、工作是固定的，且所用時(shí)間非常有限。因此無(wú)論跟蹤的情況如何，程序所用的空間與時(shí)間均是固定的，而且都較少，這可以大大提高程序的效率。另外使用這種設(shè)計(jì)方案，不僅僅很容易實(shí)現(xiàn)幾何對(duì)象的跟蹤，而且能對(duì)任何對(duì)象進(jìn)行跟蹤，如文本、按鈕、測(cè)量結(jié)果等等，因?yàn)橹灰谖粓D中繪跟蹤對(duì)象即可，實(shí)現(xiàn)起來(lái)毫無(wú)差別。3實(shí)現(xiàn)跟蹤新算法根據(jù)新算法的原理，實(shí)現(xiàn)步驟如下：1）聲明位圖對(duì)象；2）創(chuàng)建位圖對(duì)象；3）增加跟蹤對(duì)象；4）在位圖對(duì)象中增加跟蹤對(duì)象的痕跡；5）繪制跟蹤；6）當(dāng)不需要是跟蹤痕跡時(shí)，清除跟蹤。在筆者用MicrosoftVisualC+6.0編寫(xiě)的“動(dòng)態(tài)幾何模型”程序中，關(guān)鍵的實(shí)現(xiàn)部分為創(chuàng)建位圖、增加跟蹤痕跡以及繪制跟

10、蹤三個(gè)步驟3.1 聲明位圖對(duì)象由于跟蹤不需要保存到文件中，因此用于保存跟蹤的位圖對(duì)象可作為視圖類(lèi)的成員，其聲明如下：classCDrawView:publicCViewpublic:CDCm_dcTraceMem;/畫(huà)跟蹤位圖時(shí)所用的DCCBitmap*m_pBmpTrace;/跟蹤生成的位圖CBitmap*m_pBmpTraceOld;/跟蹤位圖的舊位圖CRectm_rcTraceBmp;/位圖中有內(nèi)容的最大矩形框CDrawObjListm_traceList;/被跟蹤的對(duì)象列表.3.2 創(chuàng)建位圖對(duì)象在視圖類(lèi)中增加成員函數(shù)CreateTraceBmp用于內(nèi)存DC和位圖對(duì)象的創(chuàng)建(相關(guān)說(shuō)明加有

11、注釋)：/初始化跟蹤位圖相關(guān)的DC和位圖voidCDrawView二CreateTraceBmp()if(m_pBmpTrace!=NULL)/如果已創(chuàng)建，則直接退由return;CDrawDoc*pDoc=GetDocument();ASSERT_VALID(pDoc);m_rcTraceBmp.SetRectEmpty();/置空包含跟蹤痕跡的最大矩形CRectrc;GetClientRect(&rc);/獲取作圖區(qū)窗口大小CClientDCdc(this);/作圖區(qū)DC設(shè)備上下文創(chuàng)建一個(gè)與作圖區(qū)DC設(shè)備兼容的內(nèi)存設(shè)備上下文環(huán)境m_dcTraceMem.CreateCompatib

12、leDC(&dc);m_pBmpTrace=newCBitmap();/為位圖對(duì)象分配內(nèi)存空間創(chuàng)建一個(gè)與內(nèi)存設(shè)備上下文m_dcTraceMem.兼容的位圖m_pBmpTrace->CreateCompatibleBitmap(&dc,rc.Width(),rc.Height();選擇位圖到內(nèi)存設(shè)備上下文m_dcTraceMem中，使得在內(nèi)存設(shè)備上下文m_dcTraceMem上繪圖都繪在位圖上m_pBmpTraceOld=m_dcTraceMem.SelectObject(m_pBmpTrace);以作圖區(qū)背景顏色填充位圖，已保證背景一致m_dcTraceMem.FillS

13、olidRect(rc,pDoc->GetPaperC010r();創(chuàng)建位圖時(shí)機(jī)：為了不要在作圖區(qū)重繪時(shí)顯示空的位圖(與背景色相同)而浪費(fèi)資源，應(yīng)該注意創(chuàng)建與刪除位圖的時(shí)機(jī)。即當(dāng)有對(duì)象被跟蹤時(shí)調(diào)用CreateTraceBmp函數(shù)，而當(dāng)沒(méi)有對(duì)象被跟蹤時(shí)，應(yīng)該刪除位圖。另外，在打開(kāi)文件時(shí)需判斷是否有對(duì)象跟蹤，若有，則也需要調(diào)用函數(shù)CreateTraceBmp。3.3 在位圖中增加痕跡在視圖類(lèi)中增加成員函數(shù)AddTraceToBmp,用于把跟蹤對(duì)象的位置記錄到位圖中，即在位圖中繪制該對(duì)象：/畫(huà)跟蹤對(duì)象，參數(shù)pObj為跟蹤對(duì)象voidCDrawView:AddTraceToBmp(CDrawOb

14、j*pObj)if(!pObj->m_bShow|!pObj->m_bTrace)return;m_rcTraceBmp|=pObj->m_rectPosition;/更新跟蹤痕跡的最大矩形pObj->Draw(&m_dcTraceMem);)其中語(yǔ)句pObj->Draw(&m_dcTraceMem)是把CDrawObj對(duì)象繪制到內(nèi)存設(shè)備上下文中，即實(shí)現(xiàn)在位圖中繪制對(duì)象：把對(duì)象的痕跡保存到位圖中了。一旦跟蹤對(duì)象位置發(fā)生變化時(shí)，調(diào)用AddTraceToBmp函數(shù)即可。例如執(zhí)行動(dòng)畫(huà)按鈕、變量值發(fā)生變化、鼠標(biāo)選取對(duì)象移動(dòng)等。鼠標(biāo)選取對(duì)象移動(dòng)響應(yīng)函數(shù)為CS

15、electTool:OnMouseMove,只要在該函數(shù)中調(diào)用調(diào)用AddTraceToBmp:voidCSelectTool:OnMouseMove(CDrawView*pView,UINTnFlags,constCPoint&point)if(selectMode=move)POSITIONpos=pView->m_selectedList.GetHeadPosition();while(pos!=NULL)CDrawObj*pObj=pView->m_selectedList.GetNext(pos);.pObj->MoveTo(delta,pView);/移動(dòng)對(duì)

16、象pView->AddTraceToBmp(pObj);增加跟蹤痕跡3.4 繪制跟蹤跟蹤的繪制，只需要在CDrawView:OnDraw中顯示位圖就可以完成跟蹤的繪制。voidCDrawView:OnDraw(CDC*pDC)if(m_pBmpTrace)/畫(huà)對(duì)象的跟蹤位圖，如果有跟蹤pDrawDC->BitBlt(m_rcTraceBmp.left,m_rcTraceBmp.top,m_rcTraceBmp.Width(),m_rcTraceBmp.Height(),&m_dcTraceMem,m_rcTraceBmp.left,m_rcTraceBmp.top,SRCC

17、OPY);pDoc->OnDraw(pDrawDC,this);/畫(huà)對(duì)象需要注意的是：1）跟蹤應(yīng)當(dāng)在繪制作圖區(qū)中的對(duì)象之前，否則跟蹤位圖可能會(huì)遮擋莫些對(duì)象；2）通過(guò)BitBlt函數(shù)顯示位圖時(shí)，只需要畫(huà)位圖中有跟蹤痕跡的部分，即m_rcTraceBmp所代表的矩形。4實(shí)驗(yàn)4.1 實(shí)驗(yàn)1:圓的跟蹤仍以1節(jié)中的例子為例，在動(dòng)態(tài)幾何模型作相同的圖形，動(dòng)畫(huà)按鈕的設(shè)置為：運(yùn)動(dòng)次數(shù)為100,最小值為0,最大值為2*pi,時(shí)間為10毫秒，運(yùn)動(dòng)類(lèi)型為重復(fù)運(yùn)動(dòng)，如圖3。執(zhí)行動(dòng)畫(huà)按鈕“動(dòng)畫(huà)：點(diǎn)C0,2*pi”，1秒，點(diǎn)C運(yùn)動(dòng)一周，效果如圖3,程序運(yùn)行速度與開(kāi)始沒(méi)有區(qū)別，點(diǎn)C的運(yùn)動(dòng)視覺(jué)效果依然是連續(xù)快速運(yùn)動(dòng)。1

18、0分鐘點(diǎn)C運(yùn)動(dòng)600周，程序運(yùn)行速度與開(kāi)始沒(méi)有區(qū)別，應(yīng)用程序之間的切換也沒(méi)有延遲情況，點(diǎn)C運(yùn)動(dòng)1周依然只需要1秒。4.2 實(shí)驗(yàn)2:函數(shù)曲線的跟蹤在動(dòng)態(tài)幾何模型軟件中按如下步驟作圖：1)作函數(shù)曲線y=sin(x-a)+ln(a),自變量變化范圍為a-6,a+6,使得曲線關(guān)于點(diǎn)(a,ln(a)對(duì)稱(chēng)；2)作坐標(biāo)點(diǎn)A(a,ln(a),并設(shè)置x參數(shù)為a;3)作變量A的動(dòng)畫(huà)，參數(shù)設(shè)置為：運(yùn)動(dòng)次數(shù)為200,最小值為0,最大值為7,時(shí)間為20毫秒，運(yùn)動(dòng)類(lèi)型為重復(fù)運(yùn)動(dòng)；4)跟蹤曲線及點(diǎn)A,并適當(dāng)修改跟蹤畫(huà)筆。跟蹤動(dòng)畫(huà)按鈕；5)插入文本對(duì)象，文本內(nèi)容為“y=sin(x-a)+ln(a)”；6)執(zhí)行動(dòng)畫(huà)按鈕，效果如圖4。圖4跟蹤曲線圖5超級(jí)畫(huà)板中跟蹤曲線在超級(jí)畫(huà)板作類(lèi)似圖形，變量動(dòng)畫(huà)設(shè)置與上述一致，所有作圖都取消高質(zhì)量畫(huà)筆，動(dòng)畫(huà)運(yùn)動(dòng)一次后效果如圖5。4.3 比較以實(shí)驗(yàn)2與超級(jí)畫(huà)板進(jìn)行比較。動(dòng)畫(huà)設(shè)置：運(yùn)動(dòng)次數(shù)為200、時(shí)間為20毫秒，變量a從最小值0變到最大值7理論值為4秒。表1為兩種跟蹤方案運(yùn)行效率比較，明顯看由新方法更為高效，而且運(yùn)動(dòng)時(shí)間越久優(yōu)勢(shì)越明顯。在表1中，時(shí)間單位為秒；視覺(jué)效果為用戶(hù)肉眼觀察效果；應(yīng)用程序切換時(shí)間為從在任務(wù)欄激活軟件到圖形顯示所用時(shí)間。5