发明名称 |
一种点面叠加分析方法 |
摘要 |
本发明提供一种点面叠加分析方法,包括如下步骤:1)将每个多边形分解为一组具有方向的多边形边;2)对于每个分析点,分别构造以该分析点为起点的竖直辅助线,所述辅助线终点位于所述多边形的外包以外;3)利用扫描线算法,对所有辅助线和该多边形的所有边进行扫描,得到每条辅助线与所述多边形的第一个交点;4)对于每条辅助线,分析该辅助线产生第一个交点的多边形边的位置关系,得出所述辅助线所对应的分析点与所述多边形的位置关系。本发明能够进行大数据量点与多边形关系的判断。对于任何一条辅助线,只要扫描到第一个交点,即可得到此线对应的点在多边形内还是在多边形外。因此本发明能够减少运算量,大大提高点面叠加的运算速度。 |
申请公布号 |
CN101533525A |
申请公布日期 |
2009.09.16 |
申请号 |
CN200810101816.8 |
申请日期 |
2008.03.12 |
申请人 |
中国科学院计算技术研究所 |
发明人 |
朱效民;闫杰;赵红超;方金云 |
分类号 |
G06T17/00(2006.01)I;G06T17/50(2006.01)I |
主分类号 |
G06T17/00(2006.01)I |
代理机构 |
北京泛华伟业知识产权代理有限公司 |
代理人 |
王 勇 |
主权项 |
1. 一种点面叠加分析方法,包括如下步骤:1)每次取一个多边形,对该多边形的方向进行初始化,将每个多边形分解为一组具有方向的多边形边;2)对于每个分析点,分别构造以该分析点为起点的竖直辅助线,所述辅助线终点位于所述多边形的外包以外;3)利用扫描线算法,对所有辅助线和该多边形的所有边进行扫描,得到每条辅助线与所述多边形的第一个交点;4)对于每条辅助线,分析该辅助线所对应的分析点和与该辅助线产生第一个交点的多边形边的位置关系,得出所述辅助线所对应的分析点与所述多边形的位置关系。 |
地址 |
100190北京市海淀区中关村科学院南路6号 |