全國最多中醫師線上諮詢網站-台灣中醫網
發文 回覆 瀏覽次數:2923
推到 Plurk!
推到 Facebook!

"平移"矩形或"旋轉"矩形後, 求矩形內的所有座標

答題得分者是:syntax
Mmmoney
一般會員


發表:9
回覆:19
積分:5
註冊:2007-10-12

發送簡訊給我
#1 引用回覆 回覆 發表時間:2009-11-04 16:27:35 IP:60.251.xxx.xxx 訂閱

各位大哥

假設矩形上有 N 條直線
而我有這 N 條直線的頭尾點

目前我 計算 矩形在 任意角度旋轉或平移後的所有直線上座標
是用 Bresenham直線演算法

但是在DSP上的效率 跟 PC比
差了一百倍
(Bresenham直線演算法在for迴圈內)

想到的改善方法是
不要用Bresenham直線演算法來計算平移後的每條線的座標點
也許可以用矩形的Angle, 和平移的x/y方向
來簡略計算
例如:
先用Bresenham直線演算法算出矩形平移後的頭尾兩條邊線
再利用上述的想法 來 直接知道 其餘在矩形中間的 N-2 條線
的座標各該X/Y方向移動幾個PIXEL


因為對此方面的基礎知識不夠
看了一些 開源的geometric library
也不知道如何套用
希望有前輩可稍微指點指點, 感謝!



編輯記錄
Mmmoney 重新編輯於 2009-11-06 09:47:34, 註解 無‧
Mmmoney 重新編輯於 2009-11-06 13:48:06, 註解 無‧
istillloving
高階會員


發表:33
回覆:182
積分:183
註冊:2008-10-09

發送簡訊給我
#2 引用回覆 回覆 發表時間:2009-11-05 12:14:44 IP:140.127.xxx.xxx 訂閱
我覺得你的問題讓我陷入了無窮回圈裡面

平移 和 角度 ......

平移是什麼意思你知道嗎???

角度是用來旋轉的吧....=..=

旋轉加上平移

平移的旋轉.......這什麼鬼....=..=

的確是難以歸類....

------
恩...
編輯記錄
istillloving 重新編輯於 2009-11-05 12:15:23, 註解 無‧
syntax
尊榮會員


發表:26
回覆:1139
積分:1258
註冊:2002-04-23

發送簡訊給我
#3 引用回覆 回覆 發表時間:2009-11-06 08:13:38 IP:59.125.xxx.xxx 訂閱
的確,我也有點暈,旋轉、平移、旋轉、旋轉平移旋平移轉旋轉旋轉平移旋轉旋轉平移旋轉旋平移轉旋平移轉旋轉旋平移轉旋轉..........暈暈暈暈暈暈暈
===================引 用 istillloving 文 章===================
我覺得你的問題讓我陷入了無窮回圈裡面

平移 和 角度 ......

平移是什麼意思你知道嗎???

角度是用來旋轉的吧....=..=

旋轉加上平移

平移的旋轉.......這什麼鬼....=..=

的確是難以歸類....

istillloving
高階會員


發表:33
回覆:182
積分:183
註冊:2008-10-09

發送簡訊給我
#4 引用回覆 回覆 發表時間:2009-11-06 12:22:21 IP:140.127.xxx.xxx 訂閱
我看你改了標題之後卻沒有改內容.....

裡面這一句...........任意角度平移後的所有直線上座標

不知道你是的改還是你真的不知道平移是什麼......

任意角度平移

這句話真經典 搞的我好亂....=..=

而且說真的看一篇論文裡面如果提到新的名詞

一定會做一番解釋或者是定義

而你問題裡面提到那演算法

難道要大家先去看那些演算法 了解之後 再幫你解決問題....

講白一點 那是不可能的事

===================引 用 Mmmoney 文 章===================

各位大哥

假設矩形上有 N 條直線
而我有這 N 條直線的頭尾點

目前我 計算 矩形在 任意角度平移後的所有直線上座標
是用 Bresenham直線演算法

但是在DSP上的效率 跟 PC比
差了一百倍
(Bresenham直線演算法在for迴圈內)

想到的改善方法是
不要用Bresenham直線演算法來計算平移後的每條線的座標點
也許可以用矩形的Angle, 和平移的x/y方向
來簡略計算
例如:
先用Bresenham直線演算法算出矩形平移後的頭尾兩條邊線
再利用上述的想法 來 直接知道 其餘在矩形中間的 N-2 條線
的座標各該X/Y方向移動幾個PIXEL


因為對此方面的基礎知識不夠
看了一些 開源的geometric library
也不知道如何套用
希望有前輩可稍微指點指點, 感謝!



------
恩...
編輯記錄
istillloving 重新編輯於 2009-11-06 12:27:59, 註解 無‧
istillloving 重新編輯於 2009-11-06 12:29:15, 註解 無‧
Mmmoney
一般會員


發表:9
回覆:19
積分:5
註冊:2007-10-12

發送簡訊給我
#5 引用回覆 回覆 發表時間:2009-11-06 13:55:43 IP:60.251.xxx.xxx 訂閱
Dear  大哥:

一個矩形在二維平面座標上 可以 平移 也可以旋轉咩

其實我的意思就是 矩形的圖控 在二維平面上被滑鼠移動位置後

如何比較快速的求得 矩形內部全部的座標位置?

我本來的用法是Bresenham演算法, 他可以用一條直線的起始/結束點, 去模擬一條直線在螢幕上的座標
前文是說, 我不要用它!
因為他在DSP平台上的效率比 PC慢

請教各位大哥大姐有沒有其他求 矩形內部全部的座標 的方式?

編輯記錄
Mmmoney 重新編輯於 2009-11-06 13:56:11, 註解 無‧
Mmmoney 重新編輯於 2009-11-06 13:57:24, 註解 無‧
syntax
尊榮會員


發表:26
回覆:1139
積分:1258
註冊:2002-04-23

發送簡訊給我
#6 引用回覆 回覆 發表時間:2009-11-07 10:08:32 IP:59.125.xxx.xxx 訂閱
這位大哥

http://en.wikipedia.org/wiki/Bresenham's_line_algorithm

依據該演算法的內容,加上 「矩形內部全部的座標位置」 推斷你是要做畫出矩形並填色,類似這樣的功能
求矩形的圖形範圍內,在量化後(即使用自然數 N 對應),在矩形圖形範圍內所有的整數座標點
使用陣列,定出矩形的所有點

該演算法已經是一種加速的演算方式了 (只使用整數,不用浮點)

DSP平台上的效率比 PC慢 ?
不知 DSP 硬體規格為何?比 PC 慢?,不見得如此,有沒有利用 DSP 的特性? ~ 如果該 DSP 有設計特殊的浮點計算線路,使用整數計算,會比不用,慢

如果要計算一個矩形A量化後的所有的點,不管矩形經過哪種平移與旋轉的組合
1. 還是原來的矩形A
2. 都可以重新定義相對座標原點來相對於絕對座標原點
3. 矩形A都可以被另一個正矩形所包覆 (正矩形,指的是平行的對邊各自與兩個座標平行或垂直)
4. 在正矩形的區域內,所有的點,都被所包覆的矩形A,劃分成,在包覆的矩形A內,與包覆的矩形A外
5. 平移,對於相對原點沒有意義,旋轉,必須先計算完畢
6. 以上定義完畢,請先將旋轉後的四個角點位置計算出來
7. 使用一個 for 迴圈,參與運算的點的數目是政矩形的長 x 寬
8. 在迴圈中使用四個角點,利用斜率劃分區域,將所有正矩形點納入計算,即可求得
9. 然後優先考慮 DSP 的特行,再來採用適合的加速演算法

你的問題應該是這樣吧 ~
===================引 用 Mmmoney 文 章===================
Dear 大哥:

一個矩形在二維平面座標上 可以 平移 也可以旋轉咩

其實我的意思就是 矩形的圖控 在二維平面上被滑鼠移動位置後

如何比較快速的求得 矩形內部全部的座標位置?

我本來的用法是Bresenham演算法, 他可以用一條直線的起始/結束點, 去模擬一條直線在螢幕上的座標
前文是說, 我不要用它!
因為他在DSP平台上的效率比 PC慢

請教各位大哥大姐有沒有其他求 矩形內部全部的座標 的方式?

istillloving
高階會員


發表:33
回覆:182
積分:183
註冊:2008-10-09

發送簡訊給我
#7 引用回覆 回覆 發表時間:2009-11-26 13:05:07 IP:140.127.xxx.xxx 訂閱
請問你 旋轉的角度 和 平移的距離

是使用者自訂嗎?
------
恩...
Mmmoney
一般會員


發表:9
回覆:19
積分:5
註冊:2007-10-12

發送簡訊給我
#8 引用回覆 回覆 發表時間:2009-11-26 18:08:56 IP:60.251.xxx.xxx 訂閱

syntax您說的方式蠻有深度的!
給了我們這些後輩很多啟發
謝謝!

istillloving:
是阿~~ 由使用者任意的拖拉UI上的矩形


各位前輩~
最後我用了一個比較簡單的方式
因為現在我對數學會有點恐懼
大學之後 只修過統計學/微積分
平常沒什麼在用數學

方式如下,

1. 用Bresenham算出量測工具 直線座標 (附檔中的黑線)
2. 用sin/cos算出第一個pixel(藍色XX)的 法線,長度是Tickness (粉紅垂直線)
3. 第二條的法線, 是用該法線的中心點pixel和上一個pixel的 delta值,
去整數加減 第一個法線
4.之後的法線以此類推

等所有法線都算出來之後
就有全部矩形內的座標了




編輯記錄
Mmmoney 重新編輯於 2009-11-26 18:09:58, 註解 無‧
Mmmoney 重新編輯於 2009-11-26 18:40:13, 註解 無‧
Mmmoney 重新編輯於 2009-11-26 18:43:31, 註解 無‧
Mmmoney 重新編輯於 2009-11-26 18:44:43, 註解 無‧
Mmmoney 重新編輯於 2009-11-26 18:45:08, 註解 無‧
istillloving
高階會員


發表:33
回覆:182
積分:183
註冊:2008-10-09

發送簡訊給我
#9 引用回覆 回覆 發表時間:2009-11-26 20:35:21 IP:140.127.xxx.xxx 訂閱
那你現在的問題是

經過平移一段距離 再 旋轉某個角度

然後畫出 那條線嗎??
------
恩...
AndrewK
高階會員


發表:6
回覆:151
積分:161
註冊:2006-10-09

發送簡訊給我
#10 引用回覆 回覆 發表時間:2009-11-27 18:12:25 IP:58.115.xxx.xxx 訂閱
------
Just Do It
-------------------------
其實男生不是真的喜歡你不減肥,而是喜歡你愛吃還不肥;也不是真的喜歡你不化妝,而是喜歡你素顏也好看;也不是真的喜歡你瘦,而是喜歡你瘦卻有胸;也不是真喜歡你獨立,而是他忙的時候別煩他。女孩子,太認真你就輸了。
編輯記錄
AndrewK 重新編輯於 2009-11-27 18:13:11, 註解 無‧
AndrewK 重新編輯於 2009-11-27 18:14:40, 註解 無‧
AndrewK 重新編輯於 2009-11-27 18:33:04, 註解 無‧
AndrewK 重新編輯於 2009-11-28 03:16:45, 註解 更正‧
系統時間:2017-12-12 4:57:52
聯絡我們 | Delphi K.Top討論版
本站聲明
1. 本論壇為無營利行為之開放平台,所有文章都是由網友自行張貼,如牽涉到法律糾紛一切與本站無關。
2. 假如網友發表之內容涉及侵權,而損及您的利益,請立即通知版主刪除。
3. 請勿批評中華民國元首及政府或批評各政黨,是藍是綠本站無權干涉,但這裡不是政治性論壇!