文章目录

  • 背景
  • 一、Clipper2中的术语（terminology）
    • 1. 裁剪Clipping
    • 2. subject/clip
    • 3. segment
    • 4. Paths
    • 5. Simple polygons
    • 6. Complex polygons
    • 7. Polygon holes
    • 8. Filling region
    • 9. Filling rule
    • 10. Winding number
    • 11. Touching
    • 12. Polygon offseting
      • 1. Join type
      • 2. End type
  • 二、Clipper2 中的一些注意事项
    • 1. polygon touching problem
    • 2. Self-intersection polygon
    • 3. Rounding
    • 4. Self-intersection artefacts
  • Reference

背景

Clipper是一个开源的计算几何图形库，支持图形的交，并，补以及亦或(boolean)操作，同时也支持图形的变大/变小(sizing)操作。

The Clipper library performs clipping and offsetting for both lines and polygons. All four boolean clipping operations are supported – intersection, union, difference and exclusive-or. Polygons can be of any shape including self-intersecting polygons.

Clipper 是由Angus Johnson于2010年发布，2022年其再次发布了一个对于Clipper的改进版，这样把2010年的版本叫做Clipper1，现在的版本叫做Clipper2。

一、Clipper2中的术语（terminology）

Clipper2中有一些基本的术语，它们是Clipper2的核心：

1. 裁剪Clipping

clipping最初是指用某个clip window对某个image进行裁剪，只留下clip window内部的部分image，相当于对两个图形求交集。后来clipping(裁剪)泛化为不仅仅是裁剪(intersection), 还包括union, difference, XOR等boolean操作。

2. subject/clip

image 等被裁剪对象叫做subject, clip window等称为clip

3. segment

segment就是线段，由相连的两点(point/vertice)表示

4. Paths

Paths是由一系列segment构成的路径
Open paths是指起点和终点不相连的Paths, 也叫做polylines
Close paths是指起点和终点相连的Paths，通常叫做polygon
subject可能是Open paths, 也可能是closed paths
clip只能是closed paths.

5. Simple polygons

由一条不自交(self-intersect)的Close Paths构成的图形称为简单多边形(simple polygons)

6. Complex polygons

如果Closed paths自相交，或者由多条Paths组成的polygons, 称为复杂多边形(complex polygons)

7. Polygon holes

Polygon内部不被填充的部分成为polygon holes， holes通常是由位于outer polygon contour内部的inner polygon contour 组成。

8. Filling region

简单多变形(simple polygons)的填充区域是固定的，复杂多变形(complex polygons)的填充区域(Filling region)依赖填充规则(Filling rule)，填充规则决定什么是hole, 什么不是hole, hole不填充，不属于填充区域，除掉hole的部分都属于填充区域。

9. Filling rule

通过填充，可以表明哪些区域是位于Closed path的内部，哪些区域是位于Closed path的外部。Clipper2支持4种填充规则(Filling rule)，分别是：EvenOdd, NonZero, Positive, Negative，其中EvenOdd规则是基于射线法确定，NonZero, Positive, Negative是基于图形的winding number确定。

  • EvenOdd: 也称交替填充( alternate filling)，从图形的外部一点引一条射线，第一次相交Paths, 相应的区域填充，第二次相交的Paths，相应区域不填充，第三次相交Paths，相应区域填充，依次类推
  • NonZero: Winding number不为0的部分填充
  • Positive: Winding number 大于0的部分填充
  • Negative: Winding number 小于0的部分填充

EvenOdd规则和Paths中edge direction和Winding number无关，其它三个与Paths中edge direction和Winding number相关。

10. Winding number

Winding number可以理解为绕圈数，Wiki给出了一个一个解释：

In mathematics, the winding number or winding index of a closed curve in the plane around a given point is an integer representing the total number of times that curve travels counterclockwise around the point

下面图片展示了P点处的Winding number，一个比较形象的解释是：假设一个人站在P点，转动身体使人的视线跟随曲线方向，当目光把整个曲线扫描一遍，身体转动的圈数等于winding number的绝对值。 如果逆时针转，Winding number为负，反之为正。
Clipper2中的术语和基本概念-编程之家
上面的方法不太直观，这里给出了另外一个比较直观的方法：从图形的左边外部和需要计算winding number的子区域的一点，比如P所在的区域画一条线，最外部的winding number 是0， 当虚线延长到P点的过程中，如果图形由右至左穿过虚线那么，winding number加1，如果图形由左至右穿过虚线那么，winding number减1，这样任何一点的winding number就可以计算出来了。
Clipper2中的术语和基本概念-编程之家
下面是来自Clipper2中几个计算winding number的进一步的例子:
Clipper2中的术语和基本概念-编程之家
以上面五角星图形为例子，根据四种填充规则得到的图形如下：
Clipper2中的术语和基本概念-编程之家

11. Touching

在Closed Paths中，segments通常被叫做edge．

  • Edge touching是指edge共线(collinear)或重合(overlap)
  • Polygon touching是指当两个polygon有Edge touching

12. Polygon offseting

Polygon offseting就是将polygon变大或者变小，用Clipper2上的定义是指：

Geometric offsetting refers to the process of creating parallel curves that are offset a specified distance from their starting positions.

Clipper2的offseting支持(inflating/deflating)，不支持单方向的offseting，比如horizontal or vertical offseting。
对于Open paths or Closed paths，Clipper都支持offseting
Clipper2中的术语和基本概念-编程之家

1. Join type

做Polygon offseting时，edge的连接类型(Join type)可能是Square、Round、Miter，这主要是对连接处非90度的情况进行处理的。它们分别的功能是：

  • Square：当edge的join处，角度小于90度时，当inflate/deflate polygon时，会将尖角切掉，并且添加一条线段，添加的线段到join vertex的距离是inflate/deflate的offset。
  • Round: 当edge的join处，角度小于90度时，当inflate/deflate polygon时，会将尖角切掉，并且添加一条凸型曲线，添加的曲线到join vertex的距离是inflate/deflate的offset。
  • Miter: 当edge的join处，角度小于90度时，当inflate/deflate polygon时，会将尖角切掉，并且添加一条线段，添加的线段到join vertex的距离是inflate/deflate的offset * miter, miter的默认值是2，当miter为无穷大时，这种情况下inflate/deflate将保留原来图形的尖角(spike)。

2. End type

当进行做Polygon offseting时，由于input可能是Open paths or Closed paths，End type将指明如何对待input的ending vertices.

  • Polygon: output result path将会被当做polygon(首尾相连，填充内部）
  • Join： output result path 将会被当作polyline(首尾相连，内部不填充）–not clear
  • Square： ends 延长offset长度，采用Square的方法截短
  • Round：ends 延长offset长度，采用Square的方法截短
  • Butt: ends不延长，采用Square方法截断

当对Polygons进行inflate/deflate时，EndType必须选择 EndType.Polygon，如果选择别的类型，将会支队polygon的outline进行inflate/deflate。这里有个例子。

二、Clipper2 中的一些注意事项

1. polygon touching problem

由于subject可能是Open paths，也可能是closed paths，clip只能是closed paths．
那么我们有时可能是clip closed paths,有时是clip open paths.

用的最多的是clip closed paths，这种情况下得到的外层contour一般是逆时针的(anti-clockwise/counter-clockwise)，内层holes是顺时针的(clockwise)，这意味着用EvenOdd填充方法或NonZero填充方法得到的contour是一样的。

clip closed paths最大的一个问题是得到的结果可能还有polygon touching的情况，如果遇到这样的情况，作者的建议是再调用一次union，那么得到的应该是最简(simplest/clean)形式的polygon。

2. Self-intersection polygon

  • boolean操作支持self-intersection polygon
  • offseting操作不支持self-intersection polygon

3. Rounding

在计算几何中，由于坐标是由离散的实数表示的(不管时整型还是浮点数），那么，从理论上来说，如果我们需要得到确切的坐标（比如两条线的交点），几何计算就不可能是numerically robust的。

Clipper2预期到了坐标的不精确，管理这种不精确性，做到了numerically robust，主要是通过以下几点：

  1. 用整型表示所有的内部坐标(by using integer variables rather than floats, maximum imprecision is constant. This simplifies differentiating significant from insignificant imprecision）。
  2. 使用算法来解决由于不精确性带来的坐标不是严格不等的问题
  3. 内部计算对所有的结果进行round

4. Self-intersection artefacts

在做union操作时，可能会有自相交的局部图形存在：
Clipper2中的术语和基本概念-编程之家

Reference

  1. http://www.angusj.com/clipper2/Docs/Overview.htm
  2. http://www.angusj.com/clipper2/Docs/Rounding.htm