一、概述

官方定義：兩個圖形A,B的閔可夫斯基和C={a+b|a∈A,b∈B}
通俗一點：從原點向圖形A內部的每一個點做向量，將圖形B沿每個向量移動，所有的最終位置的并便是閔可夫斯基和（具有交換律）

?

例如，平面上有兩個三角形，其坐標分別為A={(1,0),(0,1),(0,-1)}及B?= {(0, 0), (1, 1), (1, ?1)}，則其閔可夫斯基和為A?+?B?= {(1, 0), (2, 1), (2, ?1), (0, 1), (1, 2), (1, 0), (0, ?1), (1, 0), (1, ?2)}。若推廣至流形的連續集，閔可夫斯基和從幾何上的直觀體現即是A集合沿B的邊際連續運動一周掃過的區域與B集合本身的并集，也可以使B沿著A的邊界連續運動掃過區域與A自身的并集。

?

?

本文只討論凸包的閔可夫斯基和。如下圖，粉色區域便是三角形和一個不規則四邊形的閔可夫斯基和

?

二、怎么求

閔可夫斯基和的邊是由兩凸包構成的
也就是說把兩凸包的邊極角排序后直接順次連起來就是閔可夫斯基和

?

凸包肯定會存在于A的凸包+B的凸包上。

?我們可以給這個兩個點集做一次凸包，然后再從這兩個點集中分別x最小中y最小的點開始。

? ? ? 出來之后，可能是這樣的。

?

?

?就是M點開始，我們進行找點運動。

? ? ? 可以感性理解：下一個凸包上的點是或者。前提是已經做好凸包，也就是說，點是逆時針排布的。

? ? ? 所以這樣，我們就可以做出來了。?

?

三、算法

求凸包之間的閔可夫斯基和的方法。
把兩個凸包的每一條向量都摳出來，按照極角序排序構成新凸包即可。
注意點和向量的去重(向量相同斜率去重)。

還有個地方可以提一下：求多個凸包的閔可夫斯基和的時候可以直接全把邊拿出來一塊求，沒有必要兩個兩個求。
具體實現的時候，找出最高且最靠左的點。

先把這個點加入答案，從這個點開始把所有向量遍歷一遍，最后去掉最后一個點即可(最后這個點會和第一個點重合)。
下面是C++的代碼實現：

pot P={-inf,-inf},Q={-inf,-inf},R={-inf,-inf};n=read(); for(int i=1;i<=n;i++){a[i].x=read();a[i].y=read();if(dcmp(a[i].y-P.y)==0&&dcmp(a[i].x-P.x)<0)P=a[i];if(dcmp(a[i].y-P.y)>0)P=a[i];if(i!=1)f[++cnt]=a[i]-a[i-1];if(i==n)f[++cnt]=a[1]-a[i];}n=read();for(int i=1;i<=n;i++){b[i].x=read();b[i].y=read();if(dcmp(b[i].y-Q.y)==0&&dcmp(b[i].x-Q.x)<0)Q=b[i];if(dcmp(b[i].y-Q.y)>0)Q=b[i];if(i!=1)f[++cnt]=b[i]-b[i-1];if(i==n)f[++cnt]=b[1]-b[i];}n=read();for(int i=1;i<=n;i++){c[i].x=read();c[i].y=read();if(dcmp(c[i].y-R.y)==0&&dcmp(c[i].x-R.x)<0)R=c[i];if(dcmp(c[i].y-R.y)>0)R=c[i];if(i!=1)f[++cnt]=c[i]-c[i-1];if(i==n)f[++cnt]=c[1]-c[i];}sort(f+1,f+cnt+1,cmp);pot k=P+Q+R;p[++tot]=k;for(int i=1;i<=cnt;i++){k=k+f[i];if(i!=cnt&&dcmp(f[i].x*f[i+1].y-f[i].y*f[i+1].x)==0)continue;p[++tot]=k;}tot--;
k=p[1];

?

轉載于:https://www.cnblogs.com/icmzn/p/10754758.html

總結

以上是生活随笔為你收集整理的闵可夫斯基和（Mincowsky sum）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。