0

次のように、0=白、1=黒の整数の 2D 配列があるとします。

1110001
0110000
0011000
0101100
0100110
0100011
1000001
1011000
1011000

配列内のすべての黒い線を見つけたい。勾配が 1 の垂直、水平、対角線だけが必要なわけではありません。これらすべてを行うことができます。すべての勾配の行を見つける方法が必要です (コードを減らすために既に行っている方法を含めることができます)。したがって、2D 配列を見ると、[0,8] (左下隅) から [2,0] (上部中央) に向かう傾き 3 の線が見えます。他のいくつかのリストを見てきましたが、それらは私がすでにできることだけを探しているか、これらの行を見つける方法を提供していないようです.

私は Java でコーディングしていますが、C++ コード、または単なる論理的な説明も歓迎されます。

私の説明がまだ広すぎる場合は、次のように考えてください。ペイントの線ツールを使用して作成できるすべての線を見つけられるようにしたいと考えています。

4

1 に答える 1

0

探している回線の少なくともほとんどを、妥当なコストで取得できるソリューションを見つけたと思います。このソリューションの欠陥についてコメントしてください。

  1. すべての水平線、垂直線、および完全な対角線 (勾配 1 または -1) を検索します。単純化するために水平線について説明しますが、対角線と垂直線に小さな微調整を加えることで、同じことが適用できます。
  2. 一番右の点が右上または上に隣接する点を持っているかどうかを確認します。（右下または下についても同じことを行います）。
  3. 隣接点が上にある場合、開始点が隣接点と等しい行について、現在の点から行のリストで後方に移動することを確認します。（右下または下のポイントのリストで同じことを行います。）
  4. 行が見つかった場合、または Y が現在の行から 2 以上離れている場合に停止します。
  5. 現在の行の終点が、新しいリスト (複数の横線で構成される行のリスト) の行の終点であるかどうかを確認します。その場合は、この行に新しい行 (手順 4 で見つかった行) を追加します。(これにより、行が重なるのを防ぐことができます。
  6. 手順 4 で Y が 2 以上離れている場合 (回線の終端、接続なし) マスタ リストに回線を追加します。
  7. すべての水平線が繰り返された後、新しいリストをマスター リストに追加します。
  8. 必要に応じて調整しながら 2 ～ 7 を繰り返し、完了後にマスター リストが完成します。垂直線と水平線が正方形または類似のものを作成する場合にのみ重なりますが、水平線またはほぼ水平線の重なりは発生しません。

このロジックに欠陥がある場合はお知らせください。可能であれば、代替案を提案してください。

于 2013-09-23T19:38:02.650 に答える