[問題] 在矩形中給四點找出圍出來的範圍

看板C_and_CPP作者 (Rex)時間14年前 (2010/02/01 17:51), 編輯推噓2(2推 0噓 12→)
留言14則, 4人參與, 最新討論串1/1
矩形是由二維陣列所表示，給四個座標(即陣列的索引值)， 要找出這四個座標所圍出來的範圍，(例如在二維陣列中給值) ┌─┬─┬─┬─┬─┬─┬─┐ │ │ │ │○│ │ │ │ ├─┼─┼─┼─┼─┼─┼─┤ │ │ │●│●│ │ │ │ ├─┼─┼─┼─┼─┼─┼─┤ │ │●│●│●│●│ │ │ ├─┼─┼─┼─┼─┼─┼─┤ ○ : 給的四個點 │○│●│●│●│●│○│ │ ├─┼─┼─┼─┼─┼─┼─┤ ● : 圍出來要做標記的範圍 │ │●│●│●│ │ │ │ ├─┼─┼─┼─┼─┼─┼─┤ │ │ │○│ │ │ │ │ ├─┼─┼─┼─┼─┼─┼─┤ │ │ │ │ │ │ │ │ └─┴─┴─┴─┴─┴─┴─┘ 想請問有沒有什麼快速運算好方法可以解？ 或是有類似的問題可以參考呢？ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 220.133.18.7
→
02/01 19:53, , 1F
有些點看起來都跑出來了, 應該先確定在裡面的定義是啥
02/01 19:53, 1F
→
02/01 20:46, , 2F
上右 與 右下 兩個的結果不一樣...
02/01 20:46, 2F
→
02/01 20:47, , 3F
1) 4 個座標會順序給你嗎? 2) 四個座標是不是一定是
02/01 20:47, 3F
→
02/01 20:47, , 4F
convex 的多邊形?
02/01 20:47, 4F
我把圖修的稍微一致一點，因為我是把自己要處理的問題弄成比較單純一點的問題來問， 所以沒有定義的很正確，請原諒。 座標順序會給，圖一定是covex。 ※ 編輯: henry035 來自: 220.133.18.7 (02/01 21:37)
推
02/01 21:31, , 5F
就找triangle rasterization的algorithm吧, 四邊形也不
02/01 21:31, 5F
→
02/01 21:32, , 6F
過是兩個三角形. 只是, 你有自己的想法嗎?? 不然一開始
02/01 21:32, 6F
→
02/01 21:34, , 7F
就來問快速運算好方法?_?
02/01 21:34, 7F
→
02/01 21:35, , 8F
硬幹的話就算四條edge, 然後掃scanline判斷吧, 另外還有
02/01 21:35, 8F
→
02/01 21:35, , 9F
coverage的問題, 一個grid被掃過多少%才要標記?_?
02/01 21:35, 9F
推
02/01 21:44, , 10F
如果你的矩形不是很大的話, 好像有一個數學公式可以判斷
02/01 21:44, 10F
→
02/01 21:44, , 11F
一個點是否在三角形圍起來的範圍內, 把矩形內的所有座標
02/01 21:44, 11F
→
02/01 21:45, , 12F
帶入test也是一個方法, 聽說會比做正式的rasterrization
02/01 21:45, 12F
→
02/01 21:46, , 13F
快....@_@"
02/01 21:46, 13F
→
02/01 21:52, , 14F
謝謝大大給方向，我先研究看看。
02/01 21:52, 14F
‣ 更多 henry035 的文章
文章代碼(AID): #1BPgGRMS (C_and_CPP)