如何確定一系列點（或多邊形）是否在矩形區域內？

我一直在尋找關於確定點是否位於多邊形內的帖子，並且對我來說答案要麼過於模糊，抽象或複雜。所以我會試着問我的問題具體到我需要做什麼。如何確定一系列點（或多邊形）是否在矩形區域內？

我有一組描述非直線（有時是閉合的多邊形）的點。我有一個矩形的「視圖」區域。我需要儘可能高效地確定任何線段（或多邊形邊界）是否通過視圖區域。

我不能簡單地測試每個點，看它是否位於視圖區域內。一個區段可能穿過該區域，而區域內實際上沒有任何點（即該區域在該區域上繪製）。

這裏是我想要確定的一個例子（紅色表示該函數應該返回true爲一組點，藍色意味着它應該返回false，例子使用直線和矩形，因爲我不是一個藝術家）。

Red indicates the function should return true, blue indicates it should return false

我希望能夠考慮到另一種狀態（儘管方法/功能可以是單獨的一個），是確定不是多邊形的邊界只是是否通過矩形區域，但無論區域完全被多邊形所包圍。這裏的細微之處在於，在上述情況中，如果我只關心繪製邊框，則該方法應該返回false。但在這裏描述的情況下，如果我需要填充多邊形區域那麼我需要該函數返回true。我現在不需要擔心測試「甜甜圈」形狀的多邊形（感謝上帝！）。

這裏是示出細微差別的例子（紅色矩形不具有單個頂點或邊界段穿過屏幕上的區域，但它仍然應該在屏幕上考慮）：

The red rectangle does not have a single vertex or border segment passing through the on-screen region, but it should still be considered on-screen.

對於「是否有任何線段或多邊形邊界通過或位於屏幕上？」問題我知道我可以想出一個解決方案（雖然可能不是一個有效的）。儘管它比較冗長，但條件對我來說很明顯。但第二個「是屏幕上的多邊形區域？」問題有點困難。我希望有人可能有這樣做的好建議。如果一個解決方案很容易在另一個上面實現，那麼booya。

一如既往，預先感謝您的任何幫助或建議。

PS我有一個確定線相交的功能，但它似乎是矯枉過正使用它來比較每個片段與屏幕區域的每一邊，因爲屏幕上的區域始終是一個普通的[0，0，寬度，高度]矩形。是不是有某種捷徑？

來源

2011-05-20 jpwrunyan

PS我有一個函數，用於確定線交叉點，但看起來像過度使用它來比較每個段與屏幕上的每一側區域，因爲屏幕上的區域是總是一個普通的[0，0，寬度，高度] 矩形。是不是有某種捷徑？

這不是矯枉過正，這裏它neccessary。我能想到的唯一快捷方式是將值[0，0，寬度，高度]硬編碼到該函數中並簡化一下。

來源

2011-05-20 08:56:30 alxx

什麼你正在尋找被命名爲Collision Detection Algorithm谷歌搜索將導致你大量的各種語言實現的，以及大量的理論

有大量的幾何理論的背後，從最簡單的平分線演算到約束Delaunay三角剖分和Voronoi圖（這只是例子）。這取決於物體的形狀，尺寸和用於確保該號碼得到;-)正確性所需要和計算時間之間的比率

好讀

來源

2011-05-20 07:44:43 Grooveek

謝謝。我熟悉基於多邊形的碰撞檢測。這就是我爲我的原始線段交點檢測功能（比如說快3倍）。聽起來像你和alxx建議我使用情況1.我會檢查你的鏈接的情況2的信息。如果我得到的東西工作，我會張貼在這裏反饋。 – jpwrunyan 2011-05-20 09:30:29

如何確定一系列點（或多邊形）是否在矩形區域內？

回答

相關問題