基於VTK多義線的區域查找

Question

我有以下由VTK多義線組成的域 - 每行以'x'開頭和結尾，可能有多個點，並且分配了左右標誌來表示該行左側和右側的區域，確定您是否從開始到結束行進。

the domain of interest http://oi43.tinypic.com/vwsug5.jpg

爲域中的任何隨機點rp，我需要找出它在哪個區域

到目前爲止，我已經嘗試：

• 計算最近的VTK指向rp，找到它所屬的曲線，然後計算rp是否在曲線的左側或右側。這對閉合曲線不起作用，例如上圖中的區域1，特別是如果它們不是連續的（即，一個retangle）
• 將域分成桶：最初，包含vtk點的桶是充滿與該點相關的區域標誌;剩下的桶根據鄰居填充。其中rp下落的桶然後返回其標誌組。但是，如果存儲區包含多個區域標誌（即，當rp靠近一行），則無法使其工作。

我認爲這可能是一個解決的問題，但我不太確定在哪裏看。我曾考慮過point-in-polygon問題，但我正在處理曲線而不是多邊形。其他想法涉及光線追蹤，但它似乎更適合於3D。

任何人都可以提出一個替代方案，或對我嘗試過的修改嗎？

Answer 1

感興趣子域（SDOI）周邊的每條線都必須具有SDOI作爲其邊界域之一。

• 所以，你可以淹沒填補（或擴展圈子）在rp是域中。
• 查找內容是所有這些行neighboured的公共域。
• 這就是你SDOI。

除非：

特殊情況：rp是環形（即結構域1）。所以我們不知道我們是在環內還是環外。我們知道我們處於這種「特殊情況」，因爲從上述方法（1或2）只返回兩個域，但我們不知道哪一個域。

解決方案：

• 遍歷從rp的線，直到它穿過封閉線，通入另一個域。
• 現在做洪水填充這個域，但排除你交叉的線（和第一次洪水填充的所有線）。
• 所有這些線相鄰的域不是你的SDOI
• 所以你現在可以從第一次洪水填充中推斷出SDOI。