กรอบสี (frame)

1065

สมมุติว่าเรามีกระดาษหนึ่งแผ่นที่มีพิกัดมุมบนซ้ายเป็น (x1,1,y1,1)(x_{1, 1}, y_{1, 1}) และพิกัดมุมบนขวาเป็น (x1,2,y1,2)(x_{1, 2}, y_{1, 2}) ถ้าหากเรามีกรอบสี่เหลี่ยมที่มีพิกัดมุมบนซ้ายเป็น (x2,1,y2,1)(x_{2, 1}, y_{2, 1}) และพิกัดมุมบนขวาเป็น (x2,2,y2,2)(x_{2, 2}, y_{2, 2}) กระดาษจะไม่มีส่วนที่ทับกับกรอบสี่เหลี่ยนก็ต่อเมื่อข้อใดข้อหนึ่งดังต่อไปนี้เป็นจริง:

  • x1,1>=x2,2x_{1, 1} >= x_{2, 2}
  • x1,2<=x2,1x_{1, 2} <= x_{2, 1}
  • y1,1>=y2,2y_{1, 1} >= y_{2, 2}
  • y1,2<=y2,1y_{1, 2} <= y_{2, 1}

ในอีกนัยหนึ่ง ถ้าหากขอบขวาของกระดาษอยู่ทางด้านซ้ายของขอบซ้ายของกรอบสี่เหลี่ยม หรือขอบซ้ายของกระดาษอยู่ทางด้านขวาของขอบขวาของกรอบสี่เหลี่ยม หรือขอบบนของกระดาษอยู่ทางด้านล่างของขอบล่างของกรอบสี่เหลี่ยม หรือขอบล่างของกระดาษอยู่ทางด้านบนของขอบบนของกรอบสี่เหลี่ยม กระดาษกับกรอบสี่เหลี่ยมจะไม่มีพื้นที่ทับกัน

ดังนั้นเราสามารถที่เทียบกระดาษและกรอบสี่เหลี่ยมทุกคู่จากข้อมูลนำเข้าและประมวลผลว่าทั้งสองอย่างนี้ทับกันหรือไม่ได้ภายใน O(1)O(1) ฉนั้นอัลกอริทึมนี้ใช้เวลาการทำงานเท่ากับ O(nm)O(nm)