0
$\begingroup$

I have two squares in a grid and I need to check if they are adjacent. Performance of my solution is important.

enter image description here

As per image, given the fact that I know the squares are in a grid, I could use the lazy solution, denoted by the green circles. If the mid point of any of the rectangles falls in between the green circles, they must be adjacent. This works as long as the squares are in a grid.

This means if distance $d$ between some square's mid point and red squares midpoint falls in $A < d < A \cdot \sqrt{2} $ they are adjacent.

This is not a bad solution for my specific case right now, but I was wondering if I could use a solution that does not necessarily require the squares to be on a grid. As you can see, the nicer solution denoted by blue dotted square shows that if the square is adjacent and on a grid, it's mid point lays on a larger square, precisely twice as large. I don't know how to write this mathematically. Can you help?

$\endgroup$
5
  • $\begingroup$ Maybe I'm wrong, but I feel like this should be posted somewhere else. See: meta.stackexchange.com/questions/165519/… $\endgroup$ – Adam Rubinson Feb 7 '20 at 11:49
  • $\begingroup$ Also, how are you writing the code for your circles method? I doubt searching through all the points in between the two circles can be efficient? What I would do for this is, make each square an object, and then for each square add 4 attributes- the coordinates of each corner of that square. Then check if two squares share a corner, and if so, check if they share a second corner. However, it's been ages since I did programming lol, and maybe making lots of objects is a costly idea... $\endgroup$ – Adam Rubinson Feb 7 '20 at 11:59
  • $\begingroup$ @AdamRubinson I can't agree, I only used the algorithms tag because this question is asked to solve a software problem, but if someone answers with math, I can turn that into software. $\endgroup$ – Tomáš Zato - Reinstate Monica Feb 7 '20 at 12:00
  • $\begingroup$ @AdamRubinson The circles are an illustration, checking if a point lies between them is purely a matter of comparing it's distance with the circle's center. $\endgroup$ – Tomáš Zato - Reinstate Monica Feb 7 '20 at 12:01
  • $\begingroup$ Firstly, Instead of checking if "the distance d between some square's mid point and red squares midpoint falls in $ \ A<d<A⋅\sqrt2 \ $ they are adjacent", why not just check if "the distance d between some square's mid point and red squares midpoint equals either $ \ A \ $ or $ \ A⋅\sqrt2 \ $ they are adjacent"? Secondly, when you say, "but I was wondering if I could use a solution that does not necessarily require the squares to be on a grid", what exactly do you mean by this? Please elaborate. $\endgroup$ – Adam Rubinson Feb 7 '20 at 13:46
0
$\begingroup$

Your first solution is perfectly fine and will work $100\%$ of the time. Notice that the centers of two touching squares could be atmost $A\sqrt 2$ when arranged tip to tip. This is true no matter how the two squares are arranged. Provided that the squares do not overlap, the minimum distance will be $A$ when they share a side. Hence by checking if the distance lies in $[A,A\sqrt 2]$, you can be sure that the two squares touch atleast one common point. Essentially, you are checking if the center of the second square lies in the green ring.

Also note that when arranged in a grid, the distance can only be the extremes; nothing in between.

$\endgroup$
2
  • $\begingroup$ I know that this solution works, but if I had a more generic one (blue dotted square) I could implement it as a generic "are squares adjacent" for all cases, producing universal solution. The circles method can only be used in my particular case and does not contribute to anything else. $\endgroup$ – Tomáš Zato - Reinstate Monica Feb 7 '20 at 12:03
  • $\begingroup$ What is this "generic case" you speak of? Please provide more detail as we don't know what you mean by it. $\endgroup$ – Adam Rubinson Feb 7 '20 at 13:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.