圈多邊形交點

甲計算幾何問題：
點P0隨機選擇上的多邊形的邊（例如，EB）（例如，BCDE），以找到可能的點（即，P1,P2,P3,...）上的其他基於給定距離的邊（即，r）。以下演示通過找到以點號P0爲中心的圓與多邊形邊之間的交點來顯示解決方案。所以這個問題基本上可以通過Circle--Line-Segment相交分析來解決。圈多邊形交點

我想知道有沒有更高效的方法這個非常簡單的問題就計算成本而言？該過程將被評估幾個million times，所以任何改進都是有意義的。

最終解決方案將受益於Python功耗;
核心計算將在Fortran如果需要。

enter image description here

更新：
感謝您的意見。請考慮我對評論的評論，這有助於澄清更多問題。不願在這裏重複，鼓勵考慮所有評論和答案;）。

我剛剛實施了基於[here]算法的Circle--Line-Segment Intersection的方法。事實上，我調整它適用於線段。在Python實現的算法的基準如下：
enter image description here

線段的數目是：100,000和系統通常是桌面。所用時間爲：15 seconds。希望這些有助於給出一些計算成本的概念。在Fortan的核心實現可以顯着提高性能。
但是，翻譯是最後一步。

來源

2012-01-23 Developer

所有百萬個查詢的距離「r」是否相同？我們可以指望多邊形是凸的嗎？ –

@BorisStrandjev對於我們的問題，所有的多邊形都是凸的。對於每次迭代，「r」可能會有所不同，因此它可能會變化，但對於每個多邊形都是不變的。 – Developer

並且是在單個多邊形或不同的數百萬個查詢中完成的？ –

對於line（或line-segment）之間的交叉和circle（在3Dsphere）有更多的解釋，實施細節和也的Python，C在[this link]等樣本代碼。你可以嘗試解決你的問題。
這個想法基本上和你在[here]中已經找到的一樣。

來源

2012-01-23 11:47:48 Developer

鏈接已死亡 – Alnitak

假設circle--line-intersection進行了優化，你可能能夠通過不同情況區別有所收穫：

爲點A，B：

如果d（P0，A）< r和d（P0，B）< R：否相交
如果d（P0，A）== R：交叉口A處
如果d（P 0，B）== R：交叉口B處
如果d（P0，A）< r和d（P0，B）> R：1個相交，執行circle--line-intersection
如果d（P0，A）> r和d（P0，B）< R：1個相交，執行circle--line-intersection
如果d（P0，A）> r和d（P0，B）> R：有是0，1個或2個交點（A，B）> r：無交集 - >如果minimum distance以行（A，B）== r：1交叉 - >如果minimum distance以行（A，B）< r：2相交納秒

來源

2012-01-23 09:12:39 Wesley

在最後一種情況下，我相信你的意思是d（P0，P2）> r。 –

請注意，以「P0」爲中心的圓圈，所有交點位於圓上，因此它們的距離等於「r」。那就是'd（P0，*）= r'。我從你的回答中遺漏了什麼？ – Developer

對不起，我把交點與實際點混淆了。我會修復答案，希望它更有意義，然後 – Wesley

圈多邊形交點

回答

相關問題