I have a shape, made up of interconnected squares. Their sizes are all equal and known. Think tetris blocks, but the shapes can be made of any number of squares, greater than or equal to one.
I need to know whether it is possible for this shape to contain ANY circle, that comes into contact, or encloses ALL the squares in the shape, and NO part of the circle is outside the shape. This includes the circle's interior as well as its circumference. A circle being tangent to a square does not count as being in contact with it.
For example:
- A 2x2 shape can fit a circle, with maximum diameter of 2 square units, therefore it is valid.
A 3 square L shape can. It can fit a circle that lies tangent (internally) to the sides of the 'elbow' square and hits the opposite corner. Image: https://i.stack.imgur.com/M1y1u.jpg
A 3x1 shape cannot. The maximum size of the possible circle is 1 unit, and its not possible for the circle to be in contact with all three squares.
Things I do know so far:
- If the difference between the width and height of the shape is more than one square, it is not valid.
- If there is a hole in the shape, its not valid.
I need some kind of algorithm, as I will likely need to program this in Java.
I have been told that using the Möbius Transformation could potentially be useful, but the maths behind it is beyond my level.
Is this possible to do algorithmically, or by checking against a set of rules?
(Sorry for no images, the image uploader does not seem to be working for me)
For a given center $(x_0,y_0)$ and a given radius $r$, the condition for the included square centers is: $$ (x_i-x_0)^2-(y_i-x_0)^2 \le r^2 $$
For example, for the center $(0,0)$ and radius $1$, the shape 2x2 is generated, and for radius $2$, the shape 4x4 is generated.
For the center $(0.5,0.5)$ and radius $1.5$, the shape 3x3 is generated and with radius $2$, the shape 4x4 without 1x1 corner squares is generated.
As shown, the solution dependa on the center, which can be greatly standardized by taking the round of the mean for each coordinate: $$ (x_0,y_0)=([\overline{x}],[\overline{y}]) $$
This will discard some "pathological" cases which arise by using the mean operator alone:
For the center $(0,0)$ and radius $2$, the shape 4x4 is generated, but, for the center $(0.25,0.25)$, the shape 4x4 includes one 2x1 top block and one 1x2 right block, with a total of 20 blocks, and with the given center as the exact mean of the coordinates. By applying the round operator we remove those 2x1 and 1x2 block by having the $(0,0)$ center