判断点在多边形内部、在多边形边界上还是在多边形外部
在网上已经有大量判断点是否在多边形内部的算法介绍。
如何判断一个点是否在多边形内部？
（1）面积和判别法：判断目标点与多边形的每条边组成的三角形面积和是否等于该多边形，相等则在多边形内部。
（2）夹角和判别法：判断目标点与所有边的夹角和是否为360度，为360度则在多边形内部。
（3）引射线法：从目标点出发引一条射线，看这条射线和多边形所有边的交点数目。如果有奇数个交点，则说明在内部，如果有偶数个交点，则说明在外部。
CGAL提供了相关的方法，可以避免日常使用时重复造轮子。
template<class Traits_P, class Container_P = std::vector<typename Traits_P::Point_2>> Bounded_side CGAL::Polygon_2< Traits_P, Container_P >::bounded_side(const Point_2 & value) const；
点在多边形内部时返回CGAL::ON_BOUNDED_SIDE；点在多边形边上时返回CGAL::ON_BOUNDARY；点在多边形外部时返回ON_UNBOUNDED_SIDE。
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Polygon_2_algorithms.h>
#include <iostream>
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef K::Point_2 Point;
void check_inside(Point pt, Point *pgn_begin, Point *pgn_end, K traits) {
std::cout << "The point " << pt;
switch(CGAL::bounded_side_2(pgn_begin, pgn_end,pt, traits)) {
case CGAL::ON_BOUNDED_SIDE :
std::cout << " is inside the polygon.\n";
break;
case CGAL::ON_BOUNDARY:
std::cout << " is on the polygon boundary.\n";
break;
case CGAL::ON_UNBOUNDED_SIDE:
std::cout << " is outside the polygon.\n";
break;
}
}
int main() {
Point points[] = { Point(0,0), Point(5.1,0), Point(1,1), Point(0.5,6)};
// check if the polygon is simple.
std::cout << "The polygon is "
<< (CGAL::is_simple_2(points, points+4, K()) ? "" : "not ")
<< "simple." << std::endl;
check_inside(Point(0.5, 0.5), points, points+4, K());
check_inside(Point(1.5, 2.5), points, points+4, K());
check_inside(Point(2.5, 0), points, points+4, K());
return 0;
}
上述算法也是有前置条件的，要求多边形必须为简单多边形，简单多边形如何判断在<<判断多边形为顺时针或者逆时针>>中记录过，不再重复记录。
参考材料
https://doc.cgal.org/latest/Polygon/classCGAL_1_1Polygon__2.html#aff9f5e227e90bb285c7b3fbd8cb23369
https://www.cnblogs.com/luxiaoxun/p/3722358.html
除非注明，否则均为[半杯茶的小酒杯]原创文章，转载必须以链接形式标明本文链接