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

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

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

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

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

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

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

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

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

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

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

如果有4个交点~

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

我还是先去看看凸多边形~
感觉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编辑过]

我初初还以为很复杂~但想到了原理后就感觉很简单
可以来看看我说的有什么问题~

过一个多边形作一条直线使获得n个交点~然后把交点在顶点上并且与顶点相连的两条线段在直线的同侧则的交点排除~然后按交点坐标排序~第2*k-1到第2*k个交点之间的线段就在多边形的内部~这对一切的多边形包括凹多边形也适用~可以用笔纸比划一下~

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

刚刚在网上搜了一下资料~资料给出三种方法~其实我那个方法优化一下就是引射线法~也是要经过特殊处理的~

http://blog.
~

我最初就是这样思考的~你这么一说就回到原点了~~

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

这种属于特殊情况~有两个交点为顶点且连接顶点的两条线段在直线的同侧应舍弃这样的顶点~引射线法要特殊处理~
所以当两个交点处理~还要先判断所求点点是否在边界上~

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