点定位：如何拆分更新梯形图和二分搜索结构 ·（三）：处理S
1. 处理S（线段）
1.1 思路分析
S的处理相对比较简单，我们对其进行水平拆分，原梯形保留为上梯形，且没有退化的情况：
这里我们着重讨论的是，合并梯形（Trim Wall），笔者的拆分思路如下：
从左往右，依次进行合并；也就是左边吞并右边的梯形；
如果当前梯形的rightP在Si的上面，则合并下梯形；如果在Si的下面，则合并上梯形；如果刚好在Si上面，则什么都不做（即为处理Qi的情况）；
上图这个例子，如果我们经过A梯形，它的rightP在Si的上方，所以裁剪Si下面的蓝色虚线。同样当我们经过梯形B，它的rightP在Si的下方，所以裁剪Si上面的蓝色虚线。
1.2 代码解析
1.2.1 拆分
代码解析部分，我们同样还是先来看看整体的处理S的代码，然后重点看看拆分合并的代码逻辑：
/**
* handle S when adding a new segment,
* this operation will partition the original trapezoid into two parts( horizontal separation ):
* top(origin)
* ----------
* bottom
*
* this method will also handle trimming walls:
* first, store trapezoids, top and bottom, to be merged later.
* secondly, merge current top and bottom into previously stored ones.
* */
// This method is only called when the segment crosses multiple trapezoids
public static
void handleS( SearchVertex d, Line line, Stack<SearchVertex> de ) {
SearchVertex newer = handleS( d.trapezoid, line, de );
redirectParents( newer, d );
}
// code to do the separation and update
public static
SearchVertex handleS( Trapezoid middle, Line line, Stack<SearchVertex> de ) {
Vector p = line.startPoint;
Vector q = line.endPoint;
assert Vectors.sortByX( p, q ) <= 0;
Vector rightP = middle.rightP;
// horizontal partition
Trapezoid top = new Trapezoid( p, q, middle.top, line );
Trapezoid bottom = new Trapezoid( p, q, line, middle.bottom );
Trapezoid.mergeUppers( top, middle );
Trapezoid.mergeLowers( bottom, middle );
// p -> q -> s, no need to trim wall,
// p -> s, p -> q, s -> s, q -> s need,
if ( de != null ) {
// store trapezoids, top and bottom, to be merged later.
addTrims( top, bottom, rightP, line, de );
// merge current top and bottom into previously stored ones.
if ( de.size() > 1 ) {
SearchVertex trim = trim( de );
// get trimmed top and bottom
top = trim.top;
bottom = trim.bottom;
}
}
// initialize the y node
SearchVertex YNode = new SearchVertex( line );
// top trapezoid has been added before?
if ( top.vertex == null )
// no, create a new one
YNode.left = new SearchVertex( top );
else {
// yes, the y node points to it
assert top.vertex.trapezoid == top;
YNode.left = top.vertex;
}
YNode.left.parents.add( YNode );
// top trapezoid has been added before?
if ( bottom.vertex == null )
// no, create a new one
YNode.right = new SearchVertex( bottom );
else {
// yes, the y node points to it
assert bottom.vertex.trapezoid == bottom;
YNode.right = bottom.vertex;
}
YNode.right.parents.add( YNode );
return YNode;
}
首先我们进行水平拆分：
// horizontal partition
Trapezoid top = new Trapezoid( p, q, middle.top, line );
Trapezoid bottom = new Trapezoid( p, q, line, middle.bottom );
Trapezoid.mergeUppers( top, middle );
Trapezoid.mergeLowers( bottom, middle );
然后保存当前需要合并的梯形，如果有两个待合并的梯形，则进行合并操作：
// p -> q -> s, no need to trim wall,
// p -> s, p -> q, s -> s, q -> s need,
if ( de != null ) {
// store trapezoids, top and bottom, to be merged later.
addTrims( top, bottom, rightP, line, de );
// merge current top and bottom into previously stored ones.
if ( de.size() > 1 ) {
SearchVertex trim = trim( de );
// get trimmed top and bottom
top = trim.top;
bottom = trim.bottom;
}
}
最后生成相应的叶结点，但是注意这里的叶结点可能在之前已经初始化了，因为合并的关系，会有多个父结点指向同一个叶结点的情况：
// initialize the y node
SearchVertex YNode = new SearchVertex( line );
// top trapezoid has been added before?
if ( top.vertex == null )
// no, create a new one
YNode.left = new SearchVertex( top );
else {
// yes, the y node points to it
assert top.vertex.trapezoid == top;
YNode.left = top.vertex;
}
YNode.left.parents.add( YNode );
// bottom trapezoid has been added before?
if ( bottom.vertex == null )
// no, create a new one
YNode.right = new SearchVertex( bottom );
else {
// yes, the y node points to it
assert bottom.vertex.trapezoid == bottom;
YNode.right = bottom.vertex;
}
YNode.right.parents.add( YNode );
1.2.2 合并
最后我们来看看合并（trim wall）的代码，首先是判断是合并上梯形还是下梯形，我们使用toLeft测试进行判断：
/**
* First process of trimming walls:
* store trapezoids, top and bottom, to be merged later.
* */
public static
void addTrims( Trapezoid top, Trapezoid bottom, Vector rightP,
Line line, Stack<SearchVertex> de ) {
SearchVertex trim = new SearchVertex( SearchVertex.NodeType.TRIMMING );
double res = Triangles.areaTwo( line.startPoint, line.endPoint, rightP );
// if rightP lies above s, trim lower wall
if ( MyMath.isPositive( res ) ) {
bottom.rightP = null;
top.rightP = rightP;
trim.isTrimmingTop = false;
}
// if rightP lies below s, trim upper wall
else if ( MyMath.isNegative( res ) ) {
// assert rightP lies below s
bottom.rightP = rightP;
top.rightP = null;
trim.isTrimmingTop = true;
}
// if rightP lies on s, do nothing
// this happens when handling Q,
// just trim wall, no need to add ones to be trimmed
trim.top = top;
trim.bottom = bottom;
de.add( trim );
}
我们根据当前梯形rightP在Si的方位，进行相应的处理。这里的代码和我们之前的讲解是基本一致的，大家可以结合注释进行理解。接下来就是合并的代码逻辑：
/**
* Second process of trimming walls:
* secondly, merge current top and bottom into previously stored ones.
*
* */
public static
SearchVertex trim( Stack<SearchVertex> de ) {
assert de.size() == 2;
SearchVertex cur = de.pop();
SearchVertex prev = de.pop();
assert cur.type == SearchVertex.NodeType.TRIMMING;
assert prev.type == SearchVertex.NodeType.TRIMMING;
// trimming top
if ( prev.isTrimmingTop ) {
assert check( prev.top, cur.top );
// merge tops
Trapezoid.mergeRights( prev.top, cur.top );
// current top was eaten by previous top
cur.top = prev.top;
// link bottoms
Trapezoid.setUppers( prev.bottom, cur.bottom );
cur.bottom.leftP = prev.bottom.rightP;
// at this point, prev.bottom has been all set up
assert prev.bottom.check();
}
// trimming bottom
else {
assert check( prev.bottom, cur.bottom );
// merge bottoms
Trapezoid.mergeRights( prev.bottom, cur.bottom );
// current bottom was eaten by previous bottom
cur.bottom = prev.bottom;
// link tops
Trapezoid.setLowers( prev.top, cur.top );
cur.top.leftP = prev.top.rightP;
// at this point, prev.top has been all set up
assert prev.top.check();
}
de.push( cur );
return cur;
}
我们依据之前的判断，来合并两个上梯形，或两个下梯形。这里需要注意两点：
- 左梯形吞并右梯形，无一例外；
- 邻居重定向；
推荐大家根据代码的顺序，自己画一个例子进行理解，代码不难，但是需要费一番功夫才能弄懂究竟是如何进行合并操作的，特别需要注意合并和重定向方向，方向问题在计算几何里面尤为重要。
2. 二分搜索结构(Search Structure)
SS基本没有太多可以讨论，它基本就是一个二叉搜索树（但不是严格意义上的BST，是类BST的DAG），所以更新、搜索操作和BST都非常相似，熟悉BST的同学理解起来应该没有什么太大的难度。这里我们提一下对于退化情况的处理，也就是Pi或Qi已经存在于SS中。如果Pi位于X-Node的垂直线上，我们认为Pi在X-Node的右边：
case X_POINT_Q, X_POINT_P -> {
if ( Vectors.isLeft( root.point, p ) )
return get( root.left, line );
// whenever p lies on the vertical line of an x-node,
// we decide that it lies to the right.
return get( root.right, line );
}
另一种情况，如果Pi位于某条线段上面（S，Y-Node），我们则比较S和Si的斜率，如果Si的斜率更大，则认为Pi在S的上方，反之则在S的下方：
case SEGMENT -> {
double res = Triangles.areaTwo( root.line.startPoint, root.line.endPoint, p );
// whenever p lies on a segment s of a y-node
// (this can only happen if si shares its left endpoint, p, with s)
// we compare the slopes of s and si; if the slope of si is larger,
// we decide that p lies above s, otherwise we decide that it is below s.
if ( MyMath.isEqualZero( res ) ) {
if ( Lines.compareBySlope( line, root.line ) > 0 )
return get( root.left, line );
else return get( root.right, line );
}
else if ( MyMath.isPositive( res ) )
return get( root.left, line );
return get( root.right, line );
}
这些处理退化情况的代码，大家可以在SearchStructure类里面找到。到此，我们就基本讲解完毕怎么去拆分更新梯形图和SS，如果大家有任何的疑问，可以留言或者联系我哒~
上一节：(二)：处理P和Q
3. 附录：代码
3.1 算法
| Description | Entry method\File |
|---|---|
| Build trapezoidal Map and search structure(创建梯形图和二分搜索结构) | SearchStructure trapezoidalMap( List<Line> lines, SearchVertex box ) |
| Point Locatoin(点定位) | public SearchVertex get( Line line ) |
| Program ( including visualization, 可视化程序 ) | Programming Assignment 3 - Trapezoidal Map and Planar Point Location |
3.2 数据结构
| Description | Entry File/Package |
|---|---|
| Trapezoidal Map( 梯形图 ) | public class Trapezoid |
| Search Structure( Tree-like DAG, 二分搜索结构，树状DAG ) | public class SearchStructure |
4. 参考资料
- Computational Geometry: Algorithms and Applications
- 计算几何 ⎯⎯ 算法与应用, 邓俊辉译，清华大学出版社
5. 免责声明
※ 本文之中如有错误和不准确的地方，欢迎大家指正哒~
※ 此项目仅用于学习交流，请不要用于任何形式的商用用途，谢谢呢；