I have a convex polygon (Polygon A ) and a concave polygon (Polygon B). I want to figure out whether the convex polygon given a rotational angle for the convex polygon , fits inside the concave polygon given the convex polygon can rotate 360 degrees inside the concave polygon .
Naive way of computing this .
Initialise the polygon A with the midpoint of Polygon B as origin . For every rotational angle of convex polygon compute the following
Step 1: Compute points correspond to convex polygon with rotational
angle . Put all the points of both rotated convex polygon and
concave polygon in one set
Step 2: Find the convex polygon using grahamscan (Convex Hull) with the new set of points.
Step 3: Now you have a big convex polygon which will contain both polygons .That means you have vertex of the newly created polygon. Let's call it Polygon C
Step 4: Now check if polygon C and Polygon B are same
with same set of vertex points if yes that means Polygon B contains
Polygon A
One potential optimisation might be to utilise the angle of rotational symmetry but I am not sure if we can use this . Since we are dealing with convex polygons we are bound to find the first symmetry at (360/n) degree . Where n is the number of vertices .
Symmetry of rotation for a square example
Can we map angle of rotation say 1 degree rotation correspond to 91 degree rotation in case of the above example and be done with the process up to the rotational angle of symmetry ?
Any other efficient way of solving this problem without iterating through all the angles of rotation . Any pointers would be appreciated .