【计算几何】布尔运算交并补异或

本文涉及知识点

数学 几何

求PathD及PathsD的面积

数学规则逆时针为外边界，面积为正；顺时针为内边界（孔洞），面积为负数。

两个完全相同的矩形，一个逆时针一个顺时针

usingSystem;usingSystem.Collections.Generic;usingSystem.ComponentModel;usingSystem.Data;usingSystem.Drawing;usingSystem.Linq;usingSystem.Text;usingSystem.Threading.Tasks;usingSystem.Windows.Forms;usingClipper2Lib;

PathDpath1=newPathD(newPointD[]{newPointD(0,0),newPointD(100,0),newPointD(100,100),newPointD(0,100)});PathDpath2=newPathD();path2.AddRange(path1);path2.Reverse();doublearea1=Clipper.Area(path1);doublearea2=Clipper.Area(path2);Console.WriteLine("面积一："+area1);Console.WriteLine("面积二："+area2);

运行结果符合预期。
面积一：10000
面积二：-10000

PathsDps=newPathsD();ps.Add(path1);ps.Add(path2);doublearea3=Clipper.Area(ps);Console.WriteLine("面积三："+area3);

运行结果符合预期： 面积三：0

两个逆时针矩形不重叠

PathDpath1=CreatePath(100,100,10);PathDpath2=CreatePath(200,100,10);doublearea1=Clipper.Area(path1);doublearea2=Clipper.Area(path2);Console.WriteLine("面积一："+area1);Console.WriteLine("面积二："+area2);PathsDps=newPathsD();ps.Add(path1);ps.Add(path2);doublearea3=Clipper.Area(ps);Console.WriteLine("面积三："+area3);

结果是两者之和：
面积一：400
面积二：400
面积三：800

两个完全相同的矩形（端点重合，方向相同）

PathDpath1=CreatePath(100,100,10);PathDpath2=CreatePath(100,100,10);doublearea1=Clipper.Area(path1);doublearea2=Clipper.Area(path2);Console.WriteLine("面积一："+area1);Console.WriteLine("面积二："+area2);PathsDps=newPathsD();ps.Add(path1);ps.Add(path2);doublearea3=Clipper.Area(ps);Console.WriteLine("面积三："+area3);

重叠部分重复计算：
面积一：400
面积二：400
面积三：800

不重叠矩形，一个顺时针一个逆时针

PathDpath1=CreatePath(100,100,10);PathDpath2=CreatePath(200,100,10);path2.Reverse();doublearea1=Clipper.Area(path1);doublearea2=Clipper.Area(path2);Console.WriteLine("面积一："+area1);Console.WriteLine("面积二："+area2);PathsDps=newPathsD();ps.Add(path1);ps.Add(path2);doublearea3=Clipper.Area(ps);Console.WriteLine("面积三："+area3);

面积一：400
面积二：-400
面积三：0

结论

Paths面积就是各Path面积之和。

缠绕数（Winding Number）

以区域（子区域）内任意一点为起点，任意方向做射线。边界线从右向左穿过射线：缠绕数 +1，边界线从左向右穿过射线：缠绕数 -1，缠绕数 = 所有穿越的代数和。为了实现方便，一般用水平向右的射线。

逆势针矩形

任意边界方向都在对应射线的的逆时针平面，故WN+1。

顺时针矩形

任何边界方向都在对应射线的顺时针平面，故WN-1。

凹多边形

向左的射线和一条边界相交，边界在射线的逆时针半平面。故WN+1。
向右的射线和五条边界相交，3条边界在射线的逆时针半平面，2条在射线的顺时针半平面，故WN+3-2=1。

向右水平的射线

令射线方向 v 1 , 边界方向 v 2 ，如果 v 2 在 v 1 的逆时针半平面，则 v 1 × v 2 > 0 令射线方向v_1,边界方向v_2，如果v2在v1的逆时针半平面，则v_1 \times v_2 > 0令射线方向v1​,边界方向v2​，如果v2在v1的逆时针半平面，则v1​×v2​>0,假定射线水平向右，及v 1 = ( 1 , 0 ) ，则 v 1 × v 2 = v 2 . y v_1=(1,0)，则v_1 \times v_2 = v_2.yv1​=(1,0)，则v1​×v2​=v2​.y。

FillType 与布尔运算

publicenumFillRule{EvenOdd=0,NonZero=1,Positive=2,Negative=3}

EvenOdd (奇偶):WN为奇数是内部。和Path是逆时针还是顺时针无关。假定将某个Path改变方向，x个交点由-1变成1，y个交点由1变成-1。则WN变化为：2x-2y，是偶数，故WN的奇偶性不变。
NonZero(非0）：WN不是0是内部。和Path的方向有关。逆时针矩形内部有另外一个逆时针矩形，内部矩形WN=2。如果将任何一个矩形反向，则内部矩形的WN为0。
Positive(正数):WN>0时，是内部。
Negative(负数):WN<0时，是内部。
运算类型决定最终保留哪些区域。例如：
Intersection（交集）：保留 WC = +2 的区域。
Union（并集）：保留 WC > 0 的区域。
Difference（差集）：保留 WC = +1 的区域。
XOR（异或）：保留 WC=1 的区域。
交集并集异或都内部WC都是1，外包都是0。
差集，被减数内部是1,减数内部是-1，被减数减数外部是0。

一个正方形的并

path1逆时针，path2 顺时针。Paths哪些块是内部，由FillType和WN决定。

奇偶

publicForm1(){InitializeComponent();PathDpath1=CreatePath(0,0,100);PathDpath2=CreatePath(0,0,10);path2.Reverse();FillRulefr=FillRule.EvenOdd;varps1=Clipper.Union(newPathsD(newPathD[]{path1}),fr);varps2=Clipper.Union(newPathsD(newPathD[]{path2}),fr);doublearea3=Clipper.Area(ps1);doublearea4=Clipper.Area(ps2);Console.WriteLine("FillRule:"+fr);Console.WriteLine("面积三："+area3);Console.WriteLine("面积四："+area4);}//创建正方形,点集合逆时针顺序PathDCreatePath(doublexCenter,doubleyCenter,doublehalfLen){PointD[]pts={newPointD(xCenter-halfLen,yCenter-halfLen),newPointD(xCenter+halfLen,yCenter-halfLen),newPointD(xCenter+halfLen,yCenter+halfLen),newPointD(xCenter-halfLen,yCenter+halfLen)};returnnewPathD(pts);}

运行结果：
FillRule:EvenOdd
面积三：40000
面积四：400
path1的WN=1,path2的WN=-1，都是奇数，故都是内部。

非0

只修改一行代码

FillRulefr=FillRule.NonZero;

FillRule:NonZero
面积三：40000
面积四：400
± 1 \pm 1±1都非0，故都是内部。

正数

FillRulefr=FillRule.Positive;

FillRule:Positive
面积三：40000
面积四：0

负数

FillRulefr=FillRule.Negative;

FillRule:Negative
面积三：0
面积四：400

1个paths 2个path的并

path1逆时针矩形，path2逆时针矩形，path2完全在path1内部。path2反转后形成path3，即path3顺时针。
path2内部：WN=2，path3内部：WN=0;path1内部非空洞，WN=1。

奇偶

publicForm1(){InitializeComponent();PathDpath1=CreatePath(0,0,100);PathDpath2=CreatePath(0,0,10);PathDpath3=CreatePath(0,0,10);path3.Reverse();Console.WriteLine("面积一："+Clipper.Area(path1));Console.WriteLine("面积二："+Clipper.Area(path2));Console.WriteLine("面积三："+Clipper.Area(path3));FillRulefr=FillRule.EvenOdd;varps12=Clipper.Union(newPathsD(newPathsD(){path1,path2}),fr);varps13=Clipper.Union(newPathsD(newPathsD(){path1,path3}),fr);Console.WriteLine(""+fr);Console.WriteLine("面积一二："+Clipper.Area(ps12));Console.WriteLine("面积一三："+Clipper.Area(ps13));}//创建正方形,点集合逆时针顺序PathDCreatePath(doublexCenter,doubleyCenter,doublehalfLen){PointD[]pts={newPointD(xCenter-halfLen,yCenter-halfLen),newPointD(xCenter+halfLen,yCenter-halfLen),newPointD(xCenter+halfLen,yCenter+halfLen),newPointD(xCenter-halfLen,yCenter+halfLen)};returnnewPathD(pts);}

面积一：40000
面积二：400
面积三：-400
EvenOdd
面积一二：39600
面积一三：39600

非零

只修改一行。

FillRulefr=FillRule.NonZero;

面积一：40000
面积二：400
面积三：-400
NonZero
面积一二：40000
面积一三：39600

正数

FillRulefr=FillRule.Positive;

面积一：40000
面积二：400
面积三：-400
Positive
面积一二：40000
面积一三：39600

负数

FillRulefr=FillRule.Negative;

面积一：40000
面积二：400
面积三：-400
Negative
面积一二：0
面积一三：0

两个paths的交集

path1,path2的WN=1，path3的WN=-1

奇偶

PathDpath1=CreatePath(0,0,100);PathDpath2=CreatePath(0,0,10);PathDpath3=CreatePath(0,0,10);path3.Reverse();Console.WriteLine("面积一："+Clipper.Area(path1));Console.WriteLine("面积二："+Clipper.Area(path2));Console.WriteLine("面积三："+Clipper.Area(path3));FillRulefr=FillRule.EvenOdd;varps12=Clipper.Intersect(newPathsD(newPathsD(){path1}),newPathsD(newPathsD(){path2}),fr);varps13=Clipper.Intersect(newPathsD(newPathsD(){path1}),newPathsD(newPathsD(){path3}),fr);Console.WriteLine(""+fr);Console.WriteLine("面积一二："+Clipper.Area(ps12));Console.WriteLine("面积一三："+Clipper.Area(ps13));

面积一：40000
面积二：400
面积三：-400
EvenOdd
面积一二：400
面积一三：400

非0

FillRulefr=FillRule.NonZero;

面积一：40000
面积二：400
面积三：-400
NonZero
面积一二：400
面积一三：400

正数

面积一：40000
面积二：400
面积三：-400
Positive
面积一二：400
面积一三：0

负数

面积一：40000
面积二：400
面积三：-400
Negative
面积一二：0
面积一三：0

两个paths的差集

奇偶

面积一：40000
面积二：400
面积三：-400
EvenOdd
面积一二：39600
面积一三：39600

非0

面积一：40000
面积二：400
面积三：-400
NonZero
面积一二：39600
面积一三：39600

正数

面积一：40000
面积二：400
面积三：-400
Positive
面积一二：39600

负数

面积一：40000
面积二：400
面积三：-400
Negative
面积一二：0
面积一三：0

两个paths的交集 异或

奇偶

面积一：40000
面积二：400
面积三：-400
EvenOdd
面积一二：39600
面积一三：39600

非0

面积一：40000
面积二：400
面积三：-400
NonZero
面积一二：39600
面积一三：39600

正数

面积一：40000
面积二：400
面积三：-400
Positive
面积一二：39600
面积一三：40000

负数

面积一：40000
面积二：400
面积三：-400
Negative
面积一二：0
面积一三：400

返回值

Clipper的返回值，可以认为是Even-Odd或者Non-Zero中任意一种，即兼容这两种填充方式。

演示工具

演示工具基于Cad，支持Cad2013及更高版本。
亲士库版本：2026.9.4
Cliper库版本：2.0.0.0
点击下载亲士数学演示工具箱
如果不会操作，请看视频：https://edu.csdn.net/course/detail/41418
建议用工具尝试以下情况：
四种填充方式
部分多边形相离，部分多边形相切，部分多边形相离。
部分多边形是凸多边形，部分是凹多边形。
由于布尔运算容易理解，故工具只演示一个Path的并。
如果不想可视频或操作，可直接看图片。

奇偶模式的并集

01模式的并集

正数并集

负数并集

并集也可能为空。


上图红色三角形WN是1。黄色三角形是0，穿过三角形是-1,穿过矩形是1。红色矩形是1。全部不是负数。

扩展阅读

测试环境

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