如何檢查笛卡爾座標是否有效地組成矩形？

有N個數組。存儲
每個陣列的長度可以是不同的
在各陣列（0..N-1）有（X，Y）的元組（笛卡爾座標）

我要提取的子集的座標組合構成一個完整的大小爲N的交點。換句話說;所有的笛卡爾座標都相鄰。

實施例：

findRectangles({ 
    {*(1,1), (3,5), (6,9)}, 
    {(9,4), *(2,2), (5,5)}, 
    {(5,1)}, 
    {*(1,2), (3,6)}, 
    {*(2,1), (3,3)} 
})

產生以下：

[(1,1),(1,2),(2,1),(2,2)], 
..., 
...(other solutions)...

沒有兩個點可以來自同一組。我剛剛計算了笛卡爾乘積，但這很快就變得不可行（我的使用案例目前有18個數組，每個數組大約包含10個不同的座標）。

來源

2011-05-18 bojangles

可能的錯字：你的例子中的（2,1）是哪裏？你可以從任何陣列中選擇任何點嗎？你不能從相同的數組中選擇兩個點？ – ninjagecko 2011-05-18 11:25:39

修正了錯字;不，你不能從同一個陣列中選擇兩個點。 – bojangles 2011-05-18 11:29:28

只有矩形與所考慮的軸對齊，還是任何矩形都適合？ – 2011-05-18 11:31:01

讓XY是你的一組數組。構造兩個新集合X和Y，其中X等於XY，所有數組均排序爲x座標，Y等於XY，所有數組排序爲y座標。

對於任何X中的陣列中的每個點（X0，Y0）：發現每一個點（X0，Y1）具有相同的x座標和不同的在剩餘的陣列從X
對於每個這樣的一對點（如果它存在）：搜索Y代表點（X1，Y0）和（X1，Y1）

設C是最大數組的大小。然後對所有集合進行排序需要花費時間O（N * C * log（C））。在步驟1中，找到單個匹配點需要花費時間O（N * log（C）），因爲X中的所有數組都是排序的。查找所有這樣的點在O（C * N）中，因爲總體上最多有C * N個點。由於Y被排序，第2步需要花費時間O（N * log（C））。

因此，整體漸近運行時間在O（C * N^2 * log（C）^ 2）中。

對於C == 10和N == 18，您將獲得大約10.000個操作。乘以2，因爲我放棄了這個因素，因爲Big-O-notation。

該解決方案具有實施起來非常簡單的優點。所有你需要的是數組，排序和二進制搜索，其中前兩個很可能已經被構建到該語言中，二進制搜索非常簡單。

另請注意，這是最差情況下的運行時間，其中所有矩形都始於相同的x座標。在平均情況下，你可能會做得比這更好。

來源

2011-05-19 02:07:19 Philip

「找到所有這些點都在O（C * N）中，因爲總共最多有C * N個點。」 - 如果你使用'O（N * log（C））'進行二進制搜索（通常只是因爲某些事情可能並不意味着特定的算法能夠實現），那麼情況並非如此。它是'O（CN * NlogC）= O（N^2 ClogC）'，所以步驟2將採用'O（N^3C（logC）^ 2）'。爲了實現你的狀態，你必須使用** hashing **。見下面的答案。儘管如此，有趣的一點。 – ninjagecko 2011-05-20 12:58:30

您可以使用散列有很大的影響：

hash each point (keeping track of which list it is in) 
for each pair of points (a,b) and (c,d): 
    if (a,d) exists in another list, and (c,b) exists in yet another list: 
     yield rectangle(...)

當我說exists，我的意思是這樣的：

hashesToPoints = {} 
for p in points: 
    hashesToPoints.setdefault(hash(p),set()).add(p) 
for p1 in points: 
    for p2 in points: 
     p3,p4 = mixCoordinates(p1,p2) 
     if p3 in hashesToPoints[hash(p3)] and {{p3 doesn't share a bin with p1,p2}}: 
      if p4 in hashesToPoints[hash(p4)] and {{p4 doesn't share a bin with p1,p2,p3}}: 
       yield Rectangle(p1,p2)

這是O(#bins^2 * items_per_bin^2)〜30000，這是徹頭徹尾的迅速你的18個數組和10個item_per_bin的情況 - 比外部產品方法好得多...更糟糕的是O(items_per_bin^#bins)〜3萬億。 =）

輕微旁註：

您可以通過「修剪」的多次通過在你的計算降低基數和指數。例如

remove each point that is not corectilinear with another point in the X or Y direction 
then maybe remove each point that is not corectilinear with 2 other points, in both X and Y direction

您可以通過排序做到這一點，根據X座標，以點數量方面重複的Y座標，在O(P log(P))時間。你也可以在散列的同時做到這一點。如果一個壞人正在安排你的輸入，他可以使這個優化不起作用。但取決於你的發行版，你可能會看到顯着的加速。

來源

2011-05-18 11:32:53 ninjagecko

如何檢查笛卡爾座標是否有效地組成矩形？

回答

相關問題