 |
 |
 |
 |
 |
 |
 |
 |
|
 |
|
 |
|
| 第四节 包含与重叠 | ||||
 简单多边形的包含算法
平面上的简单多边形是不相邻的边不能相交的多边形,设它用顶点坐标的逆时针序列  确定,即沿顶点序列前行时内部在左侧。
对平面上坐标为  的任意一点P,包含性检验问题是判断它是否在所给出简单多边形的内部。一个简便的判断方法是由P做竖直向下的射线,计算此射线与多边形各边交点的个数。 |
||||
 |
||||
| 当由点P竖直向下的射线恰好通过多边形的顶点或某一边时,交点计数可采取简单的"左闭右开"法来处理,即:当多边形一边的两个顶点的x坐标都小于或等于点P的x坐标时,相应交点不计算在内。 | ||||
 |
||||
 第一节
线段的交点计算第二节
多边形表面的交线计算第三节
平面中的凸壳算法第四节
包含与重叠第五节
简单多边形的三角剖分 |
