geometry - 指定された座標セットから長方形の数を見つける

Question

特定の座標セットから最大数の長方形を見つける必要があります。

次の座標が XY 座標系で与えられているとします。 3 10、3 8、3 6、3 4、3 0、6 0、6 4、6 8、6 10、

次の座標が長方形を形成するかどうかを調べるにはどうすればよいですか (3,0) (3,4) (6,4) (6,0)

実行時間の制約: 0.1 秒

ありがとうございました

Answer 1

ポイントを「x」座標でグループ化された「y」座標のリストに分けます。あなたの場合、2 つの並べ替えられたリストがあります。

3: [0,4,6,8,10]
6: [0,4,8,10]

取得した両方のリストの交差を行う: [0,4,8,10]

それらのいずれか 2 つが長方形を形成します。

[0,4] => (3,0), (3,4), (6,0), (6,4)
[0,8] => (3,0), (3,8), (6,0), (6,8)
[4,8] => (3,4), (3,8), (6,4), (6,8)
...

このソリューションは、x、y 軸に平行な辺を持つ直交する長方形に対してのみ機能します。

Answer 2

ポイントのすべてのペアについて、たとえば (x1, y1) と (x2, y2) は、ある長方形の対角線であると見なします。初期セットに点 (x1, y2) と (x2, y1) が存在する場合、長方形が見つかりました。同じ長方形を表す 2 つの対角線が存在するため、最終的な答えを 2 で割ることに注意してください。

これは、x 軸または y 軸に平行な長方形に対してのみ機能します。

疑似コード C++:

answer = 0;
set<pair<int, int>> points;

for(auto i=points.begin(); i!=std::prev(points.end()); i++)
{
    for(auto j=i+1; j!=points.end(); j++)
    {
        pair<int, int> p1 = *i;
        pair<int, int> p2 = *j;

        if(p1.first == p2.first || p1.second == p2.second)
            continue;

        pair<int, int> p3 = make_pair(p1.first, p2.second);
        pair<int, int> p4 = make_pair(p2.first, p1.second);

        if(points.find(p3) != points.end() && points.find(p4) != points.end())
            ++answer;
    }
}

return answer/2;

Answer 3

4 つの点が長方形を形成しているかどうかを確認するには、次のようにします。

1. 2点ごとに距離を計算します。float の配列にすべて格納します。
2. 配列をソートします。

a[0] = a[1]、a[2] = a[3]、a[4] = a[5] になります。

Answer 4

次の座標が長方形を形成するかどうかを調べるにはどうすればよいですか

差分ベクトルが直交しているかどうか、つまり内積がゼロかどうかを確認します。

これは、これらの座標がリストに含まれているかどうかをチェックしません。また、四角形が座標軸に沿って配置されているかどうかもチェックしません。これははるかに単純な問題です。

入力内のすべての長方形を見つけたい場合は、すべての四角形に対して上記のチェックを行うことができます。パフォーマンス上の理由でそれが受け入れられない場合は、質問を更新して、直面している問題のサイズとパフォーマンスの制約の種類を示す必要があります。