Fun (?) question here. Given an arbitrary point on the triangle pictured below, what is the "best" way to determine which of the 60 sub triangles it lies within? Suppose I have the coordinates for all sub-triangle vertices.
"Best" is from a programming POV, so my though is to just check if the point is above, below (or on), a given line... then repeat. So maybe you check if it's above or below the 2nd steepest of the 4 lines that intersect at the bottom left vertex - if it's above, check above/below line x, if it's below check above/below line y, etc.
With minimal thought put into the algorithm, I was able to determine the location in 7 steps (meaning above/below 7 different lines) for 16 of the sub-triangles, 6 steps for 32 of the sub-triangles, and 5 steps for 12 of the sub-triangles. I'm fairly certain that this is not optimal. When I say optimal, I'd really like to minimize the max, so the 7 step triangles bug me.
I think 6 steps for 56 of the triangles and 5 steps for 4 of the triangles is a lower bound on the length of the "optimal" solution, but I don't think is achievable.
Any thoughts at the optimal solution? My gut said to split the sub triangles as closely to evenly as possible in each step, but I'm not even sure that's true (or how to do that).
In case it helps, you can view the big triangle as 15 medium sized triangles (3 in each of the 3 corners, 6 in the middle). Each of those 15 medium sized triangles is subdivided into 4 small triangles.
Thanks!
