判断某点是否在封闭曲线之内——lineGirl碰撞算法讨论

newer

　　核心提示：lineGirl游戏是一类画线游戏,游戏方法是在一幅图上画线'圈地',如果画线未封闭之前被怪碰到则回到起点并失去生命一次.目标是在生命全部失去前圈够足够百分比的'地'.闪客帝国上有朋友做过此游戏,点击...
lineGirl游戏是一类画线游戏,游戏方法是在一幅图上画线"圈地",如果画线未封闭之前被怪碰到则回到起点并失去生命一次.目标是在生命全部失去前圈够足够百分比的"地".闪客帝国上有朋友做过此游戏,点击进入游戏"天蚕变之希望篇"
这里仅就其中怪物碰撞到已划定的"地"反弹回来的算法简单讨论一下.
怪物碰到"地"被反弹,如果将"地"看作一封闭曲线,那么问题转变为判断怪是否进入封闭曲线,如果进入则被反弹(弹出曲线外).再进一步抽象,把怪看作一个质点(事实上应该把怪的四边看作四个质点,任一个进入封闭曲线后即被反弹,但这里不影响核心算法),那么问题转变为如何判断某点是否在封闭曲线内.
明确了核心算法后就可以开始用数学方法讨论了,不过别担心,我不会写公式的:)
首先看看一般情况,请看下图(见图一):

图一:一般情况判断某点是否在封闭曲线内.
如图所示,A点在曲线S内,那么可以证明,由A点作任一方向的射线,该射线与曲线边的交点有奇数个.而相反如果在曲线S外,如点B,则交点有偶数个.这个定理很好理解,这里不作多述.
好了,明确了这条定理后我们就有方向了,考虑一下lineGirl类型的游戏中所画的封闭曲线并不是任意的,而是只有直角的,线条只有水平和竖直两种,那么我们可以把射线方向确定一下,比如限定为水平方向,如下图所示(见图二):

图二:直角多边形(曲线)中判断某点是否在其内.
如上图,问题关键是:如何判断某点(比如A点,它在S内)是否在曲线S内呢?这里我们必段假定曲线是已知的,也就是曲线上各顶点坐标已知,且各点连接顺序已知,我们观察一下S的特点可以发现,如果A点纵坐标在某一段竖直线段两个端点坐标纵坐标之间,比如CD线段,那么与该线段必有一个交点(即交点1).否则则没有交点,比如线段AB.根据顶点顺序可以顺次查找符合条件的线段(两端点必为相邻顶点),如果总线段数为奇数,则该点在S内.
另外,对于点是否在线上可以单列出来首先判断,虽然可以把在线上作为一种在曲线内的特殊情况,但是单列出来也不会太麻烦,而且代码可能更清晰.这都不是问题.
有了以上两种一般情况的铺垫,下面我们可以很容易地解决lineGirl中的实际问题了.这是因为在实际制作游戏过程中我们可以使用二维数组.
稍微解释一下如何使用二维数组来构造游戏:
我们控制人物移动和怪物移动的最小单位为某一定值,这样就可以以该值为最单位将场景分为若干小块,每一小块都是二维数组中的一个元素."圈地"就抽象为在二维数组中作标记,标记越多"地"也图得越多.而且计算"圈地"的百分比也较容易.
在数组下讨论判断就更容易了,如下图(见图三):

图三:数组情况下对于封闭曲线的判断.
点A在曲线内,每一方格代表一个数组元素,人物移动的最小长度就是方格的边长.以A为端点作水平射线也就是取出A点所代表的数组元素中的同行脚码比A小的元素,如图所示,一共有三个交点.观察一下这三个交点可以发现这样的判断规律:交点左右一边是未圈中地(即在曲线外),另一边是圈中地(即在曲线内),由于不存在"曲线上",所以我们只要数清楚这样的前一元素是未圈中地/圈中地,后一元素是圈中地/未圈中地的个数就可以了,更进一步,圈中地和未圈中地把射线分为了若干段,比如A的射线分为了两段属于圈中地,两段属于未圈中地,如果未圈中地的段数为偶数段,则点A在曲线内(圈中地内),反之如果为奇数则在圈中地外.
以上判断算法可纯算作个人笔记,因为我还没有去做一个DEMO,有朋友正在做,所以只是一点儿意见而已.不对之处希听指正.

WhoCanSay

N版，快弄成lisp吧！！！

newer

WhoCanSay 发表于 2016-6-21 08:17
N版，快弄成lisp吧！！！

这个就是 射线法吧，论坛有的。

/db_自贡黄明儒_

newer 发表于 2016-6-21 08:30
这个就是 射线法吧，论坛有的。

对于同一封闭图形，使用BOUNDARY有时成功，有时不成功，即使图形放大也是这样。说明BOUNDARY可能不是射线法。我怀疑（当然没有任何根据）是取屏上各点颜色来判断的

/db_自贡黄明儒_

newer 发表于 2016-6-21 08:30
这个就是 射线法吧，论坛有的。

应该与你说的射线法，我找出来改了改

2. 
   
3. ;;164.43 [功能] 判断点是否在曲线内(射线法)
   
4. ;;线内T 线上0　线外nil
   
5. ;;(InCurve (setq pt (getpoint)) (setq e (car (entsel))))
   
6. (DEFUN InCurve (pt e / _EntmakeXlineX FLAG i TMPRAY)
   
7.   (defun _EntmakeXlineX        (pt)
   
8.     (entmakeX (list '(0 . "XLINE")
   
9.                     '(100 . "AcDbEntity")
   
10.                     '(100 . "AcDbXline")
    
11.                     (cons 10 pt)
    
12.                     (cons 11 '(1 0 0))
    
13.               )
    
14.     )
    
15.   )
    
16.   (IF (EQUAL pt (VLAX-CURVE-GETCLOSESTPOINTTO e pt) 1E-6)
    
17.     0        ;在线上
    
18.     (PROGN
    
19.       (SETQ e (VLAX-ENAME->VLA-OBJECT e))
    
20.       (SETQ TmpRay (VLAX-ENAME->VLA-OBJECT (_EntmakeXlineX pt)))
    
21.       (SETQ pt (VLAX-3D-POINT pt))
    
22.       (SETQ i 0)
    
23.       (setq Flag T)      
    
24.       (while (and (/= 180 i) Flag)       
    
25.         ;;如果Flag 为nil或者长度为3，则结束;
    
26.         (if (and (setq Flag (VLAX-INVOKE e 'INTERSECTWITH TmpRay ACEXTENDNONE))
    
27.                  (/= (LENGTH Flag) 3)
    
28.             )
    
29.           (progn (setq i (+ i 15)) (VLA-ROTATE TmpRay pt (/ PI 15)));采用12度
    
30.           (setq Flag nil)
    
31.         )
    
32.       )
    
33.       (VLA-DELETE TmpRay)
    
34.       (if Flag T)
    
35.     )
    
36.   )
    
37. )
    
38. 
    

<br /> ;;164.43 [功能] 判断点是否在曲线内(射线法)<br /> ;;线内T 线上0　线外nil<br /> ;;(InCurve (setq pt (getpoint)) (setq e (car (entsel))))<br /> (DEFUN InCurve (pt e / _EntmakeXlineX FLAG i TMPRAY)<br />   (defun _EntmakeXlineX        (pt)<br />     (entmakeX (list '(0 . "XLINE")<br />                     '(100 . "AcDbEntity")<br />                     '(100 . "AcDbXline")<br />                     (cons 10 pt)<br />                     (cons 11 '(1 0 0))<br />               )<br />     )<br />   )<br />   (IF (EQUAL pt (VLAX-CURVE-GETCLOSESTPOINTTO e pt) 1E-6)<br />     0        ;在线上<br />     (PROGN<br />       (SETQ e (VLAX-ENAME->VLA-OBJECT e))<br />       (SETQ TmpRay (VLAX-ENAME->VLA-OBJECT (_EntmakeXlineX pt)))<br />       (SETQ pt (VLAX-3D-POINT pt))<br />       (SETQ i 0)<br />       (setq Flag T)      <br />       (while (and (/= 180 i) Flag)        <br />         ;;如果Flag 为nil或者长度为3，则结束;<br />         (if (and (setq Flag (VLAX-INVOKE e 'INTERSECTWITH TmpRay ACEXTENDNONE))<br />                  (/= (LENGTH Flag) 3)<br />             )<br />           (progn (setq i (+ i 15)) (VLA-ROTATE TmpRay pt (/ PI 15)));采用12度<br />           (setq Flag nil)<br />         )<br />       )<br />       (VLA-DELETE TmpRay)<br />       (if Flag T)<br />     )<br />   )<br /> )<br /> <br />

xmzhangzhilin

射线法有缺陷，一般情况下点在外，则交点有偶数个，但是有种情况是射线刚好经过曲线的拐点（或与曲线相切），则交点变为奇数个

剑.

xmzhangzhilin 发表于 2018-5-2 11:09
射线法有缺陷，一般情况下点在外，则交点有偶数个，但是有种情况是射线刚好经过曲线的拐点（或与曲线相切） ...

加一个判断条件：所得交点是否为曲线的顶点

xinxirong

谁说相切点就一定是顶点
来自: 微社区

lsthz

研究研究！
来自: 微社区

434939575

/db_自贡黄明儒_ 发表于 2016-6-24 09:20
应该与你说的射线法，我找出来改了改

黄大师，这个spl拟合多点线，判断外有误，返回 t.

434939575

/db_自贡黄明儒_ 发表于 2016-6-24 09:20
应该与你说的射线法，我找出来改了改

黄大师，这个spl拟合多点线，判断外有误，返回 t.  有回弯的。

aimisiyou

P点在封闭样条曲线外，但程序运行结果是T（即在内部）。