wood burning stoves*
The moose likes Programming Diversions and the fly likes Which quadrant? Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Spring in Action this week in the Spring forum!
JavaRanch » Java Forums » Other » Programming Diversions
Bookmark "Which quadrant?" Watch "Which quadrant?" New topic
Author

Which quadrant?

Bear Bibeault
Author and ninkuma
Marshal

Joined: Jan 10, 2002
Posts: 61426
    
  67

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.

What's your solution?

[Asking smart questions] [Bear's FrontMan] [About Bear] [Books by Bear]
Paul Clapham
Bartender

Joined: Oct 14, 2005
Posts: 18657
    
    8

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

Joined: Oct 02, 2003
Posts: 11411
    
  16

it is possible for a point to be on both diagonals. In fact, it is a necessity.


There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
Bear Bibeault
Author and ninkuma
Marshal

Joined: Jan 10, 2002
Posts: 61426
    
  67

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
Bartender

Joined: Jan 17, 2008
Posts: 2402
    
  28

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
Bartender

Joined: Oct 14, 2005
Posts: 18657
    
    8

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

Joined: Jan 10, 2002
Posts: 61426
    
  67

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

Joined: Oct 02, 2003
Posts: 11411
    
  16

I think we're ALL inside the asylum...
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Which quadrant?