• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Which quadrant?

 
Sheriff
Posts: 67746
173
Mac Mac OS X IntelliJ IDE jQuery TypeScript Java iOS
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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?
 
Marshal
Posts: 28193
95
Eclipse IDE Firefox Browser MySQL Database
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
lowercase baba
Posts: 13089
67
Chrome Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
it is possible for a point to be on both diagonals. In fact, it is a necessity.
 
Bear Bibeault
Sheriff
Posts: 67746
173
Mac Mac OS X IntelliJ IDE jQuery TypeScript Java iOS
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.)
 
Rancher
Posts: 2759
32
Eclipse IDE Spring Tomcat Server
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Marshal
Posts: 28193
95
Eclipse IDE Firefox Browser MySQL Database
  • Likes 2
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Sheriff
Posts: 67746
173
Mac Mac OS X IntelliJ IDE jQuery TypeScript Java iOS
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 13089
67
Chrome Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I think we're ALL inside the asylum...
 
Don't get me started about those stupid light bulbs.
reply
    Bookmark Topic Watch Topic
  • New Topic