Algorithm for solving a simple (?) Array Problem

Question

For this problem, speed is very important. I drew a good image to better explain the problem. The algorithm must calculate whether the edges of the rectangle continue within the canvas, will another edge cross the edge?

We know:

• Canvas size
• The size of each rectangle
• The position of each rectangle

The faster the solution, the better! I'm pretty stuck on this and don't know where to start.

alt text http://www.freeimagehosting.net/uploads/8a457f2925.gif

Greetings

Answer 1

Just create a set of intervals for each of the X and Y axis. Then for each new rectangle, see if there are intersecting intervals in the X or Y axis. See here for one way to implement interval sets.

In the first example, the interval set on the horizontal axis will be { [0-8], [0-8], [9-10] } , and vertically: { [0-3], [4-6], [0-4] }

This is only a sketch, here I have set forth a lot of details in detail (for example, you can usually set the set / tree interval, "whose intervals overlap this" instead of "intersecting with this", but nothing can be done).

Edit

Browse this MIT lecture (it's a bit long, but absolutely worth it). Even if you find simpler solutions (than introducing an extended red and black wood), it's good to know the ideas behind these things.

Answer 2

Lines that are not parallel to each other intersect at some point. Calculate the slopes of each line, and then determine which lines they will not intersect.

Let's start with this, and then see how to optimize it. I am not sure how your data is presented, and I do not see your image.

Using slopes is a simple equality check, which probably means you can use data sorting. In fact, you can probably just create a set of different slopes. You will need to figure out how to present the data in such a way that the two slopes of the same rectangle are not considered intersecting.

EDIT: Wait, how two rectangles whose edges go to infinity do not intersect? Rectangles are basically two lines perpendicular to each other. Does this mean that it always intersects with another if these lines are extended to infinity?

Answer 3

until you specify the language you decide to solve, I will use some kind of pseudocode

the idea is that if everything is in order, then the sorted collection of the edges of the rectangle along one axis should be a sequence of non-overlapping intervals.

• specify all your rectangles by assigning them separate identifiers
• create an empty binary tree collection (btc). this collection should have a way to insert an integer node with information btc :: insert (key, value)
• for all rectangles, do:

 foreach rect in rects do btc.insert(rect.top, rect.id) btc.insert(rect.bottom, rect.id) 

4. now iterating through btc (this will give you an ordered order)

 btc_item = btc.first() do id = btc_item.id btc_item = btc.next() if(id != btc_item.id) then report_invalid_placement(id, btc_item.id) btc_item = btc.next() while btc_item is valid 

5,7,8 - repeat steps 2,3,4 for the coordinates of the line and the line and the line.

Answer 4

I like this question. Here is my attempt to end this:

If possible: Create a polygon from each rectangle. Treat each edge as a line of maximum length to be trimmed. Use the clipping algorithm to check the weather or do not overlap with another. For example, this: String trimming

But keep in mind: if you find an intersection in the vertex position, it is valid.

Answer 5

Here is an idea. Instead of creating each rectangle with (x, y, width, height) , create them using (x1, y1, x2, y2) or at least interpret these values ​​with respect to width and height.

That way, you can check which rectangles have the same x or y value, and make sure the corresponding rectangle has the same secondary value.

---

Example:

The indicated rectangles have the following meanings:

• Square 1: [0, 0, 8, 3]
• Square 3: [0, 4, 8, 6]
• Square 4: [9, 0, 10, 4]

First, compare Square 1 with Square 3 (no collision):

• Compare x values
  • [0, 8] to [0, 8] This is exactly the same, so there is no crossover.
• Compare y values
  • [0, 4] - [3, 6] None of these numbers are alike, so they are not a factor

Then we compare Square 3 with Square 4 (collision):

• Compare x values
  • [0, 8] - [9, 10] None of these numbers are alike, so they are not a factor
• Compare y values
  • [4, 6] - [0, 4]. Rectangles have a total of 4, but 0! = 6, so there is a collision

We know that we know that a collision will occur, so the method will end, but give an assessment of Square 1 and Square 4 for some additional clarity.

• Compare x values
  • [0, 8] - [9, 10] None of these numbers are alike, so they are not a factor
• Compare y values
  • [0, 3] - [0, 4]. The rectangles have a total number of 0, but 3! = 4, so there is a collision

Let me know if you need more details :)

Answer 6

Heh, given the extreme overlapping intervals, you simply define all the individual intervals along the x and y axis. For each cutting line, search for the upper boundary along the axis that will be cut based on the starting interval value. If you do not find the interval or the interval does not cross the line, then this is a valid string.

The slightly tricky part is to understand that the actual cut lines do not intersect the rectangle along the axis, so you can combine overlapping intervals in one interval. You get a simple sorted array (which you fill in O (n)) and O (log n) for each cutting line.