Question

如何判定一个点在多边形的内部还是外部，用delphi怎么编程啊

Answer 1

这个问题需要分情况考虑：
1.如果给定的多边形是凸多边形，则可以按照我之前回答另外一个相似问题的答案来进行判断。这是传送门：【百度软件研发工程师面试题】给定一个凸四边形，如何判断一个点在这个凸四边形内还是外？
2.如果给定的多边形是凹多边形，那么就麻烦一点了。需要这样：先在凹多边形上添加一些边，使得凹多边形变成凸多边形，然后再按照第一步的方法去判断。示例图如下：

对于凹多边形ABCDEFGH，补边BE和FH(图中虚线所示)，则可以构成三个凸多边形：凸多边形ABEFH，凸多边形BCDE和凸多边形FGH，然后判断给定点与这三个凸多边形的关系。
如果给定点在凸多边形ABEFH内部，而在凸多边形BCDE和凸多边形FGH的外部，那么就可以说明给定点在多边形ABCDEFGH的内部了。
下面就分别说明如何判断一个三角形是逆时针还是顺时针，如何判断一个多边形的凹凸性，如何补边，以及如何通过补边构造凸多边形。只要构造出所有的凸多边形，就可以按照上述第二种情况判断了。
判断一个三角形的顺时针还是逆时针
(学过3D渲染的同学应该知道，这个判断很重要，涉及到3D空间中哪些三角形需要渲染，而哪些三角形不需要渲染)
可以利用矢量叉积来判断一个给定的三角形是逆时针还是顺时针。
假设给定三角形的三个顶点A(x1,y1),B(x2,y2),C(x3,y3),构造三角形两边的矢量分别是：
AB=(x2-x1,y2-y1), AC=(x3-x1,y3-y1)
则AB和AC的叉积为：
|x2-x1, y2-y1|
|x3-x1, y3-y1|
值为：r = (x2-x1)(y3-y1) - (y2-y1)(x3-x1)
然后利用右手法则进行判断：
如果r>0,则三角形ABC是逆时针的
如果r<0,则三角形ABC是顺时针的
这样就可以判断一个给定三角形是顺时针还是逆时针了。
(如果这里你发现计算出r=0，那么说明ABC三点共线，即给定点在多边形的边上，可以直接返回)
判断一个多边形的凹凸性。
利用上述判断三角形是顺时针还是逆时针的方法来辅助判断一个多边形的凹凸性。
对于一个给定的多边形，按照逆时针方向遍历该多边形的所有顶点，并放入一个首尾相连的循环链表中。然后从这个循环链表中每次取出相邻三个顶点，判断这个三个顶点构成的三角形是顺时针三角形还是逆时针三角形，如果是逆时针，则说明该三角形三个顶点中位于中间的顶点是凸点；如果是顺时针，则说明位于中间的顶点是凹点。
例如：假设取出的三个顶点是A、B、C，如果三角形ABC是逆时针三角形，则说明顶点B(即位于中间的顶点)是凸点，否则是凹点。然后可以取出D点，通过三角形BCD判断C点的凹凸性，同理D点，E点...最后也可以判断出A点的凹凸性。(通过由最后一个顶点，A点,B点按顺序构成的三角形来判断A点的凹凸性)。如果该多边形所有的顶点经过判断都是凸点，则说明该多边形是凸多边形，否则就是凹多边形。
对于上述示例用图，多边形ABCDEFGH中，点A，B，E，F，H是凸点，点C，D，G是凹点。由于并不是所有的顶点都是凸点，所以多边形ABCDEFGH是凹多边形。
补边
利用上述对给定多边形的每一个顶点的凹凸性的判断来进行补边操作。
补边算法：
1.从存储多边形顶点的循环链表中，找到一个凸点(一定存在这个凸点，即不可能所有顶点都是凹点)
2.从这个顶点开始往后遍历顶点，当遇到的第一个凹点时标记紧邻这个凹点的前一个凸点，因为这个凸点就是所需要补的边的一个顶点，然后继续往后遍历，如果还是凹点，跳过继续遍历，直至找到第一个凸点，那么这个凸点就是所需要补的边的另一个顶点。这样就找出了所需要补的边的两个顶点，就可以确定需要补的一条边了。
3.从找到的凸点开始，重复上述第2步操作。直至回到最开始找到的凸点，则算法结束。这样就可以找到所有需要补的边了。
可以发现，每一条补边，起点和终点都是凸点，中间经过的顶点都是凹点。
上述示例用图中，对于补边BE，顶点B和E都是凸点，而它们中间的顶点C和D则都是凹点。对于补边FH，顶点F和H都是凸点，而它们中间的顶点G则是凹点。
构造凸多边形
利用上述补边来构造凸多边形。
算法如下：
1.对于找到每一条补边，起点和终点都知道，就可以从多边形顶点的循环链表中取出这两个顶点中间的所有的顶点，而这些顶点加上起点和终点就构成了一个外在凸多边形(即不属于原始多边形的多边形)。
示例中，外在凸多边形有凸多边形BCDE和凸多边形FGH。
2.在原始多边形顶点的循环链表中把所有的凹点都去除，只留下凸点。那么这些凸点即构成了原始多边形经补边之后构造的大凸多边形了。
示例中，去除所有凹点C，D，G，则剩下的顶点A,B,E,F,G构成了补边之后的大凸多边形ABEFH
经过上面的所有分析，就可以轻松判断任意一个点是否在一个给定多边形的内部了。

追问

不用这么麻烦吧，计算机图形学里的方法没这么发杂啊

Answer 2

感觉直接算比较难~不如你用图像做好了~把多边形转成像素坐标，画出来，中间填色~然后按坐标查那个点的颜色是不是填充的~是填充的就是在里面 不是就在外面~

Delphi没用过~不过你查查，这种语言应该有绘图包的吧~
当然前提是你那图像坐标值不大~要不然还是老实用图形算吧~

Answer 3

使用最简单的射线法判定。
定理:从多边形内部一点引出一条射线,射线与多边形边界交点个数必然为奇数,否然必然为偶数。
对于任意多边形都适用。
直接随机一个角度生成射线然后枚举多边形每条边询问是否存在交点即可。

Answer 4

你的多边形的定义是什么呢？convex么？