12 - Tetrahedral Shadows
Back to Topic List
Hi Kevin!
This time I would like some help whether my understanding of the problem is right or not. So, the four vertices of the tetrahedron is given in 3D. "At noon the sun shines directly downwards, and the tetrahedron casts a shadow onto the floor below and assuming all rays of light travel directly downwards, all parallel to each other." I assume that the floor is the XY plane, so the projections of each vertex is (Xi, Yi) where the original coordinates of each vertex is (Xi, Yi, Zi) - so Zi coordinates can be disregarded.
If this is right, then the task is to calculate the area of a quadrilateral. The area can be calculated with several methods, I tried the so-called "Shoelace formula". This formula can be applied for convex and concave quadrilateral as it uses signed area values by calculating some determinants. As the 4 four projected vertices can form a concave quadrilateral we need the absulute value of areas as the shadow of a tetrahedron cannot be concave (is is just my suspicion), or if it can be, then it is not problem as the formula covers both cases.
So I would like to ask you if this thinking will lead me to the solution or contains mistakes and I should keep on trying.
Thank you in advance!
Hi Adam!
Your understanding of how the points project onto the "floor" is entirely correct - however I'm not sure that the Shoelace method will always produce the correct answer here. As you mention, the issue is the convex shadows created when connecting the 4 points (and you are correct to suspect that it is not possible for a convex solid to cast a concave shadow).
shadow vs shoelace
However, I think you're about 90% of the way there... I'm hesitant to say too much more and reveal the remaining 10% :)
I also double-checked and updated the checker logic for this problem, as it looked like the trigonometric methods I was using were introducing some error in certain testcases.
Hi Kevin!
Thank you for the confirmations of my thoughts! I agree that saying too much would kill the "Heureka" moment for me, so I think what you said is enough :)
Hmmm....Considering the 3-data example. The first and second tetrahedron cast a convex polygon while the third a concave one, but we know that this is not possible, it is the case you showed with the GIF in your previous post when the vertex is "hiding. So I found the convex hull of the point set which can contain 3 points ("concave" case) or the original 4 points ("convex" case).
I had to sort the points clock wise/counterclock wise in order to apply shoelace formula.
Trying shoelace formula led me to the correct answer in case of concave (third tetrahedon in the example with area 12744) but the first and second ones differed from the answers in the example: I got 5406 instead of 5349 and I got 8517 instead of 6640
Then I tried another approach. Simply I searched for the center point of the polygon (let call it point O) and made triangles by connecting O with each vertex. Then I simply calculated the area of these triangles by Heron"s formula, which gave me exactly the same results as shoelace did (5406 and 8517)
I do not want you to help me with hints, I just would like to ask you to check the checker's algorithm once more please.
Thank you and sorry for bothering you :)
Hi Adam!
No bother at all! I think that this time around the issue came with the "update" I made to remove the error in the previous checker logic... On second regard, it looks like the previous logic was actually correct and my "update" was incorrect.
The checker has been reverted, so the issue should be fixed now.
And the previous correct values for the example testcases were 5406 8517 12744, so your values look 100% correct now :)