T9的空间

You will never walk alone!

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  69 随笔 :: 0 文章 :: 28 评论 :: 0 Trackbacks

我就叫他射线法吧
基本步骤:

1,过p点垂直向上作一条射线

2,判断此射线与n边形n条边的交点

3,把所有交点相加,如果是奇数则说明在多边形内,否则在多边形外

思路非常的简单,另外说明一下几种特殊的情况:

1,射线与多边形的顶点相交;比如射线过多边形的Pi点,则如果Pi-1和Pi+1在此射线的异侧,此交点可以算一个,如果此两点在射线的同侧,则此交点不计。此结论非常简单,画个图应该就能明白了

2,p点在多边形的某一条边上;也认为p在多边形中

3,p不在多边形的边上,但p的射线与多边形的某一条边重合;比如与Pi,Pi+1线段重合,则如果Pi-1和Pi+2在射线的两侧,此情况也算一个交点,否则此情况不计交点

posted on 2008-09-23 20:51 Torres 阅读(510) 评论(0)  编辑 收藏 引用 所属分类: Computation Geometry

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理