使用彈簧演算法描繪良好且維持心像圖之圖形

Abstract

圖形繪製是資訊圖像表示的重要課題之一，應用層面甚廣。因應圖形繪製中對於系統互動與呈現資料庫改變－－稱之為動態圖形繪製－－的需求，我們必須在演算法加入「心像圖維持」這個要素。若在動態圖形繪製問題中，重新繪製時沒有考慮到兩張圖的前後關連，單純在每次改變後重新繪製，有很大的可能圖形的架構會改變而影響使用者的辨識。若可以在前一張圖的基礎下進行修改而成為下一張圖，同時顧及避免基本架構改變與對圖形整齊之需求等兩要素，即可達到心像圖維持的要求。本篇論文建基於泛用性與速度均佳的彈簧演算法，提出一個與前人有所差異的觀點，並依此設計了一套新的心像圖維持演算法。

Graph drawing is an important topic in the domain of information visualization. For needs of interaction with a drawing system or data transition presentation, called 'dynamic graph drawing', we should consider to add a factor called 'mental map preservation' into the current algorithm. In a dynamic drawing problem, if we ignore relations between the new graph and the old one while redrawing the former, but just let the algorithm auto-redraw along with data transition, it's possible that the layout structure of the new one differs from the old one, and then sways human users' ease of identification. We can achieve preserving users' mental map if we can look after both avoidance of structure swaying and need of layout neatness when redrawing the layout from the old graph to the new one. This paper, based on the spring algorithm having a balance between speed and robustness, proposes a view different from former researches, and designs a new mental map preserving algorithm according to that.