一种判断点与多边形关系的快速算法

采用对多边形各边赋权值的方法,分析射线与多边形相交的不同情况,给出了使用结构化查询语言实现交点个数求解的快速解决方案.结合数据库管理系统提供的优化查询机制,通过执行一次查询求得射线与多边形的交点个数,从而快速地判断出点与多边形的位置关系.与其他改进方法相比,该方法易于理解,计算简单,对于具有多顶点的复杂多边形,其优越性显得更为突出.

Fast Method to Determine Spatial Relationship between Point and Polygon

To analyze the different locations of the intersection of a ray and a polygon quickly,a scheme of calculating the number for the intersection point is established based on the structure query language(SQL) and the method of weighting each side of the polygon.Combined with the optimized query mechanism of database management system,the amount of the intersections can be calculated by running the SQL once,and the spatial relationship between the point and polygon is confirmed rapidly.It is verified that the method is simpler and more understandable than the competing methods,especially for the complicated multi-vertex polygons.