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: http://imgur.com/a/lE0wP
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)
No comments:
Post a Comment