How can I determine if a convex polygon is completely contained within another convex polygon where speed is critical? I've thought about doing this, which will only use inequalities:
pcp = potentially contained polygon
- Iterate through every one of pcp's points, comparing each one to every one of the containing polygon's points.
- Determine if pcp's point is to the left/right and to the bot/top of the first point.
- Check against every other point of the containing polygon. If the pcp's point is not the same orientation horizontally and vertically as the first check in step 2, then the pcp's point is not contained, thus the entire pcp isn't contained.
Am I on the right track? I haven't implemented this so I have no idea if it'll work. Are there faster methods or improvements that could be made?
A convex polygon can be given either by its vretices or, often more adequate, by inequalities $a_ix+b_iy\ge c_i$ describing the half planes whose intersection is the polygon. With the latter form, a point of the plane is inside the polygon iff all iniequalities hold for its coordinates (or possibly on the boundary if we have equality in at least one of the inequalities). Thus if we have the vertices for the potentially contained polygon and the inequalities for the potentially containing polygon, you need only check each of the vertices against each of the iniequalities. This takes $O(nm)$ time if $n,m$ are the number of vertices. (Note that we made no use of the fact that the potentially contained polygon is convex)