計算相交和絃對的數量

考慮N圓圈中的和絃，每個和絃都由其端點確定。描述用於確定在圓內相交的和絃對的數量的O(nlogn)解決方案。計算相交和絃對的數量

舉例：沒有兩個和絃共享一個端點。

2012-07-18 Kavish Dwivedi

缺少功課標籤？ – BoBTFish 2012-07-18 15:01:55

Google-fu：http://ripcrixalis.blog.com/2011/02/08/clrs-14-1-dynamic-order-statistics/ – biziclop 2012-07-18 15:04:48

-1

關閉我的頭頂部，按極角排序弦的終點（這是O（n log n）部分）。然後通讀排序列表（即O（n）） - 如果兩個相鄰的端點屬於同一和絃，則它沒有交集。在列表中的兩個相鄰條目屬於不同的和絃的情況下，取決於這兩個和絃的其他端點位於哪裏可能存在交叉 - 例如，如果和絃A具有以其排序順序的終點A1和A2，並且類似於和絃B具有B1和B2，則在列表中找到B2-A1不是交集，因爲B1在前，A2在後。但是，B1-A2將是一個十字路口。

另請參閱biziclop對另一個更精心構建的解決方案的評論。

來源

2012-07-18 15:20:40 twalberg

這會找到一些交叉點，但不是所有的 - 相交的和絃不會必須有相鄰的端點。 – interjay 2012-07-18 16:41:31

我的部分措辭不佳。我是想表明的是，如果一個特定的弦的端點都在有序它們之間的任何其他終端，有可能的交集（儘管如果第二絃的兩個端點是第一端點之間，這不是一個交點）。我想我沒有考慮這種情況，其中包括A1-B1-C1-D1-A2這樣的情況，在這種情況下，B，C和D全部三條相交A. – twalberg 2012-07-18 16:56:57

但是，你無法在' O（n）'的時間，通過排序列表。在'O（nlogn）'時間內，你甚至不能找到所有的交叉點，因爲可能有'O（n^2）'交叉點。你需要一個數據結構，可以讓你一次計算多個交點。 – interjay 2012-07-18 17:03:19

存在一個在O（nlogn）中執行作業的通用線段交集算法。
這可以用於你的情況，因爲兩個和絃不能在圓的外部相交。
以下鏈接包含算法：
http://www.cs.princeton.edu/~chazelle/pubs/IntersectLineSegments.pdf

附：
它需要知識的基本計算幾何（線掃描，距離樹）。

希望這會有所幫助。

來源

2012-07-19 09:45:41

計算相交和絃對的數量

回答

相關問題