Take in the real plane a finitely long horizontal line segment and connect the two endpoints by a convex path, above the segment, with the property that the only extreme points of the convex hull of the resulting arch-like circuit formed by the line segment and the path are the points along the line segment part, the `baseline' so to speak. That is, there are no linear parts of the path and it is continuous.
Question: Consider two such figures A and B. I am curious about whether there is a general method for detecting an intersection between A and B, assuming I only know the coordinates of the points of A and the points of B.
Motivation: My friend is working on some kind of applied physics problem about colliding `trajectories.' He asked me essentially the same question as the one posed above. I thought about it for about an hour and a half before convincing myself that, if there is in fact a general method, the key should maybe be to look at what happens in the vicinity of corners and maximums and then try to exhaustively outline conditions for intersection. The cases I came up with were:
- A and B just touch in a single point, so that they do not trespass into each other's interior--i.e., a corner of A pricks the outside of B or the maximum of A just touches the baseline of B from below.
- A and B just touch in a single point, with all of A except this isolated point (the point of contact) lying strictly inside B.
- A and B coincide in two points, so that either a corner or the maximum of A lies inside B.
- A and B coincide in three points, whereby a `tail' of A lies in the interior of B, but the rest of A passes out of B.
- A and B coincide in four points--A essentially squeezes through B.
- A and B coincide in five points; similar to case 5 but the maximum of A also coincides with the maximum of B.
- A and B coincide in a point and a common subset of each other's baselines by lying on the same horizontal and having their tails overlap.
- A and B coincide in all points.
But actually if one looks closely, I am pretty sure that all of the cases except the fifth one can be covered entirely by checking if either a corner or the maximum of A occurs on or inside the boundary of B. So actually the problem should be reduced to checking two cases:
- Either a corner or the maximum of A occurs on or inside the boundary of B.
- Neither the corner nor the maximum of A occurs on or inside the boundary of B.
My idea is to run the following algorithm. First for both A and B set aside the following special points: their left corners, their right corners, and their maximums. Start with A and pick some $z$ out of its special points. Retrieve, if they exist, the unique points $p_1$ and $p_2$ of B that have the same vertical coordinates as $z$ does and similarly retrieve the points $q_1$ and $q_2$ of B that have the same horizontal coordinates as $z$ does. Compare them: If either $p_1$ or $p_2$ is identical to $q_1$ or $q_2$, then you know that the figures coincide in a special point of A, which handles cases 1, 3, 6, and 8; If the horizontal coordinate of $z$ is between those of $p_1$ and $p_2$ and if the vertical coordinate of $z$ is between those of $q_1$ and $q_2$, then you know that $z$ lies in the interior of B or somewhere on its baseline, handling cases 2, 4, and 7 (technically, these pairs of points are not well-defined in the seventh case because $p_1 = p_2 = z$ for instance, but you can just directly inspect for overlapping baselines by checking to see if the corners of A and B have the same vertical coordinates and if one of the corners of A (B) lies in between B's (A's) corners). However, I don't quite know how to test case 5--I thought there should be some checkable necessary and sufficient condition having to do with maximums, but it seems hard to do. Presumably, you'd cycle through the five remaining special points if none of the above checks out.
Some follow-up questions are: Are my cases exhaustive? If so, how do I check for case 5 and is there a way to do it in terms of my special points? If my intuition is correct here, how do you formally argue for it?
All that I am doing in the above algorithm is just taking orthogonal projections onto horizontals and verticals, which is sensible from an intuitive geometric standpoint, since I am looking for instances of A and B crossing into each other. I did some research later on and discovered that my thinking makes a great deal of contact with the idea of the separation theorem for convex polygons and that my algorithm seems in fact to be almost a direct application of that theorem. (After all, you could just treat the figures under consideration as the limiting case, right?)
Added: Actually, I think I was seeing ghosts and it should be pretty simple to handle the fifth case--all you have to do is check to see if the baseline of A lies between the baseline of B and the maximum of B.