回复 40# tommytangtang
一下内容是原文照抄（有小小修改；我终于也沦为搬运工了啊……）
点与凸多边形之间的测试
假设n边凸多边形顶点V0, V1, …,Vn-1 呈逆时针排列。通过测试顶点P与方向直线V0、Vk（k=n/2）
的位置关系，可将多边形的测试范围缩至一半。该过程重复执行并相应地调整K值，直至发现顶点P位于多
边形的外部或位于有向直线V0Vk ~ V0Vk+1之间。对于后者，若顶点P位于有向直线VkVk+1的左侧（呈
逆时针排列），则其位于多边形内部。
以一个8条边的凸多边形作为例。首先，顶点P针对直线V0V4进行测试，并将多边形顶点范围降至一半。
由于顶点P位于A的左侧，所以丢弃多边形的右半部分，并继续对左半部分执行相同处。下一步，在顶点P与
直线B之间执行测试，最后对直线C进行测试，此时，顶点P位于邻接顶点构成的两条直线之间。最后，顶点
P与该邻接顶点构成的直线进行测试。
测试结果为：顶点P位于多边形内部。
[attach]7612[/attach]
图为：凸多边形顶点的二分搜索使得点P的包含测试的时间复杂度为O(log n)（这里测试了4条边：A~D）
另外，预计算函数TriangleIsCCW()将计算三角形顶点是否为逆时针方向排列。该测试的高效实现 方法如下列代码所示：
──────────────────────────────────────────┐
// Test if point p lies inside ccw-specified convex n-gon given by vertices v[] │
int PointInConvexPolygon(Point p, int n, Point v[]) │
{ │
// Do binary search over polygon vertices to find the fan triangle │
// (v[0], v[low], v[high]) the point p lies within the near sides of │
int low = 0, high = n; │
do { │
int mid = (low + high) / 2; │
if (TriangleIsCCW(v[0], v[mid], p)) │
low = mid; │
else │
high = mid; │
} while (low + 1 < high); │
│
// If point outside last (or first) edge, then it is not inside the n-gon │
if (low == 0 || high == n) return 0; │
│
// p is inside the polygon if it is left of │
// the directed edge from v[low] to v[high] │
return TriangleIsCCW(v[low], v[high], p); │
} │
──────────────────────────────────────────┘
该点包含测试方法类似[Preparata85]中所描述的相关算法结构，其中n边多边形内部也存在一个与 此处的顶点V0对应。
－－－－－－－－－以下内容可能造成不适，请[跳过]或者[对上面内容进行消化]后再访问－－－－－－－－
该算法通过多边形的一个原点和其他顶点，对多边形进行划分（二分），通过TriangleIsCCW()函数
逐渐找到最靠近点P的两个边界，在示例中最后找到为：V0->V5 和 V0->V6 。这个过程手工演算一 次就知道原理了。
最后一步 return TriangleIsCCW(v[low], v[high], p); 即为判断：如果V5->V6->P 呈逆时针顺序， 则点P在多边形内部。 TriangleIsCCW() 函数判断传入的三个顶点数据是否呈逆时针排列，书中没有给出，但是在网上找到：
─────────────────────────────┐
template<class T> │
T Cross(T x0, T y0, T x1, T y1) { │
//|x0 y0| = |a b| │
//|x1 y1| |c d| │
│
//ad * bc │
//x0 * y1 - x1 * y0 │
│
return (x0 * y1) - (y0 * x1); │
} │
│
template<class T> │
bool triangleIsCCW( │
T x0, T y0, │
T x1, T y1, │
T x2, T y2) { │
auto cross = (Cross<T>(x1-x0,y1-y0,x2-x0,y2-y0)); │
return cross > 0; │
} │
─────────────────────────────┘
原理就是对传入的三个顶点坐标进行向量运算（以P为原点，计算出另外两个点 的相对坐标，视为向量ａ、ｂ，计算这两个向量的向量积（cross product）） （高等数学第一章有介绍这个计算和性质，或者在网上搜索：叉积……）
计算向量积得到的是垂直于ａ和ｂ所在平面的向量V，遵循右手法则：右手握住V 向量（垂直于ａ和ｂ），手指从ａ向ｂ环绕，大拇指的方向和向量方向一致。 也就是如果ａ-> ｂ->原点p 是逆时针方向则V>0 ，是反方向则V<0，如果ａｂ平 行或者其中一方为0，则V=0
[attach]7613[/attach] | 
发表于 2014-8-18 21:26
| 
发表于 2014-8-18 21:37
| 
发表于 2014-8-18 22:05
| 
发表于 2014-8-18 22:39
| 
Crlf确定加的是技术分吗……