HTML5 canvas元素的元素點映射，需要算法

Question

我目前正在研究「飛行標籤雲領域」的純HTML 5畫布實現，這在許多頁面中毫無疑問地被視爲Flash對象。

標籤畫得很好，表現令人滿意，但是畫布元素中有一件事情可以打破這種想法：您無法識別您在畫布上繪製的對象，因爲它只是一個簡單的平面「圖像」..

我在這種情況下要做的是捕捉點擊事件，並嘗試「猜測」哪個元素被點擊。所以我必須有一種矩陣，它爲畫布上的每個像素存儲指向標籤對象的鏈接，並且我必須在每次重繪時更新此矩陣。現在這聽起來非常低效，在我開始嘗試實現這個之前，我想問問社區 - 在這種情況下是否有一些「衆所周知」的算法可以幫助我？或者也許我只是錯過了一些東西，答案就在角落後面呢？ :)

Answer 1

這被稱爲point location problem，它是計算幾何中的基本主題之一。有很多方法可以使用，比你想的方法快得多，但細節取決於你想要完成什麼。

例如，每個文本字符串都包含在邊界框中。你只是想測試用戶是否在該框中的某個地方點擊過？然後，簡單地存儲每個渲染字符串的最小和最大座標，然後根據每個邊界框測試點，看它是否包含在該範圍內。如果你有大量的測試點，你可以構建任意數量的數據結構來加快速度（例如R-trees），但對於單點來說，構建這樣一個結構的開銷可能是不值得的。

如果您關心點是否實際上落在了描邊字符的不透明區域內，則問題稍微複雜一些。一種解決方案是使用邊界框方法首先消除大多數可能性，然後逐個渲染剩餘的字符串到屏幕外緩衝區，每次檢查目標點是否被觸摸。