デカルト平面上で 10 ～ 100 個のランダムな座標を生成するプログラムを作成したいのですが、線を形成する点を見つける必要があります。
線を形成できる少なくとも 4 つのポイントの組み合わせである必要があります。これを行うには、選択した 4 つの点の間の勾配を見つけて、それらが直線を形成できるかどうかを調べます。
ただし、難しいのは、すべてのポイントをどのように組み合わせて作成できるかということです。少なくとも 4 つのポイントのすべての組み合わせを見つけてから、それらの間の勾配をチェックして線を形成できるかどうかを確認するブルート フォース法を使用したいと考えています。
この問題にどのようにアプローチできるかについてのアドバイス、たとえば、組み合わせを効率的に見つける方法についてのアドバイスをいただければ幸いです。
4 つのポイントのすべてのセットを試すメリットはないと思います。ポイントの各ペアを取得し、それらが形成する直線の式 y = mx + c を計算し、各ペア (m, c) を配列に挿入します。次に、この配列を並べ替えます (最初の並べ替えキーが m か c かは関係ありません)。同じ線に属するすべての点のペアは、並べ替えられた配列内の連続したブロックとして表示されます。同じ線上に n 個の点がある場合、対応するブロックには n^2 個の連続した要素がありますが、n 個だけを識別するのは簡単です。明確なポイント。時間と空間の複雑さ: O(n^2 log n)。
ポイント セットにPCA 分析を適用する必要がある場合があります。
通常、4 つのランダムな点は、それらのランダム性のために線を形成しません。そのようなことをしたい場合は、個別の4つのポイントセットごとに線形回帰を微調整し、それぞれの分散を確認してから、ポイントがいつ「線上に整列するか」を確認するために決定する必要があるしきい値を下回るセットを選択します"。