2 つの長方形が重なっているかどうかを効率的に判断するにはどうすればよいでしょうか?

重なり合う四角形: 包括的な分析

2 つの四角形が 2 次元平面内で重なっているかどうかを判断することは、コンピューター グラフィックスと計算における基本的な問題です。幾何学。この記事では、この問題を解決するための効率的なアルゴリズムを検討します。

重なりの条件

2 つの長方形 A と B は、4 つの条件の場合にのみ重なり合います。

• A の左端は B の右端の左側にあります。 RectA.Left
• A の右端は B の左端の右側にあります: RectA.Right > RectB.Left
• A の上端が B の下端の上にあります: RectA.Top > RectB.Bottom
• A の下端は B の上端より下にあります: RectA.Bottom
RectB.Top

アルゴリズム

これらの条件に基づいて、重複をチェックするアルゴリズムを構築できます。

def check_overlap(RectA, RectB):
  return RectA.Left < RectB.Right and \
         RectA.Right > RectB.Left and \
         RectA.Top > RectB.Bottom and \
         RectA.Bottom < RectB.Top

実装

C コードでは、このアルゴリズムを次のように実装できます。

#include <iostream>

class Rectangle {
public:
  int left, right, top, bottom;
};

bool check_overlap(Rectangle rect1, Rectangle rect2) {
  return rect1.left < rect2.right && \
         rect1.right > rect2.left && \
         rect1.top > rect2.bottom && \
         rect1.bottom < rect2.top ;
}

int main() {
  Rectangle rect1, rect2;
  std::cout << "Enter the coordinates of Rectangle 1 (left, right, top, bottom): ";
  std::cin >> rect1.left >> rect1.right >> rect1.top >> rect1.bottom;

  std::cout << "Enter the coordinates of Rectangle 2 (left, right, top, bottom): ";
  std::cin >> rect2.left >> rect2.right >> rect2.top >> rect2.bottom;

  if (check_overlap(rect1, rect2)) {
    std::cout << "The rectangles overlap." << std::endl;
  } else {
    std::cout << "The rectangles do not overlap." << std::endl;
  }

  return 0;
}

この実装では、ユーザーに 2 つの長方形の座標の入力を求め、前述の条件に基づいて重複をチェックします。

以上が2 つの長方形が重なっているかどうかを効率的に判断するにはどうすればよいでしょうか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。