情況如下:如何檢查笛卡爾座標是否有效地組成矩形?
- 有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個不同的座標)。
可能的錯字:你的例子中的(2,1)是哪裏?你可以從任何陣列中選擇任何點嗎?你不能從相同的數組中選擇兩個點? – ninjagecko 2011-05-18 11:25:39
修正了錯字;不,你不能從同一個陣列中選擇兩個點。 – bojangles 2011-05-18 11:29:28
只有矩形與所考慮的軸對齊,還是任何矩形都適合? – 2011-05-18 11:31:01