平面多边形方向及内外点判断的新方法

Orientation and Point Inclusion Test for Planar Polygon

提出了一种通过构造一个与平面多边形拓扑同构的、严格凸多边形判断多边形方向的新方法 ,分析了退化情况并给出了处理方法 .基于受约束的三角划分的思想 ,提出了一种新的判断点在多边形内外的准则 ,并给出了算法 .实际应用表明 ,这两个算法稳定、可靠 。

By constructing a strict convex polygon topologically homomorphic to a planar polygon and considering some degenerate conditions, a new algorithm to determine the orientation of polygon is proposed. Based on the idea of constrained triangulation, a practical criterion and corresponding algorithm to determine the point inclusion of polygon are put forward. Some applications show that the two algorithms are stable, reliable and simple.