algorithmflashactionscriptshapes# Algorithm for two rectangles placing in a specific way

# Edit

I've spent some time on looking for an appropriate way to solve my problem with the specific rectangles placement.

Lets get directly to the problem.

I've got two rectangles, which are fixed size. One of them is locked, and cannot be moved, and the other one can be move freely.

I've got two of them placed on the fixed width and height canvas. Lets say it's 1000x1000.

I need to place the second, moveable rectangle in the horizontal or vertical alignment with the other, locked one, while the moveable one cannot get outside the range of 1000x1000 canvas.

What I understand under the definition of horizontal/vertical alignment is that if you look only at X (that's for horizontal) or Y (that's for vertical) axis, you have the locked one inside the moveable one or the other way.

I know that I can get through my problem with a hack, but I want to find any smarter solution to it.

Any suggestions?

EDIT: All the informations about two rectangles are known. Corners, widths/heights.

Solution

Given a coordinate plane over some X[-inf, +inf] axis and a nominal Y[-inf, +inf] axis, two points can be said to be in vertical alignment if their coordinates on the Horizontal axis (we Choose X) are equal. They can be said to be in horizontal alignment if their coordinates on the Vertical axis (Y) are equal.

A rectangle can be described by two pairs of coordinates (x1, y1) and (x2, y2), such that x1 <= x2, and y1 <= y2. (If your pairs come mixed, you can actually rearrange them to use this format - it'll make your life easier.)

A rectangle (r1) can be said to reside INSIDE another rectangle(r2) if and ONLY if r1.x1 >= r2.x1, r1.y1 >= r2.y1, r1.x2 <= r2.x2, and r1.y2 <= r2.y2 all hold true. Note that this holds true no matter which quadrant you're in, or in which direction your axes run.

A rectangle (r1) can be said to reside OUTSIDE another rectangle(r2) if and ONLY if both r1.x1 and r1.x2 fall outside the range (r2.x1, r2.x2) and both r1.y1 and r1.y2 fall outside the range (r2.y1, r2.y2). Note that this includes the case in which r2 is INSIDE r1.

A rectangle (r1) can be said to be SEPARATE from another rectangle (r2) if and only if it is OUTSIDE that rectangle, and that rectangle is not INSIDE it. (that is: r1 OUTSIDE r2 && NOT r2 INSIDE r1)

A rectangle (r1) can be said to OVERLAP another rectangle(r2) if and only if it is neither INSIDE nor OUTSIDE that rectangle. (Alternatively, you may choose to claim that a rectangle wholly inside another is a valid overlap, and say that OVERLAP = !SEPARATE. Depends on your applications.)

Alignment is much harder for rectangles. Rectangles of the SAME EXACT size can be said to be aligned in the same way as points (using (x1, y1) of each rectangle as your points of reference. For Rectangles of Differing size, I suggest you use the center point as a reference: Rectangles are VERTICALLY aligned if (r1.x1+r1.x2)/2 = (r2.x1+r2.x2)/2, and horizontally aligned if (r1.y1+r1.y2)/2 = (r2.y1+r2.y2)/2.

I'd write a class that encompasses these rules, and use that to check each movement, using three rectangles - the two you mentioned, and the bounding box as the third.

```
CLASS rectangle
x1
x2
y1
y2
CONSTRUCT(xx1, yy1, xx2, yy2):
Ensure xx1 <= xx2 and yy1 <= yy2 - swap them if you like
x1 = xx1, y1 = yy1, x2 = xx2, y2 = yy2
IS_INSIDE(rectangle r2):
IF r2.x1<=x1 && r2.y1<=y1 && y2 <= r2.y2 && x2 <= r2.x2:
RETURN TRUE
RETURN FALSE
IS_OUTSIDE(rectangle r2):
IF r2.x1 <= x1 <= r2.x2 || r2.x1 <= x2 <= r2.x2 || r2.y1 <= y1 <= r2.y2 || r2.y1 <= y2 <= r2.y2 :
RETURN FALSE
RETURN TRUE
IS_SEPARATE(rectangle r2):
IF IS_OUTSIDE(r2) && ! r2.IS_INSIDE(me):
RETURN TRUE
RETURN FALSE
IS_OVERLAPPED(rectangle r2):
IF ! IS_OUTSIDE(r2) && ! IS_INSIDE(r2):
RETURN TRUE
RETURN FALSE
IS_VERTICALLY_ALIGNED(rectangle r2):
IF (x1+x2)/2 = (r2.x1+r2.x2)/2:
RETURN TRUE
RETURN FALSE
IS_HORIZONTALLY_ALIGNED(rectangle r2):
IF (y1+y2)/2 = (r2.y1+r2.y2)/2:
RETURN TRUE
RETURN FALSE
```

Then you can write a very simple function to see if r2 is validly placed, assuming r2 is the moveable rectangle, r1 is the fixed one, and box is an undisplayed rectangle representing the bounding box of the canvas:

```
IS_VALID_PLACEMENT(r2, r1, box):
//In the bounding box
IF r2.IS_OUTSIDE(box):
RETURN FALSE
//Aligned with r1
IF ! r2.IS_VERTICALLY_ALIGNED(r1) && ! r2.IS_HORIZONTALLY_ALIGNED(r1):
RETURN FALSE
//Not overlapping r1
IF ! r2.IS_SEPARATE(r1):
RETURN FALSE
RETURN TRUE
```

And just run that every time the box moves. If it returns false, undo the move, or use bounding logic to do abutment.

I was rereading your question, and I noticed your definition of vertical alignment. Totally doable:

```
IS_VERTICALLY_ALIGNED(rectangle r2):
IF x1 <= r2.x1 <= r2.x2 <= x2 || r2.x1 <= x1 <= x2 <= r2.x2:
RETURN TRUE
RETURN FALSE
IS_HORIZONTALLY_ALIGNED(rectangle r2):
IF y1 <= r2.y1 <= r2.y2 <= y2 || r2.y1 <= y1 <= y2 <= r2.y2:
RETURN TRUE
RETURN FALSE
```

- Difference between back tracking and dynamic programming
- How can we optimize this algorithm from O(N ** 2) to better complexity in order to pass performance test?
- How do I predict the required size of a Base32 Decode output?
- Reversing AND Bitwise
- Why does my binary search need an extra comparison? log2(N)+1
- How to build a trie for finding exact phonetic matches, sorted globally by weight, and paginated? (Building off this example)
- What is the Time Complexity and Space Complexity of extending a string according to a rule?
- Skyscraper puzzle algorithm
- Check if all elements in a list are equal
- Bitwise Interval Arithmetic
- fast algorithm for drawing filled circles?
- How to find distance from the latitude and longitude of two locations?
- Determine if two rectangles overlap each other?
- Randomly Splitting a Graph according to Conditions
- Maximize distance while pushing crates
- Free a binary tree without recursion
- How can I estimate number of nodes in given tree structure?
- Explanation of class Definition for Binary Trees in leetcode
- Procedural Generation of 2D Rooms
- Is there an algorithm to find the closest element to X in an unsorted array in Ω(logN)?
- Advanced Java idiom for 2+ classes implementing a generic interface
- Is there any algorithm in c# to singularize - pluralize a word?
- Number of Common sub sequences of two strings
- Trying to solve problem 19 on Euler Project
- is a "non-decreasing" sequence "increasing"?
- Is it possible to get the original value of a number, after several multiplications **with overflow**?
- Algorithm to determine the highest and lowest possible finishing position of a team in a league
- Algorithm to calculate the number of divisors of a given number
- Rolling or sliding window iterator?
- best way to pick a random subset from a collection?