[HELP] A problem related to: minkowski sum of two simple polygon

Revision en4, by steinum, 2021-05-18 14:59:58

I was trying to solve this problem : cf-497D

My solution idea : let $$$R_d(p) = p'$$$ where $$$p'$$$ is the new location of point $$$p$$$ if we rotate it $$$d$$$ degree counter-clockwise with respect to $$$(0,0)$$$.

Hence, for some point $$$a \in A$$$ and $$$b \in B$$$ we can write $$$R_d(a-p)+p = R_d(b-q)+q$$$.

$$$R_d(a-p)+p = R_d(b-q)+q$$$

$$$\Longrightarrow R_d(a)-R_d(p)+p = R_d(b)-R_d(q)+q$$$ [R_d() is actually a cross/dot function , hence we can separate it]

$$$\Longrightarrow p-q - R_d(p) + R_d(q)= R_d(b)-R_d(a)$$$

$$$\Longrightarrow (p-q) \frac{R_d - 1}{R_d}= a-b$$$

Here , $$$(p-q) \frac{R_d - 1}{R_d}$$$ actually represent a circle($$$C$$$) centered $$$p-q$$$ and radius = $$$|p-q|$$$.

And

Unable to parse markup [type=CF_MATHJAX]

= Minkowski sum of A and (-B) [if we consider all $$$a$$$ and all $$$b$$$ ].

Hence, the problem turns into, checking if circle $$$C$$$ intersect polygon A-B or not.

My first idea was to triangulate $$$A$$$ and $$$-B$$$ then calculate the Minkowski sum of each pair, then check if the polygon(sum) intersect with circle $$$C$$$ or not.

I've written this code. I used the triangulation method mentioned in Computational geometry algorithms and applications-Springer-Verlag Berlin Heidelberg (2008) [page: 49]. But got WA on test 7.

Then I change my triangulation algorithm and use the Ear clipping method mentioned here. Here is my implementation($$$O(n^3)$$$). But again got WA on case 31.

I've read the editorial, and without triangulation, just take each pair of edge(one from $$$A$$$ and another one from $$$B$$$) and Minkowski sum them and got AC. My code.

Do we only need the borderline of the polygon here in this problem ? or my both triangulation code is wrong. Can you help me figure out, what have I done wrong, in my both code? And please share your triangulation code(both $$$n^2$$$ and $$$nlogn$$$ [with line sweep]).

Tags minkowski sum, triangulation, computational geometry,

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English steinum 2021-05-18 14:59:58 7
en3 English steinum 2021-05-17 18:03:33 14 Tiny change: '$ degree ccw with resp' -> '$ degree counter-clockwise with resp'
en2 English steinum 2021-05-15 17:20:47 1 Tiny change: 'nd all $b$].\n\nHenc' -> 'nd all $b$ ].\n\nHenc'
en1 English steinum 2021-05-15 17:18:04 2096 Initial revision (published)