Fitting a convex polygon into another polygon

Question

I am searching for an algorithm where I can check whether a convex polygon (shape 1) fits into another polygon (shape 2).

My first research brought me to "Packing irregular shapes". This is in my opinion a little bit overkill. I only have one container and one object.

Shape 1 is normally a convex polygon. Shape 2 can be convex, or concave.

My application: I have 3D laser scanner to measure logs, which gives me shape 2. I also have different cutting profiles from which I consider the convex hull, giving shape 1.

Now I want to check whether a cutting profile fits into my laser profile.

Answer 1

Motivation. If you would ask whether a disk B of certain radius can fit into a polygon P then there is a standard method in computational geometry: Check whether the maximum inscribed circle has a radius not smaller; see this stackoverflow answer:

The above algorithm to compute the maximum inscribed circle is quite "simple": Compute the so-called Generalized Voronoi Diagram and take the Voronoi node with largest clearance radius. (This is only motivation, just keep reading for a minute.)

In your case your Shape 2 is not a ball; well, not a Euclidean ball, to be precise. But, actually, your Shape 2, as a convex polygon B, could define a convex distance function and compute the Voronoi diagram under this polyhedral distance function. But this is more theoretical background and maybe not something you want to implementation for production code.

Those Voronoi diagrams are strongly related to computing offset curves, e.g., for tool-path planing in NC-machining. See this blog article for some discussions and the following figure:

A ball B of radius r fits into the shape P if and only if there is an offset curve at distance r. (You actually get the set of all valid centers, namely those within the offset curve at radius r.) And those offset curves can be mathematically described as a Minkowski difference, as outlined in the blog article.

Minkowski-difference. So now we can come back to your original problem. Does a convex polygon B fit within a polygon P? It does if and only if the Minkowski difference (P-B) is a non-empty set; any center out of (P-B) works as an example.

A few more details based on the figure above: Let us denote by -B = {-v : v in B} the shape B after point reflection. (Choose the origin anywhere you like; I denoted it by the little cross with 'o' for origin.) Now think of -B as the shape of a pen (blue) and you move your pen (actually the cross) along the boundary of P. You get the gray area. (This is the Minkowski sum of the boundary of P with -B.) Remove the gray area from P and you get the Minkowski difference P-B. Choose any point within P-B and place a copy of B there; it will fit within P. I placed a few copies (orange) for you.

Implementation. You can construct the gray area by considering each segment s of P individually and slide -B along it. More precisely, you place a copy of -B on each endpoint of s and find the tangents of the two copies of -B that form the boundary of the gray area:

Take the per-segment solutions and compute the union over all segments of P. Then subtract this union from P. Take a look at Clipper for an open source library that can do that for you.

What you get is not only the boolean answer whether B fits into P, but the set of all valid center for B in form of an set of polygons. Maybe this is interesting for your application, too.

If you allow for rotations of B as well then the problem gets significantly more complex, I think. Maybe you can work with some discretization of rotational angles. Maybe you find some solution in the field of robot-motion planning resp. related to the piano mover's problem in computational geometry.