最近做游戏要用到关于这个知识~高数不好~伤脑筋~

给定多边形的n个顶点坐标(x1,y1),(x2,y2),(x3,y3)……(xn,yn)按顺序相连组成一个多边形(不考虑连线过程出现相交而把多边形分割的情况)~
和已知点(x,y)
如何判断该点是否在多边形区域内？~

感觉可以分成多个三角形来判断~但问题时怎么判断该点是否在一个三角形区域内呢~

最好有一个完整的代码~~~~~~

[此贴子已经被作者于2017-4-2 22:59编辑过]

单个三角形求解好做~但感觉难点在于多边形可能是不规则的~任意三点连成的三角形不一定在多边形区域內~~~

多边形  是 凹 的 还是 凸的

如果是凸的 应该可以根据  求点 （x,y）的 水平 和 垂直 线

与多边形的 交点数量

2、3个交点的 在顶点、边上

4个交点的  可根据交点的范围进行判定； （x,y1） ,(x,y2), (x3,y),(x4,y)

当 y1 > y2,  x1 > x2, 如果 y1 > y > y2, x1 > x > x2 则在多边形内



不在上面条件中的  就不在（凸）多边形中，  时间复杂度为O(n)  n为边的数量

高数是 大学的吧

这个好像是初中的 二元一次方程，  属于几何？

凸的我试试应该可以求解~但感觉如果是凹的则比较复杂了~
解到凸的现在已经够用了~也算可以过吧~但如果能找到凹多边形(任意多边形)的解法就更好了~

多谢指点突然明白如何求解凸多边形了
思路就是把每一条边的两点一元方程式列出来~然后就作水平线和垂直线(其实只要不重合的就可以行得通了)~

先判断该点是否在某直线(含取值范围)上~
如果在则在边界上~
如果不在~

如果有一条直线连续经过两个点则不在该凸多边形里面~

如果小于4个交点则不在该凸多边形里面~

如果有4个交点~

则如果((x1-x)*(x2-x)<0)&&((y1-y)*(y2-y)<0)则在凸多边形里面~
否则不在凸多边形里面~

通用的

列举垂直方向的 交点  假设  与 m 条线段有交点 m 个  交点分别为（x, y1）,(x，y2） 。。。 （x, ym）

通过 排序 可以满足  y1 < y2 < ... < ym

现在就是区分 (x, y1) 到 （x, y2）之间这段， 即相邻的2点连线 是否需要范围内还是外

可以给这些排好序的交点 加上一个附加属性， 方向性，   例如， 第一个顶点（x, y1）  当 (x, y1) 不属于 多边形的顶点 则方向定位
外->内，  当 （x,y1）属于多边形的顶点 则方向定为（顶点）； 第二个顶点（x,y2） 当（x, y2）不属于 多边形的顶点 则方向定位，依赖前一个（x,y1）
的方向， 如果（x, y1）为 外->内， 则（x, y2）定位 内到外， 否则定为 外->内， 如果（x,y2）属于多边形的顶点,则方向定位(顶点）；


总结， 交点的方向是交替的 先是（外->内） 然后 再是 (内->外） ，这样子循环的， 但是  这些属性的交点间 可以随意穿插 交点方向为（顶点） 的点。
   然后就是方向的识别（两点连线是否属于多边形范围内）   
  1、（外->内） 连 （内->外） 属于 范围内
  2、（外->内） 连 （顶点）  属于 范围内
  
  3、 （顶点）连 （顶点） 属于范围 依赖 上次识别的范围属性 如果 没有上次的状态  即为（表示 第一个和第二个点都是 顶点） 范围外
  4、 （顶点）连 （外->内） 属于范围外
  5、 （顶点）连 （内->外） 属于方位内

  6、 （内->外）连 （外->内） 属于 范围外
  7、 （内->外）连 （顶点） 属于 范围外


然后就是进行 y 范围的对比了。 y 落在什么范围就是 就可以直接看出这个点属不属于 多边形的范围了

[此贴子已经被作者于2017-4-3 00:41编辑过]

我还是先去看看凸多边形~
感觉6楼的思路还可以优化~
凸多边形的一个重要的性质是:
过凸多边形上的任意一个顶点作任意一条不与边界重合的直线最多把该多边形分割成两个部分~

所以判断凸多边形的方法就可以变得很简单了~
先判断该点在不在边界上~
如果不在~
作一条垂直x轴的直线~判断交点个数~

如果有两个交点纵坐标为y1,y2并满足(y1-y)*(y2-y)<0这个条件就行了~

凹多边形我还是要慢慢理解一下~

[此贴子已经被作者于2017-4-3 02:12编辑过]

我现在也能理解凹多边形了~就像你说的，作一条垂直的直线然后判断交点个数~
先判断该点是否在边界上~
如果不在~
先把坐标刚好在顶点上而且连接顶点的两条线段在直线的同侧这种特殊情况的顶点排除掉~
如果该直线刚好与两个顶点之间的连线重合则取其中一个顶点~

得到点y1,y2,y3……yn~

然后对y1,y2,y3……yn和y
进行排序~

看看y的排位是多少~
设y的排位是i(i从下标1开始)~
如果y的排位是偶数则在多边形里面~
否则就在多边形外面~

PS:实际上排序还可以简化一下~取相邻的两个点x1,x2~如果(x1-x)*(x2-x)<=0并且该顶点相连的两条直线不在同侧0则记录该两个交点是否在直线的上方~最后看看上方个数是否为偶数就行了~

[此贴子已经被作者于2017-4-3 03:03编辑过]

说的比唱的好听，代码实现呢？
仔细想来，纯凸的封闭多边形好判断，只要判断该点与其他顶点的连线是否与多边形的某条边是否相交，未与任何边相交则在多边形内，否则在外。
如果是非常变态的凹多边形，如一个螺旋的封闭多边形，则判断相交则实在麻烦，我能想到的算法是在最小区域矩形框内从要判断的点开始着色，如果着色过程中碰到矩形边框则说明该点在多边形外面，如果着色完成都碰不到矩形边框，则说明在多边形内。
矩形区域内着色就是深度搜索算法，考虑栈空间，也可用堆空间的广度搜索。