need to write a C++ program that solves the following... Given a list of n recta

Question

need to write a C++ program that solves the following...

Given a list of n rectangles, design an efficient algorithm to decide whether
or not a set of n rectangles contains two rectangles that overlap.

The solution that I am attempting to implement is the line sweep algorithm that creates a line to travel the x-axis from left to right to detect the edge of each rectangle. When the line comes into contact with the left edge of a rectangle the y segment (y.low to y.high) is inserted into an interval tree. When the line leaves the right edge of the rectangle its associated y segment is deleted from the interval tree. The tree structure is a red-black interval tree so the efficiency is O( nlog(n) ).

What I am (more or less) comfortable with

What I am having trouble with

Any help with this is appreciated!

Explanation / Answer

( Full Commented and tried to make more simpler )

Here is the link to code : http://ideone.com/3BdSaG

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.