点包含检测

在2D中，如何判断一个点是否被包含在任意凸多边形之内呢？最为直接的办法是半空间检测。基本上，可以想像将每条边延长至无限长，从而平面被分割成两半，如图所示。

如果检测的点在每个半空间的内侧，那么根据凸多边形的性质，点一定是在多边形内部。此时只需找到一种测试方法来判断点在一条直线的哪一侧。

如果将直线以一定顺序进行标记，转换为向量，之后可以将直线想像为平面，使用点积操作符，即可确定点在平面的哪一侧，还是恰好就在平面上（参考《点到平面的距离》）。