Win a copy of Mesos in Action this week in the Cloud/Virtualizaton forum!

Bear Bibeault
Author and ninkuma
Marshal
Posts: 64838
86
Given a rectangle divided into four quadrants via two diagonals, determine within which quadrant any given point within the rectangle resides.

You may assume that the diagonals are of zero width (so any point is entirely within at most one quadrant), and you may not assume that the rectangle is square.

The quadrants are named top, right, bottom and left. Origin is upper left.

I have an algorithm that works (computing percent distance from each edge), but I'm unsatisfied with its elegance.

Paul Clapham
Sheriff
Posts: 21107
32
• 1
Let's call the width of the rectangle W and the height H. And let's put the origin of the coordinate system at the bottom left corner. And suppose the coordinates of the point are (x, y).

Then the first step is:

1. If y/x < H/W then the point is in Bottom or Right. If not then it's in Top or Left.

Actually that's the second step, the first is:

1. If x = 0 then the point is in Left.

The third step is:

3. If y/(W-x) < H/W then the point is in Bottom or Left. If not then it's in Top or Right.

Those two decisions tell you which of the four quadrants the point is in. It's easier to follow this if you draw the diagram of the rectangle and its diagonals and consider the slope of the diagonals.

By the way it's possible for a point to be on one of the diagonals even if they have zero width. That's the case where y/x = H/W, for example. I've left out that to simplify the process.

fred rosenberger
lowercase baba
Bartender
Posts: 12124
30
it is possible for a point to be on both diagonals. In fact, it is a necessity.

Bear Bibeault
Author and ninkuma
Marshal
Posts: 64838
86
OK, for the sake of the exercise, let's say that the algorithm must produce a single quadrant, "rounding" to a quadrant when necessary. Which quadrant is used for rounding is unimportant. (In other words, if the point is on the diagonal between top and right, choose one of top or right, doesn't matter.)

Jayesh A Lalwani
Rancher
Posts: 2756
32
After working out the solution, I figured that my solution is exactly the same as Paul's +1 for Paul

Only thing I would add is

if x==W, then point is on right

So, the complete steps are

Paul Clapham
Sheriff
Posts: 21107
32
• 2
And if you replace "y/x < H/W" by "Wy < Hx" and so on, you don't need to be concerned about division by zero.

Bear Bibeault
Author and ninkuma
Marshal
Posts: 64838
86
Thanks guys. Those are all pretty much variations on my original theme, so at least I know I'm not crazy.

Or am I? bwa-ha-ha.

fred rosenberger
lowercase baba
Bartender
Posts: 12124
30
I think we're ALL inside the asylum...