通過拖動多邊形作爲畫筆來編輯矢量圖像

目標是通過在屏幕上拖動鼠標像多邊形形狀的畫筆一樣進行簡單的矢量圖像編輯，創建畫筆的Minkowski sum和鼠標的路徑。新的多邊形將從任何先前存在的不同顏色的多邊形中減去，並與任何現有的相同顏色的多邊形合併。通過拖動多邊形作爲畫筆來編輯矢量圖像

該計劃將每個鼠標移動作爲從鼠標上一個位置到其當前位置的線段，計算該線段上的Minkowski和，然後使用Weiler–Atherton clipping algorithm更新現有多邊形以包含該Minkowski和。

由於Weiler-Atherton似乎可能會導致UI延遲，如果爲每個鼠標移動運行，我們計劃通過將其放入另一個線程來延遲該步驟，這可能需要時間趕上最新的鼠標移動，或者保存所有Weiler-Atherton計算直到繪圖完成，然後在保存時將其作爲批量操作進行。我們擔心這可能會導致大量重疊多邊形的積累，從而導致用戶界面延遲渲染它們所需的時間。

問題是：上述計劃是Inkscape和其他嚴肅的矢量圖形編輯軟件將執行此操作的方式？這似乎是一個瘋狂的計劃，無論是在算法的詭計和計算複雜性。專家會做什麼？

正在考慮的另一種選擇：使用簡單的光柵操作進行繪畫，然後將光柵轉換爲矢量圖像作爲最後一步。從柵格到矢量的轉換看起來不及Weiler-Atherton那麼棘手，最終輸出的質量可能會受到影響，但它可能是更好的選擇嗎？

來源

2017-09-03 Geo

爲每個鼠標移動運行這些算法似乎不太可能會導致性能問題。計算機遊戲引擎每幀運行的計算幾何數量大大增加。 – jkff

當用戶按住鼠標按鈕並繪製圖標時，您可以記住所有鼠標移動線段，同時將畫筆*行Minkowski與畫面分辨率位圖相加。

您可以使用位圖來繪製屏幕，直到用戶釋放按鈕。那時您可以計算所有線段Minkowski和的聯合並將生成的形狀添加到您的圖形中。

要同時計算這麼多形狀的聯合，某種掃描線算法會是最好的。您應該可以在O（N log N）或線性時間內完成這項工作，這不會造成任何明顯的延遲。

來源

2017-09-04 02:29:01

你的意思是基於Bentley-Ottmann算法，還是你有其他算法？ – Geo

是的，類似的東西對於很多短片段非常有效，在實踐中可能是一個不錯的選擇。我會添加優化以根據需要從鼠標線段生成多邊形線段。 –

IMO Weiler-Atherton的瓶頸是交叉點的檢測，當通過強力施加時需要O（N 2）操作。其餘的處理是重新組織頂點和交點之間的連接，這應該被限制爲O（N），或者甚至是O（NI），其中NI表示交點的數量。

在這種特殊情況下，您可以通過網格或邊界框的層次結構加速搜索交叉點。（請注意，網格與Matt使用輔助位圖渲染的想法相似。）

除非您真的有十億個邊緣，否則我不會擔心運行時間。

來源

2017-09-04 08:16:32

如果你想像專業的矢量圖形軟件那樣做任意的刷子形狀（包括刷子形狀可以對速度或手寫筆壓力作出反應等功能），那麼可能會很不幸地涉及到它。

我正在試驗「Ahn，Kim，Lim - 二維彎曲對象的近似一般掃描邊界」中描述的方法。它似乎處理了我期望從專業繪圖應用程序中得到的許多案例 - 尤其是在掃動時刷子形狀可以動態變化的細節;自適應地生成您想要的分辨率的邊界曲線; 2d曲線的可變寬度偏移;等等。

似乎可以簡化這個方法，如果你並不需要一個通用的方法。但我想在此添加它作爲參考。

PS：我正在尋找一個非paywalled鏈接到這裏包括的答案，那麼這個想出了 - Looking for an efficient algorithm to find the boundary of a swept 2d shape。看起來很像你想要做的:)。

來源

2017-09-19 14:41:58 hkrish

以下是該論文的鏈接：https://pdfs.semanticscholar.org/2e92/f0c0c0d28bcc75a57d68732bb1506eb505b0.pdf – hkrish

通過拖動多邊形作爲畫筆來編輯矢量圖像

回答

相關問題