作业帮如何判断一个点是否在一个多边形内部
来源：学生作业帮助网 编辑：作业帮 时间：2024/11/05 20:45:28
如何判断一个点是否在一个多边形内部
如何判断一个点是否在一个多边形内部
如何判断一个点是否在一个多边形内部
在多边性的存储中,每一个多边形都是由一系列连续的点组成,例如保存为数组Polygon[5],表示这个多边形是由5个点组成,这5个点顺序地存储在了数组Polygon之中.就如同走路一般地划线,从数组的第一个点连到第五个点,多边行就构造出来了.
在图形编程中,坐标的利用是不可忽视的.在这里判断一个点是否在多边行内部（可以包括线上）就要利用到各个点的坐标关系.下面开始讨论具体的方法.
对任何事物的分析,我们应该遵守由简入繁的原则,这样才能提高条理性,少犯错误.我们先判断一个点是否在一个三角形内部.一个三角形在一个坐标系（譬如由A、B、C三点组成）中,我们可以通过计算它的有向面积来判断A、B、C三点在坐标系中的顺逆.当然,在此之前我们必须先订立一套计算面积的规则.比如,在笛卡尔坐标系中,我们利用：
S=((A.x-B.x)*(A.y+B.y)+(B.x-C.x)*(B.y+C.y)+(C.x-A.x)*(C.y+B.y))/2
----------------------------------
对于凸多边形而言（以三角形ABC为例）,假设存在一个点D,若这个点在三角形的内部,则以该点为起点,和原多边形的任意两个连续的且尊照多边形组成方向
的点（如DAB、DBC、DCA）组成的三角形讲都是一个方向,如DAB和DBC都是顺时针方向.若这个点在三角形的外部,则会出现DAB、DBC、DCA三个三角形方向不一致的情形,即其中有一个不同于另外两个（如一个顺,两个逆）.到这里我们就知道了如何判断一个点在一个三角形内部的算法,总结一下就是通过判断该点同三角形连续两点组成三角形的顺逆性（归于面积的正负）来得到结果的.
实际上,对于其他的凸多边性也可以用一样的方法,只是这个时候判断的三角形的数目增加了,不管怎么样,只要点在多边形内部他们的顺逆都是一样的.对于凹多边形而言,情况就要相对复杂一些了.此时,判断一个点是否在其内部的计算量会增加比较多.具体算法如下：此时三角形一个个的判断可能会失效,我们应当两个同时判断.即判断该点是否同时在多边形的连续两个三角形之中,相当于是求两个三角形的交集,直到完成多边形封闭.例如,判断P点是否在多边形ABCD之中,依次判断P是否在ABC-BCD、BCD-CDA、CDA-DAB、DAB-ABC各个成对三角形中,P在ABC-BCD中表示P在ABC-BCD的交集之中.这样就可以判断一个点是否在一个凹多边形内部了.
以上说的仅仅是简单多边形而已,在复杂多变形之中（如内洞、飞地等）,还要通过多边形的拓扑运算来得到结果.另外,在凸边形中,还可以进行优化：可以以一个点为中心,分裂多边形为最少个数的三角形,从而得到改进.