基于平均条带划分的点的包含性测试方法

Point inclusion test based on averagely-divided stripes

提出了一个大量点与多边形关系计算的方法。该方法首先对多边形进行简单预处理，然后采用射线法对每个点进行包含性测试。预处理将多边形的最小包围矩形划分为相同大小的竖直条带，并计算每条边在哪些条带中，该预处理过程简单快速。利用预处理信息对点进行包含性测试时，只需用当前点构造的射线和点所在的条带包含的边进行相交测试即可。每个条带内包含的边的数目是有限的，常常接近一个常数，远远小于多边形的边数，因此相交测试计算次数显著减少，从而可以快速求得点与多边形的关系。该方法已经实现，并用人造数据和真实地理数据进行测试，测试结果证明该方法正确有效。

This paper presents a straightforward and efficient method for point inclusion test for large data sets. The method first preprocesses the polygon simply, and then adopts the ray-crossing idea for each inclusion test. The preprocessing just computes each edge＇ s location on the averagely-divided vertical stripes. It is simple and not time consuming. Then each point inclusion test can benefit from the preprocessing--Those edges which may intersect with the ray for each point according with the point＇ s location lying in the vertical stripes can be easily got, and the number of those edges is limited, usually near a constant number. As a result, the most time-consuming process of intersecting-tests is reduced obviously, and the inclusion test for each point is rapid. The method was implemented and tested on artificial data and real world GIS data. The testing result and the comparisons with other methods demonstrated its correctness and effectiveness.