How to find which screen corner is farthest?

[+DZ-Jay]

Given a particular position on the screen, how can I find the corner which is the farthest away?

 

I know I can figure it out myself using a few "if/else" statements, but I thought to ask just in case there is some magical math function that can do it more efficiently.

 

Here is what I am trying to accomplish:  I want to compute the maximum radius of a circle from a given point on the screen, so that it touches even the farthest point visible.  See below for an illustration:

• The black rectangle is the display screen.
• The red line segment is the maximum radius to cover the screen.
• The green circle is what I want to draw.

 

I have a version of the "dist_fast" function provided by @intvnut to compute the distance between two points; but in order to use it, I need to figure out the farthest point on the screen from the origin.  I figure the farthest point will always be one of the corners.

 

I would like to avoid having to check all four corners individually, if possible.

 

(In case you are wondering, I want to draw concentric circles from an arbitrary point on the screen until the entire screen is covered.  When the computed maximum radius is reached, it should stop drawing.)

 

Or maybe I'm over thinking this?

 

    -dZ.

 

[CapitanClassic]

https://stackoverflow.com/questions/38083222/the-furthest-point-of-rectangle

[+DZ-Jay]

17 minutes ago, CapitanClassic said:

https://stackoverflow.com/questions/38083222/the-furthest-point-of-rectangle

 

Thanks.  That's sort of what I already have.  It's just that the Max() function requires a test and branch (plus the absolute value function in IntyBASIC also includes a test and a branch).

 

I was hoping for something "less branchy," but I guess this is as good as it gets.

 

Thanks anyway!

    -dZ.

[+bent_pin]

You can make your own function and cut the branching way down:

 

I would use the black equations and bit shift left one digit to multiply by 2. Then, it would take no more than 2 branches to find the correct corner. You can cut down on code by storing the results or you can double the size of the code and cut the time of the algorithm in half if you branch to multiple copies of the 2nd step.

 

Also, if these are screen corners, then X1 and Y1 can be oriented to 0,0 and the two equations simplify further.

[+bent_pin]

@DZ-Jay Are you going to try my method?

[+DZ-Jay]

6 hours ago, bent_pin said:

@DZ-Jay Are you going to try my method?

Yes, I will.  It will have to wait until the weekend, though.  Thanks!

 

     dZ.

[+bent_pin]

1 hour ago, DZ-Jay said:

Yes, I will.  It will have to wait until the weekend, though.  Thanks!

 

     dZ.

Sweet, can you please share your results, when you've the time?

Have an awesome week!

[+DZ-Jay]

7 hours ago, bent_pin said:

Sweet, can you please share your results, when you've the time?

Have an awesome week!

 

Hi, @bent_pin,

 

Thanks again for taking the time to respond.  I was going through your solution to try to understand it, and it occurred to me that it can be made a bit more efficient by taking a few shortcuts based on some core assumptions that apply to my case.

 

I translated your original solution to IntyBASIC code for my program.  For context, I am trying to compute the distance to the farthest point, and the input to the distance function is the delta of the points across the two axis ("dist = f(∆x, ∆y)").

 

The original translation looks like this:

    ' Determine the maximum radius ...
    ' ... get the distance to the farthest point on the X axis
    If ((SCREEN_MAX_X - (pX * 2)) < 0) Then
        #dX = Abs(pX - SCREEN_MIN_X)
    Else
        #dX = Abs(pX - SCREEN_MAX_X)
    End If

    ' ... get the distance to the farthest point on the Y axis
    If ((SCREEN_MAX_Y - (pY * 2)) < 0) Then
        #dX = Abs(pY - SCREEN_MIN_Y)
    Else
        #dX = Abs(pY - SCREEN_MAX_Y)
    End If

    ' dist = DistFast(#dx, #dy)
    Gosub DistFast
    MaxRadius = dist

 

It occurred to me that computing the delta essentially repeats the computation we did to determine the side of the axis to use.  Also, because the SCREEN_MIN_X and SCREEN_MIN_Y are always zero (the origin of the screen), we can eliminate entire terms from some of those equations.

 

Thinking a bit more about it, I then figured that if I compute the delta from the point to the far screen axis (which is one of the possible outcomes available), I just need to see if it is greater than 1/2 the screen width -- if it is, the point is on the far half (C,D side); otherwise it is on the near side (A,B side).

 

Here's an illustration to clarify what I mean:

We then do the same for the Y axis.

 

 

The adjusted IntyBASIC code looks like this:

#dX = (SCREEN_MAX_X - pX)
If (#dX < (SCREEN_MAX_X / 2)) Then
    #dX = pX 
End If

#dY = (SCREEN_MAX_Y - pY)
If (#dY < (SCREEN_MAX_Y / 2)) Then
    #dY = pY
End If

 

A few other benefits:

• The division of the constants "SCREEN_MAX_X" and "SCREEN_MAX_Y" by two, is performed by the compiler directly, so that's one less operation.
• No need to get the absolute value because we can order the terms to guarantee they are positive.
• Only two test/branch operations (no "else," no Abs(), etc.)

 

I haven't tested any of this -- it's all just in my head -- so please feel free to let me know if I got anything wrong in my reasoning.

 

To be honest, this is all based on the solution you provided.  I don't think I would have thought of it without it, since I was going on a different direction originally.  So, thanks!

 

     -dZ.

 

 

[+bent_pin]

2 hours ago, DZ-Jay said:

#dX = (SCREEN_MAX_X - pX)
If (#dX < (SCREEN_MAX_X / 2)) Then
    #dX = pX 
End If

#dY = (SCREEN_MAX_Y - pY)
If (#dY < (SCREEN_MAX_Y / 2)) Then
    #dY = pY
End If

Darn good work! You saw past the closest corner problem directly to distance problem parameters.

 

 

I only have one suggestion to reduce the cost of the always operations by reversing them. Same thing, just reversed:

#dX = pX
If (#dX > (SCREEN_MAX_X / 2)) Then
    #dX = (SCREEN_MAX_X - pX) 
End If

#dY = pY
If (#dY > (SCREEN_MAX_Y / 2)) Then
    #dY = (SCREEN_MAX_Y - pY)
End If

This is faster 1/2 of the time because of the avoided subtraction problem when the if fails.

 

Thanks for sharing your code too. It will help future users.

 

If you ever need closest corner, reverse the comparators.

[+DZ-Jay]

26 minutes ago, bent_pin said:

Darn good work! You saw past the closest corner problem directly to distance problem parameters.

 

 

I only have one suggestion to reduce the cost of the always operations by reversing them. Same thing, just reversed:

#dX = pX
If (#dX > (SCREEN_MAX_X / 2)) Then
    #dX = (SCREEN_MAX_X - pX) 
End If

#dY = pY
If (#dY > (SCREEN_MAX_Y / 2)) Then
    #dY = (SCREEN_MAX_Y - pY)
End If

This is faster 1/2 of the time because of the avoided subtraction problem when the if fails.

 

Thanks for sharing your code too. It will help future users.

 

If you ever need closest corner, reverse the comparators.

 

Aha!  Even better!  Many thanks!

 

 

UPDATE:

Err ... the comparison is reverse ... if the distance from the origin to the point is less than 1/2 the screen, the point is closer to the left side, that is correct -- but it means that the farther corner is on the opposite side!  DOH!

 

The correct code should be:

' Default to left corner
#dX = pX

' If the point is closer to the left half
' pick the right corner.
If (#dX < (SCREEN_MAX_X / 2)) Then
    #dX = (SCREEN_MAX_X - pX) 
End If

' Default to top corner
#dY = pY

' If the point is closer to the top half
' pick the bottom corner.
If (#dY < (SCREEN_MAX_Y / 2)) Then
    #dY = (SCREEN_MAX_Y - pY)
End If

 

Thanks again.  I just tested the above and it seems to work.  (Testing the previous version was what elucidated the error.)

 

    -dZ.

[carlsson]

"Nobody puts DZ-Jay in a corner!"

Edited September 25, 2023 by carlsson

[+bent_pin]

1 hour ago, carlsson said:

"Nobody puts DZ-Jay in a corner!"