【计算几何】闵可夫斯基差演示

本文涉及知识点

数学 几何

演示工具

演示工具基于Cad，支持Cad2013及更高版本。 亲士库版本：2026.9.4 Cliper库版本：2.0.0.0 点击下载亲士数学演示工具箱

相关定义

闵可夫斯基和：数学定义：

A

⊕

B

=

{

a

+

b

∣

a

∈

A

,

b

∈

B

}

A \\oplus B =\\{a+b \\mid a \\in A,b \\in B \\}

A⊕B={a+b∣a∈A,b∈B} 直观理解：将B的副本放置到A的每个点上，取并集。 形态学（膨胀腐蚀、开闭操作)和集合论的闵可夫斯基差和计算几何（机器人学)的闵可夫斯基差不同。 计算几何的闵可夫斯基差：

A

⊖

B

=

{

a

−

b

∣

a

∈

A

,

b

∈

B

}

A \\ominus B=\\{a – b \\mid a\\in A,b\\in B\\}

A⊖B={a−b∣a∈A,b∈B}。

主要用途

临界多边形(NFP)–排样算法的核心

N

F

P

(

P

,

Q

)

=

P

⊕

(

−

Q

)

NFP(P,Q)=P\\oplus (-Q)

NFP(P,Q)=P⊕(−Q)。它表示零件P绕着Q滑动时，参考点的轨迹。

碰撞检测（配置空间障碍)

A

⊕

(

−

B

)

A \\oplus (-B)

A⊕(−B)定义了配置空间的障碍物区域。

多边形偏移

对多边形膨胀(向外偏移)本质求

P

⊖

圆盘。

P \\ominus 圆盘。

P⊖圆盘。

操作说明

一，选择闵可夫斯基差的被减数(模板图像)。 二，选择闵可夫斯基的减数。 注意：只能选择多义线，无论多义线是否闭合都当闭合处理。 三，计算出闵可夫斯基差。 四，将闵可夫斯基差的结果转成闭合多义线，逆时针红色，顺时针黄色。

代码

using System;
using System.Collections.Generic;
using Autodesk.AutoCAD.ApplicationServices;
using Autodesk.AutoCAD.DatabaseServices;
using Autodesk.AutoCAD.EditorInput;
using Autodesk.AutoCAD.Geometry;
using Autodesk.AutoCAD.Runtime;
using Clipper2Lib;
using QinShiZACad;
using QinShiMath;
using QinShiBase;

[CommandMethod("MinkowskiDiff")]
public void MinkowskiDiff()
{
Minkowski("闵可夫斯基差", (p1, p2) => Clipper.MinkowskiDiff(p1, p2,true));
}
[CommandMethod("MinkowskiSum")]
public void MinkowskiSum()
{
Minkowski("闵可夫斯基和", (p1, p2) => Clipper.MinkowskiSum(p1, p2, true));
}
void Minkowski(string strName, MinkowskiFun fun)
{
QinShiZACad.CSelAEntity sel1 = new CSelAEntity($"请选择一个多义线做为{strName}的被减数(模板图像)\\n");
var pr1 = sel1.Sel();
if (pr1.Status != PromptStatus.OK)
{
return;
}
QinShiZACad.CSelAEntity sel2 = new CSelAEntity($"请选择一个多义线做为{strName}的减数\\n");
var pr2 = sel2.Sel();
if (pr2.Status != PromptStatus.OK)
{
return;
}

Polyline pl1, pl2;
using (var tr = CadBase.GetDefaultDatabase().TransactionManager.StartTransaction())
{
pl1 = tr.GetObject(pr1.ObjectId, OpenMode.ForRead) as Polyline;
pl2 = tr.GetObject(pr2.ObjectId, OpenMode.ForRead) as Polyline;
}
if (null == pl1) { return; }
if (null == pl2) { return; }
PathD path1 = PolylineToPath(pl1);
PathD path2 = PolylineToPath(pl2);
PathsD path3 = fun(path1, path2);

PathD PolylineToPath(Polyline pl)
{
PathD path = new PathD();
for (int i = 0; i < pl.NumberOfVertices; i++)
{
var pt = pl.GetPoint2dAt(i);
path.Add(new PointD(pt.X, pt.Y));
}
return path;
}
var pls = path3.ToPolylines();
for (int i = 0; i < Math.Min(7, pls.Count); i++)
{
double area = Clipper.Area(path3[i]);
int iColor = 0;
if (Math.Abs(area) < 1e-9)
{//退化情况
iColor = 0;
}
else if (area > 0)
{
iColor = 1;
}
else
{
iColor = 2;
}
pls[i].ColorIndex = iColor;//外边界红色，孔洞黄色
}
CadBase.AddEnitys(pls.ToArray(), "0", CadBase.GetDefaultDatabase());
}
delegate PathsD MinkowskiFun(PathD path1, PathD path2);

public static class PolylineExtensions2
{
/// <summary>
/// PathD 转回 Polyline（不关联数据库）
/// </summary>
public static Polyline ToPolyline(this PathD path, double tolerance = 1e-4)
{
Polyline pl = new Polyline();
for (int i = 0; i < path.Count; i++)
{
PointD pt = path[i];
pl.AddVertexAt(i, new Point2d(pt.x, pt.y), 0, 0, 0);
}
// 如果 PathD 首尾点足够接近（差值小于容差），则认为它是闭合的
if (path.Count > 1)
{
PointD first = path[0];
PointD last = path[path.Count – 1];
//if (Math.Abs(first.x – last.x) < tolerance &&
// Math.Abs(first.y – last.y) < tolerance)
//{
// pl.Closed = true;
//}
// 只有至少3个点且面积非零的路径才视为有效闭合多边形
if (path.Count >= 3 && Math.Abs(Clipper.Area(path)) > 1e-6)
{
pl.Closed = true;
}
}
return pl;
}

/// <summary>
/// 将 PathsD 转换为 Polyline 列表
/// </summary>
public static List<Polyline> ToPolylines(this PathsD paths)
{
var polylines = new List<Polyline>();
foreach (var path in paths)
{
// 调用已有的单个 PathD → Polyline 扩展方法
polylines.Add(path.ToPolyline());
}
return polylines;
}
}

错误解法

直接通过前三个点的差乘判断是逆时针或顺序时针是错误的，一：三点共线。二，可能是凹角。用clipper库的有向面积判断更合理。

查看视频

https://edu.csdn.net/course/detail/41418 如果视频审核中，可以看图。 将原点和被减数一起平移，原点在闵可夫斯基差上，则被减数和减数相切。

边长100的正方形，左下角是圆点，作为模板图像(被减数)

下面部分闵可夫斯基差的颜色不对，工具是正确的。

矩形

原图 效果图：黄色是结果

凹多边形

原图

效果图：黄色是结果

凸多边形

原图

效果图：红色黄色是结果

正100多边形模拟圆作为模板图像

多边形是否重叠

如果两个多边形P、Q重叠，则其闵可夫斯基差D必定包括原点。如果两个多边形不重叠，则P与Q最小距离等于原点到D的最小距离。

扩展阅读

测试环境

操作系统：win7 开发环境： VS2019 C++17 或者 操作系统：win10 开发环境： VS2022 C++17 如无特殊说明，本算法用**C++**实现。