A Small Result in Polygon Translational Containment

Given two polygons P_1 and P_2 and two vectors t_1 and t_2 let P_1+t_1 and P_2 + t_2 be the vector sum. That is P_1 + t_1 is the set \{x \in \mathbb R^2 | x = a + t_1 \textrm{ where } a \in P_1\}. Also let the Minkowski sum of two sets A and B be as follows A \oplus B = \{a+b | a \in A, b \in B\}. The following lemma is on page 6 of the paper “Translational Polygon Containment and Minimal Enclosure using Mathematical Programming” by V.J. Milenkovic and Karen Daniels

The lemma is as follows: The set (P_1 + t_1)\cap(P_2 + t_2) is non-empty iff t_2 - t_1 \in P_1 \oplus - P_2.

To prove the lemma we note that t_2 - t_1 \in P_1\oplus -P_2 iff t_2 - t_1 = a - b for some a \in P_1 and b \in P_2. It then follows that b+t_2 = a+t_1 for some a \in P_1 and b \in P_2. Thus b+t_2 is a point in P_2 + t_2 and since b+t_2 = a + t_1 then b+t_2 is also a point in P_1 + t_1 hence b +t_2 is in (P_1 + t_1)\cap(P_2+t_2.

One question you might have is “what is the use of the lemma?”. The answer is that (P_1+t_1) does not intersect (P_2+t_2) iff t_2 - t_1 \in \overline{P_1 \oplus -P_2}. Thus given two translations of P_1 and P_2 we have an algorithm for deciding if the translated polygons overlap.

Advertisements

Solving Tangrams Using the Java Topology Suite (jts)

I’ve been using the Java Topology Suite (jts) to try and solve the Tangram puzzle. The basic algorithm is the same as I posted previously (it’s item 3 on the list of algorithms). The JTS is much easer to use and the source code is actually readable compared to CGAL. But on the downside JTS does not enforce rigorous geometry like CGAL does. This has some downsides mainly I had to modify the basic algorithm for shape fitting.

The main issue is that when trying to fit for example a triangle, t_1, inside another polygon say s_1. We can have roundoff errors such as in the following image.

round off error image

One slightly add-hoc way to solve this issue is to multiply t_1 by a scaling factor 1+\epsilon where epsilon is a small constant. Then when subtracting the new triangle (1+\epsilon)t_1 from s_1 we won’t have the issue of a small corner of s_1 being left over. But it does mean that we subtract slightly too much area from s_1. Which could cause an issue when we try to fit say another triangle, t_2, inside of s_2=s_1/(1+\epsilon)t_1 (e.g. t_2 won’t fit). To ensure t_2 fits what we can do is create a buffer of size #pieces \cdot \epsilon around s_2 before testing if t_2 is inside of s_2. Please note that #pieces is the number of for instance triangles we’re trying to fit inside of s_1 (so in this case #pieces = 2 since we’re trying to fit t_1 and t_2 inside of s_1). With the addition of the buffer even if s_2 is slightly too small the union of s_2 and its buffer will be large enough to cover t_2. I’ve had pretty good luck using this method with the JTS library.

You can see my code at the GitHub 2dfit site.

But a new problem is that solving the tangram puzzle takes a really long time since the algorithm goes through a large number of possible solutions before finding the correct one. Even after using the heuristic of fitting the largest shapes first the algorithm still takes a lot of time (in fact I’m still waiting for it to complete while writing this post). So I’ve been thinking of possible ways to speed up the algorithm. Below I’ve listed an algorithm that might be of some help in this.

Given two simple polygons called the silhouette and the puzzle piece. What we want is the algorithm to have two possible outcomes (1) it says “does not fit” in which case the puzzle piece cannot possible fit inside the silhouette and (2) “don’t know” in which case the puzzle piece could possible fit inside the silhouette but it’s also possible that it does not fit inside the silhouette.

In the below image I’ve shown the puzzle piece, p, which is a square and the silhouette, s, which is a simple polygon.

pieces

One way to determine that the puzzle piece, p, won’t fit is to start by constructing a bounding circle around it. As in the following figure.

bounding circle

What we do is calculate the %area of the circle filled by the puzzle piece (in this case a square). I’ve done the calculation and it’s \frac{2}{\pi}. Now suppose we wanted to test if the
square would not fit in the silhouette, s. Now also suppose that we try putting the bounding circle that we used for the square on the silhouette, s, as in the following figure.

bound circle 2

As is obvious the area of the bounding circle filled by the silhouette, s, is much less than \frac{2}{\pi}. Infact if we tried all possible placements of the bounding circle on the silhouette, s, we would find that the %area of the bounding circle filled by the silhouette is always less than \frac{2}{\pi}. This implies that the square cannot fit inside the silhouette, s. Now we need to determine what placements to use of the bounding circle to let us conclude that there is no possible placement that would give an %area of \frac{2}{\pi} filled by the silhouette s.