基於任意點數識別形狀

Question

這是一個艱難的。我試圖編寫代碼來識別基於任意數量的點的形狀。

基本上，通過一個觸摸界面，用戶將「繪製」一個形狀（並通過一定數量的觸摸點來跟蹤這個形狀），並且我在二維表面留下了許多點。

基於這些要點，我需要近似描述的形狀是三角形，方形還是圓形。最簡單的方法是什麼？有任何想法嗎？

Answer 1

一個好的第一步是減少點數以找到用戶試圖畫出直線的點 - Ramer–Douglas–Peucker算法適合於此。

Answer 2

嘗試找到最適合最小二乘點的曲線，三角形和正方形。無論哪種形狀具有最小的方差/標準偏差都是可能的嫌疑。找到最適合的形狀可能有點棘手。

將圓圈表示爲中心點和半徑。找出最小化方差的點和半徑。在這種情況下，對於給定的點和半徑，計算方差很容易。快速Google搜索找到一篇題爲Finding a Circle that Best Fits a Set of Points的論文並附帶必要的數學計算。

正方形有一箇中心點，邊長和旋轉角度（0到90度）。方差計算有點棘手，因爲您需要確定象限以找到距離需要最小化的最近邊，或者計算到所有四邊的距離並且只保留最小值。相同的原則，但你有三個變量，而不是兩個。

使用三角形時，可能選取三個點作爲角點，並儘量減少到兩邊的距離的平方。和廣場一樣，你需要弄清楚每個點實際上最接近哪一邊。

我猜如果你能夠爲用戶假設良好的繪畫技巧，那麼你可能只是猜測一個足夠適合每一個形狀，並檢查哪一個最適合。圓 - 中心是所有點的平均值，半徑是距離中心的平均距離。三角形 - 將中心作爲所有點的平均值，距離中心最遠的點是一個頂點，距該頂點最遠的點是另一個頂點，距離它們之間的線的最遠點是第三個頂點。正方形 - 像三角形，但增加一個點，離第三個頂點最遠，得到一個普通的四邊形。不確定這種方法有多寬容，但可能足夠滿足您的需要？無論哪種方式，它可能會很好地初步猜測數值方法來解決最小二乘問題。