You can find more details on where these challenges come from and how/why we will be approaching them in the original posting.
Challenge #2
The original link to the challenge (in French) can be found here. It's easy to understand but non-trivial to wrap one's head around...
Consider a nice perfect cube. So far so good. Consider slicing this cube with a Samurai sword in one swift straight cut. Now take a look at the 2D shape created by the cut on the cube. What types of shape can it be? We are primarily interested in whether or not it can be a regular polygon (equilateral triangle, square, regular pentagon, regular hexagon...).
Starting simple: Square
Let's look at some of the simpler shapes. Ironically, the simplest solution is not the equilateral triangle but the square. Can the slice lead to a square? After a few virtual cuts in your mind, you will have noticed that if the cut is parallel to any side, the shape of the slice will be a square!
Equilateral triangle
A little trickier, but a few additional virtual slicing and dicing should reveal the answer. Select a corner of the cube (technically, a vertex). Then move away from that corner along the three edges that make up the corner by an equal amount. The dimensional plane going through those three points (there is one and only one such plane: in 2D there is one and only one line going through two distinct points, in 3D there is one and only one plane going through three distinct points) will lead to an equilateral triangle:
The proof is straightforward: because we moved away from the corner by a constant value in all three directions, the three sides of the triangle are all equal to each other (square root of twice the square of the constant value, thanks Pythagoras!).
3-D Plotting in R
Before continuing, one question you might have is how the previous visuals were generated. Let's remind ourselves these posts are not as much about solving the challenge but also about expanding our R skills!
There are multiple functions and packages, but I was aiming for simplicity. I used the lattice package which has the benefit of containing lots of other functions so probably a good idea to have it installed once and for all, not only for the purpose of this challenge. Within that package, wireframe() is the function of interest.
The simplest way to use it is to provide a matrix where the value of the i-th row and j-th column is the altitude at the i-th index on the x-axis and j-th index on the y-axis. This assumes that all points on the x-axis and y-axis are equidistant. Alternatively, you can create a data.frame (say df) with columns for the x, y and z values. Then simply call wireframe(z ~ x + y, data = df) and you're good! There are multiple parameters for the shading, viewpoint angle and so forth...
Let's just run the basic example from the help file using the pre-loaded volcano dataset which is a 87 * 61 matrix:
wireframe(volcano, shade = TRUE, aspect = c(61/87, 0.4), light.source = c(10, 0, 10))
The z-axis label was slightly truncated, but aside from that it's a pretty nice plot for one-line of code!
Back to our cube
We solved the 3 and 4 sided regular polygons, but what about, 5, 6, 7...
We could continue playing around, but visualizing these slices is pretty tricky you'll have to admit!
So how can R help? Well how about generating a whole bunch of planes and looking at the type of slices we obtain?
To do that, a tiny little bit of algebra first. The general equation of a 2D plane in 3D is:
z = a + b * x + c * y
[well the purists might disagree and they would be correct, how about the vertical plane satisfying x = 0? It's not covered by the previous equation]
However the planes not covered are all the x = constants and y = constants which either don't slice the cube, or slice parallel to certain sides of the cube which we showed leads to squares!
So now, all we need to do is generate a whole bunch of a, b and c values, and see where the resulting plane intersects the cube.
Step 1: Edge intercepts
Again a little algebra, but there are 12 edges the plane could potentially intercept:
- the four vertical edges, parallel to the z axis, corresponding to {x=0 and y=0}, {x=0 and y=1}, {x=1 and y =0} and {x=1 and y=1}
- the four edges parallel to the x-axis
- the four edges parallel to the y-axis
In each case we can fit two of three values of x, y and z into the equation of the plane and get the third value.
Example: for x=0 and y=1, the equation becomes z = a + c. So the plane intercepts that edge at {x=0, y=1,z=a+c}.
So we end up with 12 points.
Step 2: Valid edge intercepts
For an edge to be valid, the third computed coordinate should be between 0 and 1. In our previous example, {x=0, y=1,z=a+c} is part of the cube if and only if 0 <= a + c <= 1.
We then filter to only keep the valid intercepts.
Step 3: Resulting figure?
Once we know how the cube was intercepted, we need to determine if we luckily stumbled across a special polygon!
To do that, I did the following:
- compute all distances between intercepts (only once so as not to compute everything twice, needless to have both A --> B and B --> A)
- keep the smallest value(s)
- count the number of occurrences of that smallest value
- if the number of occurrences is equal to the number of intercepts, we have ourselves a winner!
Illustration
Consider the square ABCD of side 1. I would compute all 6 possible distances:
- A --> B: 1
- A --> C: sqrt(2)
- A --> D: 1
- B --> C: 1
- B --> D: sqrt(2)
- C --> D: 1
- A --> B: 1
- A --> D: 1
- B --> C: 1
- C --> D: 1
The reason this works is that a regular polygon is convex, so the sides are the smallest distances between points (convex polygons on the left, concave on the right):
Running through a whole bunch of values for a, b and c (remember expand.grid() from the first challenge?) I got the following results for number of identified regular polygons based on number of intercepts:
#Intercepts Not Regular Regular
0 2965368 0
1 39049 0
2 564 0
3 1680834 54885
4 1761091 3884
5 1084221 0
6 530505 196
7 4 0
So a whole bunch of equilateral triangles which makes sense given the technique we developed to generate them ourselves earlier.
Quite a few squares, including some non-trivial ones (non-parrelel to a side):
We did find some regular hexagons:
However, not a single pentagon nor heptagon in sight.
Doesn't mean they don't exist, but again, we used R here to give us some leads, not fully resolve geometrical proofs!
Hope you enjoyed!
No comments:
Post a Comment