posted 4 years ago

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

What's your solution?

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 maynotassume 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.

What's your solution?

posted 4 years ago

- 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.

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.

posted 4 years ago

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.)