一种改进的点定位算法

通过对传统的点定位算法——奇偶法则算法的分析 ,提出了一种改进的奇偶法则的实现算法 .在改进算法中 ,从待判定点引出的射线定义为与 x轴平行且与其同向 ,对射线与区域边界边的相交情况进行了分类处理 .通过分析射线与边界边的位置关系 ,只有少数情况需要计算其交点 ,而大部分情况只需简单比较即可得出相交情况 .当射线穿过两条相邻边界边的交点时 ,根据定义的法则 ,只进行一次相交情况的判定 .因此 ,改进算法减少了计算交点的次数 ,提高了点定位的效率 .最后通过实际应用 ,对传统算法与改进算法在同样条件下的处理时间进行了比较

An Improved Algorithm for Inside-outside Testing

Based on the analysis of traditional algorithm of odd ever rule for inside outside testing, an improved algorithm is proposed. In the improved algorithm, the polar radial from the point to be tested is parallel to x axis and its direction is the same as the positive direction of x axis. All the possible crossing states of the polar radial and a side of the regular polygonal domain are enumerated, and they are classified. The crossing points of different type are processed in different method. According to the position relationship between the radial and the side, in a few states their crossing point must be computed to decide whether they cross or not. In most states, it can be determined that they cross or not only by simple comparison. If the radial is through the crossing point of two neighbor sides, only one testing is needed by the rules. Therefore, the times of computing crossing points is reduced, and the total time of testing is saved. An example shows that, when the points to be test are 10 000, the time which to test them takes by the improved algorithm is 23.5% of that by the traditional one, and when the points are 30 000, the former is only 15.4% of the latter.