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

[henry035 (Rex)]

矩形是由二維陣列所表示，給四個座標(即陣列的索引值)，

要找出這四個座標所圍出來的範圍，(例如在二維陣列中給值)
┌─┬─┬─┬─┬─┬─┬─┐
│  │  │  │○│  │  │  │
├─┼─┼─┼─┼─┼─┼─┤
│  │  │●│●│  │  │  │
├─┼─┼─┼─┼─┼─┼─┤
│  │●│●│●│●│  │  │
├─┼─┼─┼─┼─┼─┼─┤ ○ : 給的四個點
│○│●│●│●│●│○│  │
├─┼─┼─┼─┼─┼─┼─┤ ● : 圍出來要做標記的範圍
│  │●│●│●│  │  │  │
├─┼─┼─┼─┼─┼─┼─┤
│  │  │○│  │  │  │  │
├─┼─┼─┼─┼─┼─┼─┤
│  │  │  │  │  │  │  │
└─┴─┴─┴─┴─┴─┴─┘
想請問有沒有什麼快速運算好方法可以解？ 或是有類似的問題可以參考呢？


--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.133.18.7
→ dendrobium:有些點看起來都跑出來了, 應該先確定在裡面的定義是啥
→ adrianshum:上右 與 右下 兩個的結果不一樣...
→ adrianshum:1) 4 個座標會順序給你嗎? 2) 四個座標是不是一定是
→ adrianshum:convex 的多邊形?
我把圖修的稍微一致一點，因為我是把自己要處理的問題弄成比較單純一點的問題來問，
所以沒有定義的很正確，請原諒。

座標順序會給，圖一定是covex。

※ 編輯: henry035        來自: 220.133.18.7         (02/01 21:37)
推 VictorTom:就找triangle rasterization的algorithm吧, 四邊形也不
→ VictorTom:過是兩個三角形. 只是, 你有自己的想法嗎?? 不然一開始
→ VictorTom:就來問快速運算好方法?_?
→ VictorTom:硬幹的話就算四條edge, 然後掃scanline判斷吧, 另外還有
→ VictorTom:coverage的問題, 一個grid被掃過多少%才要標記?_?
推 VictorTom:如果你的矩形不是很大的話, 好像有一個數學公式可以判斷
→ VictorTom:一個點是否在三角形圍起來的範圍內, 把矩形內的所有座標
→ VictorTom:帶入test也是一個方法, 聽說會比做正式的rasterrization
→ VictorTom:快....@_@"
→ henry035:謝謝大大給方向，我先研究看看。