【预告】任意多边形区域内外判定

疯人￠衰人

j下任意多边形区域内外的函数完成了，只是还没有测试。偷偷用同志的本本写的，凸多边形部分应该是比较高效的，凹多边形用了递归，效率可能不高，循环版的难度比较高，水平退步不少的我写的比较混乱，于是放弃。
凸多边形的判断采用多边形的某一定点的两条边与全部对角线都在某一180度范围内这个特点，此方法的缺点是边界上的点只能算在内部。
凹多边形采用切割的方法，具体看函数吧……
因为手机无法发函数所以试用版需要去网吧发布，反正没多少人期待吧
以上内容纯属灌水……

该死的番茄

　　 　

疯人￠衰人

凸多边形已经验证成立了

难受死了

凸多边形碰撞检测

还是定向包围盒（2D可以是定向包围矩形） + 分离轴检测算法比较好

LZ说的算法完全不明白....

又稍微看了一下LZ说的.....

难道LZ是做了点和多边形的检测......

难受死了

算了 好像说不太清楚

明天写一个公式吧

疯人￠衰人

[jass]//判断Point是否在多点确定的凸多边形中,返回true为在，false为不在，参数hashtable结构如下:父key为InputKey，子key为0，变量类型为integer，内容为全部点总数。父key为InputKey，变量类型为location，内容为全部点（子key从0开始）。
function ISPointInPolygon takes hashtable Points , integer InputKey , location Point returns boolean
    local integer TempArrayNum = LoadInteger(Points,InputKey,0)
    local integer TempI = 0
    local real TempMaxReal = 0
    local real TempMinReal = 0
    local real TempAngle_0 = AngleBetweenPoints(Point,LoadLocationHandle(Points,InputKey,TempI))
    local real TempAngle_1 = 0
    loop
        exitwhen TempI == TempArrayNum
        set TempAngle_1 = TempAngle_0 - AngleBetweenPoints(Point,LoadLocationHandle(Points,InputKey,TempI))
        if TempAngle_1 < -180 then
            set TempAngle_1 = TempAngle_1 + 360
        endif
        if TempAngle_1 > 180  then
            set TempAngle_1 = TempAngle_1 - 360
        endif
        if TempAngle_1 > TempMaxReal then
            set TempMaxReal = TempAngle_1
        endif
        if TempAngle_1 < TempMinReal then
            set TempMinReal = TempAngle_1
        endif
        set TempI = TempI+1
    endloop
    set TempAngle_1 = TempMaxReal - TempMinReal
    if TempAngle_1 > 180 then
        return true
    else
        return false
    endif
endfunction
[/jass]
这个已经验证成立了

白银酱

n条边的凸多边形只需要计算最多n次的向量外积既可
凹多边形暂时还没想到什么更高效的办发...

zhuzeitou

扫描线算法……似乎图形学学过，不过那个pro完全是抄的，不记得了……
jass的话，可能要考虑坐标的实数精度

zhuzeitou

呃，好像是……

疯人￠衰人

野路子果然不专业……
不过如果不知道顶点顺序，那么必然多边形无法确定，如果确定顺序，且为单一多边形，似乎也很简单了……
对于平行于轴的扫描线，只要一条边的两个点都在被测试的点的一侧，即垂直平行线的轴方向上都大于或小于，都不需判断，其他的都需要判断测试点所在为哪侧。
根据拓补学，只要一侧边与扫描线的交点为偶数，即为外侧，否则内测，