動態(tài)幾何中高效的圖形跟蹤算法設計與實現(xiàn)

1、動態(tài)幾何中高效的圖形跟蹤算法設計與實現(xiàn)摘要：圖形跟蹤是動態(tài)幾何軟件中的重要功能，文章分析了動態(tài)幾何中圖形跟蹤功能的實現(xiàn)原理，設計并實現(xiàn)了一種高效的圖形跟蹤算法，以解決原有算法效率低的問題，通過實驗比較表明新算法具有良好運行效率。關鍵此：動態(tài)幾何；圖形跟蹤；超級畫板中圖分類號：TP393文獻標識碼：A文章編號：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在計算機上做由的幾何圖形，如果在變化和運動中能保持其幾何關系不變，叫做動態(tài)幾何圖形，有關動態(tài)幾何作圖的理論和應用的學科，就是動態(tài)幾何1O跟蹤是動態(tài)幾何軟件中的一個重要功能。在動態(tài)幾何中，一般是對幾何圖形進行跟蹤，當圖形移動、變化時，程序會記錄被跟蹤的幾何圖形所有經(jīng)過的位置的痕跡，即跟蹤幾何圖形留下的痕跡，

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

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

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

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

8、制。也就是說，可以只用一個位圖對象用來保存所有被跟蹤對象留下的全部痕跡：一旦程序中有對象被跟蹤，則生成一個位圖對象，當圖形發(fā)生移動變化，被跟蹤對象產生新的痕跡，則在該位圖對象上繪制，圖形變化完成后，所有痕跡都被繪制在位圖對象上，而顯示所有跟蹤，僅需要將位圖對象在繪圖設備上顯示。在這種設計方案中，每當有新痕跡產生，就將其繪制在位圖對象上，相當于把痕跡保存在位圖中，因此無論有多少痕跡，程序真正保存的僅僅是一個位圖對象，它的大小是固定的，且所用空間非常少。而繪制所有跟蹤的工作也僅僅是繪制該位圖對象，也不會因為跟蹤痕跡多少而受到影響，因為顯示一個固定像素位圖的工作量不會因為圖片內容不同而不同，即所作的

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

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

11、注釋)：/初始化跟蹤位圖相關的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設備上下文創(chuàng)建一個與作圖區(qū)DC設備兼容的內存設備上下文環(huán)境m_dcTraceMem.CreateCompatib

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

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

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

15、electTool:OnMouseMove,只要在該函數(shù)中調用調用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);/移動對

16、象pView->AddTraceToBmp(pObj);增加跟蹤痕跡3.4 繪制跟蹤跟蹤的繪制，只需要在CDrawView:OnDraw中顯示位圖就可以完成跟蹤的繪制。voidCDrawView:OnDraw(CDC*pDC)if(m_pBmpTrace)/畫對象的跟蹤位圖，如果有跟蹤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);/畫對象需要注意的是：1）跟蹤應當在繪制作圖區(qū)中的對象之前，否則跟蹤位圖可能會遮擋莫些對象；2）通過BitBlt函數(shù)顯示位圖時，只需要畫位圖中有跟蹤痕跡的部分，即m_rcTraceBmp所代表的矩形。4實驗4.1 實驗1:圓的跟蹤仍以1節(jié)中的例子為例，在動態(tài)幾何模型作相同的圖形，動畫按鈕的設置為：運動次數(shù)為100,最小值為0,最大值為2*pi,時間為10毫秒，運動類型為重復運動，如圖3。執(zhí)行動畫按鈕“動畫：點C0,2*pi”，1秒，點C運動一周，效果如圖3,程序運行速度與開始沒有區(qū)別，點C的運動視覺效果依然是連續(xù)快速運動。1

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