檢查直線形狀的有效性

Question

給定直線形狀，如何有效檢查其是否有效 並指出無效部分？

這裏的有效性意味着寬度約束，即，形狀 的每個部分應該具有不小於某個值d的寬度。形式上，如果您從形狀的頂部到底部垂直地掃描一條線，則該線與形狀之間的所有交點應具有不小於d的長度。 垂直情況類似。 （請注意，形狀內可能有洞，但爲了簡單起見，我們可以先忽略它。）

任何人都可以提出一個有效的算法或向我展示一些指向這個問題的指針嗎？

Answer 1

下面是一種關於O（n^2）的蠻力方法。

首先檢查是否有任何自交叉。多邊形中的交叉寬度爲0，因此它會自動失敗。

解決方案的其餘部分有兩個部分，具體取決於您的約束條件是否僅限於水平和垂直方向，或者是否爲任何角度。無論哪種情況，首先迭代多邊形的每個點。

如果約束條件是水平/垂直，請檢查多邊形的每個線段以查看它是否與通過x或y點繪製的線相交。如果相交，則計算從交點到點的距離;如果它小於約束條件，則表示失敗。

如果約束條件是任意角度，檢查與點不相鄰的多邊形的每個線段，並計算從線段到點的最近距離;你可能會從這個問題Shortest distance between a point and a line segment得到幫助。如果距離小於約束條件，則表示失敗。

Answer 2

我認爲你可以用相當典型的掃描線方法來攻擊它。

首先考慮水平掃描線，從圖的頂部掃到底部。觀察掃描線所穿過的寬度只能在穿過垂直線段的端點時纔會改變。

因此對於水平掃描線，您可以忽略水平線段。採取垂直部分的所有端點，並按垂直位置對其進行分類。 （每個端點都知道它是否是「最高」端點或其分段的「底部」端點）。

爲了模擬掃描線而對列表進行排序的過程。保持「活動集」S，初始化爲空。當您點擊一個「頂級」端點時，將其分段添加到S.當您點擊一個「底部」端點時，從S中移除它的分段。確認活動集的寬度始終滿足約束條件，然後完成。

使用平衡二叉樹（如C++ std::set）來表示活動集，使用比較函數的水平位置。這允許O（1）檢索集合中最左邊和最右邊的片段，因此寬度計算爲O（1）。它還允許插入和刪除O（log n），並且由於您只需將每個垂直段插入並刪除一次，整個掃描將花費O（n log n）。

垂直掃描線對稱重複。

每種排序都是O（n log n），每次掃描都是O（n log n），每次定位兩次...所以整體算法是O（n log n）。