摘要
针对GIS拓扑数据结构的建立,该文提出了一种快速进行内点和孤岛归属的算法.算法首先利用“面积法”实现外多边形的识别并获得外多边形左极点,然后利用“改进的射线法”将识别后的外多边形左极点和内点向左侧引出射线,并获得与弧段的交点,最后利用弧段的特征获得外多边形和内点的归属关系.由于该算法充分利用了弧段的特征,从而避免了多边形的组织和弧段的重复处理以及非直接包含关系的判断,保证了海量数据生成拓扑数据结构的效率.同时文章还对归属中的退化问题提出了解决方案.算法的实际应用表明,该算法具有较高的效率和较强的实用性.