F. Martinez 2008算法处理重叠边缘(不像格雷纳-霍曼)，但还是有点轻微。goofiness。让我们一劳永逸地解决这个问题。
再来看看问题
给定两个多边形
如何计算不同的布尔运算？
多边形表示
首先，我们需要选择一个好的多边形表达方法
你的第一直觉可能是一个简单的点数组
var poly1 = [ [0,0], [100,0], [50,100] ]; 我认为这是错误的。一个更强大的多边形定义是一个区域列表以及一个反转标识
var poly1 = { regions: [ [ [350，60]，[480，200]，[180，60] ], [ [180，60]，[500，60]，[180，220] ] ], inverted: false };该inverted标志对算法是免费的，所以我们不妨包括它.
由于布尔运算的结果是一个区域列表，因此定义多个区域的多边形非常重要。这意味着我们的切割算法将返回它消耗的相同内容。
即使是简单的布尔运算也会产生多个区域的自然结果
事实证明，算法定义多个区域的多边形基本上是免费的。所以别担心
线段
F. Martinez paper关键观察之一是根据线段进行思考。
这是完全明显的，但请记住，我们之前的算法是基于交叉点——所以这只是事后证明。
线段定义为不要和任何东西相交线段从不重叠，仅端点相互连接
底线只分为五部分
线段的某些部分只属于红色多边形，或两个多边形，或者有些线段只存在于交叉点之间，这并不重要——关键是只有五个线段
不管源数据中有什么，训练你的眼睛都能看到线段.
线段注释
既然我们从线段的角度看事情，我们可以想象线段的一侧是多边形内还是外来注释线段.
实心圆表示线段的一侧是多边形的内部
当我们看到两个重叠的多边形时，我们可以想象每个边缘的情况
如果你能理解上图，你就有足够的洞察力来推导整个算法.
线交点
不幸的是，事情会变得更加复杂。我们需要找到所有交点的顶点.
您可以测试每对线来检查两个多边形是否有交叉线。当然，这可能有点慢，但那又怎样呢？
F. Martinez paper另一个关键观点是的，如果我们使用它Bentley-Ottmann algorithm检测线之间的交叉点，然后我们可以利用同时，计算线段填写注释
这是一个非常聪明的观察……但这意味着我们需要使我们的交叉检测相当复杂.
使用该技术的另一个优点是，它比依次测试每个边缘快得多，特别是随着线段数的增加.
垂直扫描线
为了计算交点，我们假设我们正在从左到右扫描一条垂直线
在任何给定时刻，我们都可以想象一堆与垂直线相交的线：
堆栈中的粗线（A、B、C、D)
我们称这个堆栈为扫描的状态。顺序很重要——状态总是从上到下顺序
那么:状态堆栈的内容什么时候变？
仔细想想，状态只会在关键时刻改变
状态变化的关键时刻
如果您查看关键时刻中间创建的通道，您会注意到状态始终相同——通道中的多边形线从上到下始终保持相同的顺序.
那这些关键时刻是什么时候？其实很简单。
随着垂直线从左到右扫描，当新线、旧线消失或垂直线扫描交叉点时，状态会发生变化.
事件
因此，即使我们将垂直线视为扫描，但事实上，我们只关心扫描这条假想线时发生的事件
每次事件当它发生时，我们都会改变状态
事件分为三种:
1. 新行被添加到状态（
旧行从状态中删除（
注意和事件从左到右排序，因为这是垂直线扫描的方向。忽略输入顺序.
分解交叉点
Bentley-Ottmann 算法的关键观点是，当我们向状态添加一条新线时，我们只需要检查正上下线之间的交叉点.
当我们点击 B 行的我们将计算事件 status 中的插入点不实际插入.
我们用这个插入点来检查谁 B 线的上下.
如果有交点，我们在交点处拆分两条相交线-再创造四个事件
什么是四个新事件？
1.A 最左侧段的
.2.B 最左侧段的
3.A 最右侧段的
4B 最右侧段的
然后，为了继续我们的垂直扫描，我们将 A 最左线段保持在状态，并将B的最左线段插入状态.
需要注意的是，我们不会保持最右边的段落。事件负责。这很重要，因为最右边的线段可能与更多的线相交，所以我们需要进一步检查它们
说服自己这个过程是有效的，因为它只会从这里变得更加复杂.
处理垂直线
我们应该如何处理垂直线和事件……这显然是我们做不到的。.
只要我们保持一致，最后没关系。事件将是底部的点，将是最顶部的.
这意味着你可以从左到右扫描垂直线，但一旦到达某个位置，它就会从下到上扫描
处理重合线
当线直接位于对方之上时，它们是重叠的。它比你想象的要多.
有六种可能：
你可能会认为会有更多的情况— 比如蓝色的左顶点在红色的左顶点的左边呢？
但这是不可能的。如果是这样的话，蓝线会在红线之前处理，所以只会翻转颜色……但逻辑将与已列出的案例完全相同.
我们的基本策略还是一样的，但还有一个问题:
当两个线段完全相同时，我们需要以某种方式合并填写注释，并扔掉其中一个。请记住，带注释的线段是我们理想的表示，它们从不重叠.
因此，我们仍然会像往常一样拆分，但我们必须注意完全重叠的结果线段.
例如，对于案例5，我们将在蓝线的左上角分红线，在红线的右上角分红线，然后继续处理。重叠段（通过案例）将被检测到未来的事件 1)组合执行线段.
这有点棘手，但还不错.
事件结束后的交叉点
最后一种情况可能会让你失望：
当我们从状态中移除一段时，被移除段周围的两段在状态中相邻。因此，我们需要检查它们的交叉点.
例如，考虑
状态将从： 开始(A, B, C, D, E)
然后它会处理B 和 C的事件(顺序无关紧要)导致新状态:(A, D, E)
如果我们只在插入新线段时寻找交集，那么我们就会错过 A 和 D 它们之间的交集。因此，我们必须记住，当我们从状态中删除线段以检查新相邻段之间的交集时.
交叉点代码
在继续之前，让我们看看执行此线扫描算法的一些代码。我们将添加到这个代码中，以便以后计算填写注释——但最好在我们进一步复杂之前熟悉算法.
请注意，我正在从本教程中删除真实代码库中的一些细节，以突出显示算法本身.
例如，在现实中，使用epsilon值处理不精确的浮点数学需要特殊的逻辑 ，这在实际代码中被考虑在内。此处省略了这些细节.
如果您想详细了解所有内容，请 查看 GitHub 上的项目。
为了实现事件队列和状态堆栈，我们将使用双链表。这很方便，因为我们需要直接查看我们周围的元素，并随机插入元素.
我不会展示整个链表实现（如果你愿意，你可以 阅读它），但会突出基本的API.
// create a linked list
var list = LinkedList.create();
// have some data we need stored
var data = {
some: 'data',
here: 1,
hello: 'world'
};
// mutate the data object to have next/prev/remove
data = LinkedList.node(data);
console.log(data);
=> {
some: 'data',
here: 1,
hello: 'world',
next: null,
prev: null,
remove: function(){ ... }
}
// insert the node into the list at a location
list.insertBefore(data, function(node){
// perform some check between `data` and the current `node`
// if we want to insert `data` before `node`, return true
// otherwise, return false
return true;
});
// after insertion, we can remove the node via:
data.remove();
// search the list
var transition = list.findTransition(function(node){
// keep checking for a condition
// keep returning false until the condition is true
if (someCondition(node))
return true;
return false;
});
// `transition` will contain the nodes before and after the
// condition changed from false to true
console.log(transition);
=> {
before: nodeBeforeTransition or null,
after: nodeAfterTransition or null,
insert: function(node){ ... }
}
// insert `data` where the transition happened
transition.insert(data);
初始化事件
首先，让我们开始将一个区域（它是一个点列表）转换为一系列要添加到事件队列中的段：
// create the event linked list
var event_root = LinkedList.create();
// convert a region to a series of segments
function eventAddRegion(region){
// regions are a list of points:
// [ [0, 0], [100, 0], [50, 100] ]
var pt1;
var pt2 = region[region.length - 1];
for (var i = 0; i < region.length; i++){
pt1 = pt2;
pt2 = region[i];
var forward = pointsCompare(pt1, pt2);
// if points are equal, we have a zero-length segment
if (forward === 0)
continue; // just skip it
eventAddSegment(
segmentNew(
forward < 0 ? pt1 : pt2,
forward < 0 ? pt2 : pt1
)
);
}
}
目前，一个线段非常简单:
function segmentNew(start, end){
return {
start: start,
end: end
};
}
请注意，eventAddRegion它并不关心指定顶点的顺序——它关心哪个顶点将成为事件，哪个将成为
它决定使用pointsCompare
function pointsCompare(p1, p2){
// returns:
// -1 if p1 is smaller
// 0 if equal
// 1 if p2 is smaller
if (p1[0] === p2[0]) // are we on the same vertical line?
if (p1[1] === p2[1]) // are we the same exact point?
return 0;
return p1[1] < p2[1] ? -1 : 1; // compare Y values
}
return p1[0] < p2[0] ? -1 : 1; // compare X values
}
请注意，如果 X 坐标相同，我们只比较 Y 坐标.
接下来，将段转换为和
function eventAddSegment(seg){
var ev_start = eventAddSegmentStart(seg);
eventAddSegmentEnd(ev_start, seg);
return ev_start;
}
function eventAddSegmentStart(seg){
var ev_start = LinkedList.node({
isStart: true,
pt: seg.start,
seg: seg,
other: null,
status: null
});
eventAdd(ev_start, seg.end);
return ev_start;
}
function eventAddSegmentEnd(ev_start, seg){
var ev_end = LinkedList.node({
isStart: false,
pt: seg.end,
seg: seg,
other: ev_start,
status: null
});
ev_start.other = ev_end;
eventAdd(ev_end, ev_start.pt);
}
一个事件包含:
1.isStart– 区分和事件的标志
2.pt – 与此事件相关的点
3.seg – 产生此事件的线段
4.other– 姐妹事件（的other指向其，反之亦然）
5.status – 状态堆栈中的未来节点.
另请注意，我们必须手动将事件的另一个点传递给eventAdd作为第二个参数。通常我们只关注other事件中的字段——但是当添加 事件时，该other字段将是null因为我们还没有创建
使用我们的链表 APIeventAdd非常简单:
function eventAdd(ev, other_pt){
event_root.insertBefore(ev, function(here){
// should ev be inserted before here?
var comp = eventCompare(
ev .isStart, ev .pt, other_pt,
here.isStart, here.pt, here.other.pt
);
return comp < 0;
});
}
我们比较这两个事件——具体来说，我们需要知道它们是 事件还是事件，事件代表什么点，以及另一个点.
最后，负责确定事件顺序的函数:
function eventCompare(
p1_isStart, p1_1, p1_2,
p2_isStart, p2_1, p2_2
){
// returns:
// -1 if p1 is smaller
// 0 if equal
// 1 if p2 is smaller
// compare the selected points first
var comp = pointsCompare(p1_1, p2_1);
if (comp !== 0)
return comp;
// the selected points are the same
// if the non-selected points are the same too...
if (pointsCompare(p1_2, p2_2) === 0)
return 0; // then the segments are equal
// if one is a start event and the other isn't...
if (p1_isStart !== p2_isStart){
// favor the one that isn't the start
return p1_isStart ? 1 : -1;
}
// otherwise, we'll have to calculate which one is below the
// other manually
return pointAboveOrOnLine(p1_2, p2_1, p2_2) ? 1 : -1;
}
这个函数对于理解是必不可少的。每一行都很重要，如果你弄错了，你会遇到一些讨厌的错误。
首先我们比较选择的点。如果点不相等，那么这很简单：顺序与pointsCompare给我们的顺序完全相同.
如果所选点相同，则意味着两个事件正好位于彼此的顶部.
哪个先走？
好吧，如果other 也是相同的，那也没关系。这些段是相等的，最终会被事件循环组合起来.
如果其中一个点是事件，另一个是事件，那么我们希望 事件先进行
为什么？因为事件意味着从状态中删除一个段。我们应该在插入一个新的线段之前删除一个线段，否则在插入新线段时，它的邻居之一将是一个不可能与其相交的段.
最后，我们正在处理共享一个共同起点或共同终点的线段.
在这种情况下，我们需要仔细找出哪个线段在上面。我们通过手动计算另一个点是否在由p2的点组成 的线上方，通过 来做到这一点pointAboveOrOnLine
事件循环
现在我们有了事件，让我们处理事件循环
// create the status stack
var status_root = LinkedList.create();
function eventLoop(){
var segments = [];
while (!event_root.isEmpty()){
var ev = event_root.getHead();
if (ev.isStart){
// find the insertion location of ev
var transition = statusFindTransition(ev);
// figure out the events that are above and below this
// event
var above = null;
if (transition.before)
above = transition.before.ev;
var below = null;
if (transition.after)
below = transition.after.ev;
// check for intersections between ev and whoever is
// above and below it
var eve = checkBothIntersections(ev, above, below);
if (eve){
// ev and eve are equal
// we'll keep eve and throw away ev
// update eve.seg's fill annotations based on ev.seg
// TODO: this
ev.other.remove();
ev.remove();
continue;
}
// if there were intersections, then new events would
// have been inserted... those new events *could* be
// required to be processed before this event
if (event_root.getHead() !== ev){
// something was inserted before us in the event
// queue, so loop back around and process it first
continue;
}
// calculate fill annotations
// TODO: this
// create the status node
var st = LinkedList.node({ ev: ev });
// insert the node at the transition location
transition.insert(st);
// remember the node for later
ev.other.status = st;
}
else{
// this segment is ending, so we no longer have to worry
// about future segments intersecting with it...
// processing end event, so grab the previously inserted
// status node
var st = ev.status;
// removing the status will create two new adjacent
// edges, so we need to check for those
if (status_root.exists(st.prev) &&
status_root.exists(st.next)){
// new adjacent edges exist, so check for further
// intersections
checkIntersection(st.prev.ev, st.next.ev);
}
// remove the status
st.remove();
// save the segment
segments.push(ev.seg);
}
// remove the event and continue
event_root.getHead().remove();
}
return segments;
}
这是处理事件的引擎，也是我们整个算法的核心
需要注意的一些事项
1. checkBothIntersections可能会检测到它ev的段与另一个段相同--这导致完全丢弃 ev并保留先前处理的线段.
2. 在检查交叉点并确认不应首先处理从交叉点创建的事件之后，才会删除事件.
3.当我们从状态中删除一个线段时，我们会对新的相邻段进行特殊检查
4.我们只保存完成此过程线段.
在检查交叉点时还有很多事情要处理，我们将在计算填充情况时(fill annotations)添加到这个核心循环中，但这就是最根本的东西.
检查交叉口
检查当前事件与其上方和下方的任何内容之间的交集很简单:
function checkBothIntersections(ev, above, below){
if (above){
var eve = checkIntersection(ev, above);
if (eve)
return eve;
}
if (below)
return checkIntersection(ev, below);
return false;
}复杂的部分是checkIntersection
首先让我们从简单的情况开始
function checkIntersection(ev1, ev2){
// returns the segment equal to ev1
// or false if nothing equal
var seg1 = ev1.seg;
var seg2 = ev2.seg;
var a1 = seg1.start;
var a2 = seg1.end;
var b1 = seg2.start;
var b2 = seg2.end;
var i = linesIntersect(a1, a2, b1, b2);
if (i === false){
// segments are parallel or coincident
// ... special logic here ...
}
else{
// otherwise, lines intersect at i.pt, which may or may
// not be between the endpoints
// is A divided between its endpoints? (exclusive)
if (i.alongA === 0){
if (i.alongB === -1) // yes, at exactly b1
eventDivide(ev1, b1);
else if (i.alongB === 0) // yes, between B's endpoints
eventDivide(ev1, i.pt);
else if (i.alongB === 1) // yes, at exactly b2
eventDivide(ev1, b2);
}
// is B divided between its endpoints? (exclusive)
if (i.alongB === 0){
if (i.alongA === -1) // yes, at exactly a1
eventDivide(ev2, a1);
else if (i.alongA === 0) // yes, between A's endpoints
eventDivide(ev2, i.pt);
else if (i.alongA === 1) // yes, at exactly a2
eventDivide(ev2, a2);
}
}
return false;
}
该linesIntersect函数执行原始计算的grunt
如果它返回false，那么线条是重合的，我们需要处理我们上面讨论的六种情况.
否则，我们检查交叉点的地方通过观察发生i.alongA和i.alongB
这些设置为特定值，具体取决于交点发生的位置linesIntersect
检查导致分割的每种情况，如果需要分割段，则使用被分割eventDivide的事件和分割点调用该 函数.
function eventDivide(ev, pt){
var ns = segmentCopy(pt, ev.seg.end, ev.seg);
eventUpdateEnd(ev, pt);
return eventAddSegment(ns, ev.primary);
}
function eventUpdateEnd(ev, end){
// slides an end backwards
// (start)------------(end) to:
// (start)---(end)
ev.other.remove();
ev.seg.end = end;
ev.other.pt = end;
eventAdd(ev.other, ev.pt);
}
有几种方法可以划分一个线段.
我首先通过复制被分割的线段来创建代表交点右侧的线段.
然后我更新当前事件段的结束点，并重新插入更新的事件
最后，我将新段的事件添加到事件队列中.
重合线
在完成之前checkIntersection，我们需要填写重合线的特殊处理.
// segments are parallel or coincident
// if points aren't collinear, then the segments are parallel
// so no intersections
if (!pointsCollinear(a1, a2, b1))
return false;
// otherwise, segments are on top of each other somehow
// if segments touch at endpoints, then no intersection
if (pointsSame(a1, b2) || pointsSame(a2, b1))
return false;
var a1_equ_b1 = pointsSame(a1, b1);
var a2_equ_b2 = pointsSame(a2, b2);
// if segments are exactly equal, return the equal segment
if (a1_equ_b1 && a2_equ_b2)
return ev2;
var a1_between = !a1_equ_b1 && pointBetween(a1, b1, b2);
var a2_between = !a2_equ_b2 && pointBetween(a2, b1, b2);
if (a1_equ_b1){
if (a2_between){
// (a1)---(a2)
// (b1)----------(b2)
eventDivide(ev2, a2);
}
else{
// (a1)----------(a2)
// (b1)---(b2)
eventDivide(ev1, b2);
}
// we've created equal segments, so throw away ev1 because
// it is equal to ev2
return ev2;
}
else if (a1_between){
if (!a2_equ_b2){
// make a2 equal to b2
if (a2_between){
// (a1)---(a2)
// (b1)-----------------(b2)
eventDivide(ev2, a2);
}
else{
// (a1)----------(a2)
// (b1)----------(b2)
eventDivide(ev1, b2);
}
}
// (a1)---(a2)
// (b1)----------(b2)
eventDivide(ev2, a1);
}
这看起来很多，但实际上不是。如果您单独处理每个案例，这一切都是有道理的
首先，我们确保我们正在处理彼此重叠的线条
如果它们完全相等，我们返回ev2，这ev1在事件循环中具有丢弃的效果》
然后我们用它pointsBetween来计算剩下的五个案例中的哪一个
唯一可能令人困惑的是：为什么我们ev2在第一个if-block下返回，但在else if-block下不返回任何内容？毕竟，不是有相等的部分吗？
是的：是相同的线段。但这些线段都不在状态堆栈
由于(b1)---(b2)正在被除以(a1)，状态中唯一的段将是更新的段(b1)---(a1)。 该段与任何其他段不同.
事实(a1)---(a2)与(a1)---(b2)稍后将检测到的相同，因为这些段完全在事件队列中.
寻找状态转换
关于事件循环的最后一件事是解释statusFindTransition
请记住，我们不会立即插入状态堆栈——首先我们定位将发生插入的位置，因此我们可以获取当前正在处理的段上方和下方的线段.
function statusFindTransition(ev){
return status_root.findTransition(function(here){
var comp = statusCompare(ev, here.ev);
return comp > 0; // top to bottom
});
}
function statusCompare(ev1, ev2){
var a1 = ev1.seg.start;
var a2 = ev1.seg.end;
var b1 = ev2.seg.start;
var b2 = ev2.seg.end;
if (pointsCollinear(a1, b1, b2)){
if (pointsCollinear(a2, b1, b2))
return 1; // doesn't matter, as long as it's consistent
return pointAboveOrOnLine(a2, b1, b2) ? 1 : -1;
}
return pointAboveOrOnLine(a1, b1, b2) ? 1 : -1;
}
该statusCompare函数确定状态堆栈的排序.
给定两个事件，哪个事件首先出现在状态堆栈中？
我们想从上到下对状态堆栈进行排序。这样，当在状态堆栈中找到新事件的插入位置时，我们将能够直接查看插入点的上方和下方，以查看需要检查交叉点的两条线.
所以我们的排序只是计算哪条线在另一条线上.
如果a1高于或低于另一条线，那么我们就有了答案.
如果a1共线，那么我们需要检查a2
最后，如果a1和a2与另一条线共线，则意味着两条线共线 - 所以排序并不重要，只要它们最终彼此相邻即可。
Calculating Annotations
在这一点上，我们有一个系统的轮廓，它可以获取一系列线并扫过它们，检测交叉点并将线分割成线段 - 并将完美重叠的线段组合起来，这样我们就不会在同一位置有多个线段
现在：当我们完成这个过程时，我们如何计算适当的填充注释（fill annotations）
所需的组合填充注释
其实，还是挺乱的
有一个秘密可以让它变得更容易.
我们运行垂直线扫描三次:
1.只扫描红色多边形，检查自相交，只计算红色填充注释
2.只扫描蓝色多边形，检查自交，只计算蓝色填充注释
3.扫描步骤 1 和 2 中生成的线段，检查多边形之间的交叉点，计算最终的组合填充注释.
为了理解为什么我们需要扫描三次，我们首先需要看看如何计算单个多边形的填充注释.
存储注释
存储注释信息很容易——我们只需将它添加到线段中.
function segmentNew(start, end){
return {
start: start,
end: end,
myFill: {
above: null, // is there fill above us?
below: null // is there fill below us?
},
otherFill: null
};
}
有三种状态：null表示我们还没有计算填充，和true/false是计算的结果.
请注意，我们还区分了myFill和otherFill– 在注释单个多边形时，我们将填写myFill信息。在执行第三次扫描以组合多边形时，我们将填写otherFill信息.
注释单个多边形
Bentley-Ottmann 交集算法有一个漂亮的特性，对于计算填充注释非常有用:
对于添加到状态中的每个段，我们知道其正下方的线段.
这就是计算新线段填充注释所需知道的全部内容
// calculate fill annotations
var toggle; // are we a toggling edge?
if (ev.seg.myFill.below === null) // if we are a new segment...
toggle = true; // then we toggle
else // we are a segment that has previous knowledge
toggle = ev.seg.myFill.above !== ev.seg.myFill.below;
// next, calculate whether we are filled below us
if (!below){ // if nothing is below us...
// we are filled below us if the polygon is inverted
ev.seg.myFill.below = primaryPolyInverted;
}
else{
// otherwise, we know the answer -- it's the same if whatever
// is below us is filled above it
ev.seg.myFill.below = below.seg.myFill.above;
}
// since now we know if we're filled below us, we can calculate
// whether we're filled above us by applying toggle to whatever
// is below us
if (toggle)
ev.seg.myFill.above = !ev.seg.myFill.below;
else
ev.seg.myFill.above = ev.seg.myFill.below;
第一个观察是：
- 如果我们有我们下面一个部分，那么我们充满下面我们如果在我们下面的段充满 以上吧。
- 如果我们下面没有线段，那么我们就在底部——如果 多边形是倒置的，我们就会在我们下面填充。
这很容易。
第二个观察是，一旦我们知道我们是否在我们下方被填满，我们就可以计算我们是否在我们上方被填满：
如果我们是一个切换填充状态的段，那么当且仅当我们没有在我们下方填充时，我们才会在我们上方填充.
如果我们是一个不切换填充状态的段，那么当且仅当我们在我们下方填充时，我们才会在我们上方填充.
这有点复杂。切换线段段(toggling segment)是什么意思，为什么我们需要它
请记住，完全重叠的段将合并.
假设我们合并两个段，它们下面都是空的，上面是填充的。结果段下面应该是空的，上面应该是空的.
底部段是非切换线段。它下面的填充等于它上面的填充（false在这种情况下都是）
因此，一旦我们知道一个段下面的填充状态，并且我们知道该段是否正在切换，我们就可以计算上面的填充状态
var toggle; // are we a toggling edge?
if (ev.seg.myFill.below === null) // if we are a new segment...
toggle = true; // then we toggle
else // we are a segment that has previous knowledge
toggle = ev.seg.myFill.above !== ev.seg.myFill.below;
...
if (toggle)
ev.seg.myFill.above = !ev.seg.myFill.below;
else
ev.seg.myFill.above = ev.seg.myFill.below;
新段默认为切换段。先前划分的段（通过segmentCopy 内部创建eventDivde）将具有来自先前合并的填充信息，该信息将确定该段是否正在切换.
在合并期间注释
最后，当合并两个段时，我们需要更新幸存段的填充信息，如上所述.
如果相交函数确定这ev是一个重复段，它将返回eve，这是幸存的线段.
// update eve.seg's fill annotations based on ev.seg
var toggle; // is the discarded edge a toggling edge?
if (ev.seg.myFill.below === null)
toggle = true;
else
toggle = ev.seg.myFill.above !== ev.seg.myFill.below;
// merge two segments that belong to the same polygon
// think of this as sandwiching two segments together, where
// `eve.seg` is the bottom -- this will cause the above fill
// flag to toggle
if (toggle)
eve.seg.myFill.above = !eve.seg.myFill.above;这个可视化有点棘手，因为这些段正好在彼此的顶部》
由于填充状态是从下到上计算的，填充状态以下的幸存段已经计算并且无法更改.
幸存段的上方填充状态将变为丢弃段的上方 填充状态.
丢弃段的下方填充状态将与幸存段的 上方填充状态相同.
丢弃的段的上方填充状态将通过切换其下方填充状态来计算.
因此，如果丢弃的段是一个切换段，那么我们需要切换幸存段的上述填充状态.
组合填充注释
这是最后一个困难的部分，然后我们就可以自由回家了.
在对两个多边形执行自相交阶段并在该过程中对其进行注释后，我们得到以下信息:
现在我们执行第三次交叉扫描。这次扫描将与之前的完全相同，除了现在我们必须更改计算填充注释的逻辑.
因此，我们将替换主要的填充注释计算以及合并段时的逻辑.
让我们从合并段的逻辑开始，因为这很容易.
再一次，ev是丢弃的段，eve是幸存的线段.
// merge two segments that belong to different polygons
// each segment has distinct knowledge, so no special logic is
// needed -- note that this can only happen once per segment
// in this phase, because we are guaranteed that all
// self-intersections are gone
eve.seg.otherFill = ev.seg.myFill;
哦，我的天哪，终于轻松的局面了.
在第三次扫描期间合并线段时，我们可以保证这些线段属于不同的多边形，因为前两次扫描删除了所有自相交.
因此，在合并两个段时，只需复制填充信息即可.
现在是更难的部分——如何计算otherFill最后一段.
if (ev.seg.otherFill === null){
// if we don't have other information, then we need to figure
// out if we're inside the other polygon
var inside;
if (!below){
// if nothing is below us, then we're inside if the other
// polygon is inverted
if (ev.primary)
inside = secondaryPolyInverted;
else
inside = primaryPolyInverted;
}
else{ // otherwise, something is below us
// so copy the below segment's other polygon's above
if (ev.primary === below.primary)
inside = below.seg.otherFill.above;
else
inside = below.seg.myFill.above;
}
ev.seg.otherFill = {
above: inside,
below: inside
};
}
首先，如果otherFill不是null，那么它已经从之前的合并计算出来了——所以不要覆盖它
否则，otherFill由该线段是否在另一个多边形内来确定.
如果我们下面没有任何东西，那么如果它是倒置的，那么我们就在另一个多边形内.
否则，我们可以检查我们下面的部分.
如果我们都属于同一个多边形，那么如果下面的线段被另一个多边形（via below.seg.otherFill.above）填充在它上面，那么我们就在另一个多边形内
如果我们属于不同的多边形，那么如果下面的线段在其上方填充（通过below.seg.myFill.above），我们就在另一个多边形内部.
ev.primary，primaryPolyInverted和secondaryPolyInverted第三阶段开始时变量被简单有线的，基于其中的源段来自。简单.
结果段.
一个小小的记账点：保存最后段的结果之前，我们将交换myFill 和otherFill如果段是从二级多边形来源。这意味着我们生成的多边形将始终具有 主要填充状态myFill和 次要填充状态otherFill，无论线段来自何处
// if we've reached this point, we've calculated everything
// there is to know, so save the segment for reporting
if (!ev.primary){
// make sure `seg.myFill` actually points to the primary
// polygon though
var s = ev.seg.myFill;
ev.seg.myFill = ev.seg.otherFill;
ev.seg.otherFill = s;
}
// save the segment
segments.push(ev.seg);
综合内容
让我们休息一下，享受我们迄今为止计算出的美丽的图；
我们有一个独特的线段列表，这些线段没有任何交叉点，并用每个多边形的填充状态进行了注释。
我们还有一些工作要做，但从这里开始要容易得多.
选择结果段.
一旦我们有了完整注释的段列表，我们就可以根据布尔运算符（交、并、差、异或）选择结果段
作为一个额外的好处，如果我们很聪明，我们还可以计算段的未来填充状态。如果用户想对同一数据执行多个操作（例如，通过合并两个多边形来合并三个多边形，然后将第三个多边形与结果合并），这非常棒.
毕竟——为什么不呢？我们保证结果段不相交，因此我们可以完全跳过自相交阶段以供将来计算
Union
让我们来看看如何计算联合(Union)，同样的过程可以用于计算其他运算符
对于每个段，有四个布尔值，因此需要考虑 16 种状态
- 高于 1：上面填充的主要多边形？是/否
- 低于 1：下面填充的主要多边形？是/否
- 上面 2：上面填充的次要多边形？是/否
- 下面 2：下面填充的次要多边形？是/否
考虑到我们的操作，我们只需要针对每个状态回答以下问题:
- 我们保留这个细分线段吗？
- 如果是这样，结果线段是在上方还是下方填充？
好吧，让我们开始工作:
| Above 1 | Below 1 | Above 2 | Below 2 | Keep? | Filled |
|---|---|---|---|---|---|
| No | No | No | No | ||
| No | No | No | Yes | Below | |
| No | No | Yes | No | Above | |
| No | No | Yes | Yes | ||
| No | Yes | No | No | Below | |
| No | Yes | No | Yes | Below | |
| No | Yes | Yes | No | ||
| No | Yes | Yes | Yes | ||
| Yes | No | No | No | Above | |
| Yes | No | No | Yes | ||
| Yes | No | Yes | No | Above | |
| Yes | No | Yes | Yes | ||
| Yes | Yes | No | No | ||
| Yes | Yes | No | Yes | ||
| Yes | Yes | Yes | No | ||
| Yes | Yes | Yes | Yes |
你如何计算每一行？
好吧，没有真正的秘密……只需一行一行地进行，然后将其形象化.
如果该段在其上方和下方都被填充，那么我们不想保留它——它在联合中毫无价值.
如果一个段在一侧至少被填充一次，那么我们想要保留它——我们的填充状态将是任何一侧被填充.
编码表
我们如何在代码中表示表格？我决定使用一个包含 16 个元素的数组，其中 0 表示放弃该段，1 表示上方填充，2 表示下方填充.
数组中的索引是通过将标志解释为位来确定的。所以“No, Yes, No, No”是“0100”，也就是索引4
这意味着我们的五个操作由一个 16 元素的数组定义：
// union
[
0, 2, 1, 0,
2, 2, 0, 0,
1, 0, 1, 0,
0, 0, 0, 0
]
// intersect
[
0, 0, 0, 0,
0, 2, 0, 2,
0, 0, 1, 1,
0, 2, 1, 0
]
// difference (primary - secondary)
[
0, 0, 0, 0,
2, 0, 2, 0,
1, 1, 0, 0,
0, 1, 2, 0
]
// difference (secondary - primary)
[
0, 2, 1, 0,
0, 0, 1, 1,
0, 2, 0, 2,
0, 0, 0, 0
]
// xor
[
0, 2, 1, 0,
2, 0, 0, 1,
1, 0, 0, 2,
0, 1, 2, 0
]
很酷吧
最后，给定一个段列表和一个操作数组，执行选择
var result = [];
segments.forEach(function(seg){
var index =
(seg.myFill.above ? 8 : 0) +
(seg.myFill.below ? 4 : 0) +
((seg.otherFill && seg.otherFill.above) ? 2 : 0) +
((seg.otherFill && seg.otherFill.below) ? 1 : 0);
if (selection[index] !== 0){
// copy the segment to the results, while also calculating the fill status
result.push({
start: seg.start,
end: seg.end,
myFill: {
above: selection[index] === 1, // 1 if filled above
below: selection[index] === 2 // 2 if filled below
},
otherFill: null
});
}
});
同样，此时这应该很容易理解.
线段链接.
但是等等——现在我们有一个段列表，每个段都包含一个起点和终点。我们如何将其转换回多边形？
多边形是区域列表，而不是线段列表.
这并不难
基本算法是保持一个开放链的列表
当我们处理一个线段时，搜索它是否可以添加到任何开放链的末尾
如果无法将其添加到链中，则创建一个新的开放链，其中包含单个线段.
如果它可以添加到两条开链中，则将这些链合并为一条开链
否则，如果它只添加到单个开放链中，那么我们需要检查添加段是否会导致链关闭。如果是这样，关闭链并将其添加到区域列表中（并将其从打开的链列表中删除）
在做这一切的同时，我们可以更进一步，合并共线段。这在没有太多额外处理的情况下消除了结果中不必要的顶点
由于该算法非常简单，因此我不会列出代码，而是直接 在此处链接到它。你可以看到它的行为与我描述的完全一样
完毕
令人惊讶的是，我们完成了
谢天谢地，我已经在一个易于使用的库中编写了整个算法，并 发布在 GitHub 上
最重要的是，我还编写了一个交互式演示
您可以在不同的测试用例之间循环，更改操作，并在计算交点和填充注释时观看算法的动画，然后将结果段链接在一起。