2

n多角形と長さの線k(でx,yと 角度) が与えられた場合a、衝突した多角形の側面 (ある場合) を検出するアルゴリズムはありますか? これまでのところ、ポリゴンの外側にあるかどうかをテストしx,y、次にポリゴンの各エッジを繰り返し処理して、各端までの距離を計算することに頼ってきました。これは、私が作成した世界を示すJS Fiddleです。

以下は JavaScript です (HTML と CSS はコピーする価値はありません)。

var eventLoop,
    maxVelocity = 10,
    agility = 5,
    baseLength = 5,
    degree = ((2*Math.PI)/360),
    world = document.getElementById('world'),
    context = world.getContext("2d"),
    boundry = [[180, 120],[240, 60],[360, 40],[420, 120],[360, 220],[350, 240],[360, 265],[470,360],[450,480],[360,540],[240,550],[140,480],[120,470],[100,360],[120,300],[220,240],[240,220]],
    camera = {
        location: {
            x:300,
            y:90
        },
        angle: 0,
        velocity: 0
    },
    engine = {
        drawWorld: function(shape, context) {
            var point,
                index,
                size = shape.length;

            context.clearRect(0, 0, world.width, world.height);
            context.beginPath();
            for(index = 0; index < size; index++) {
                point = shape[index];
                if(index == 0) {
                    context.moveTo(point[0], point[1]);
                } else {
                    context.lineTo(point[0], point[1]);
                }
            }
            context.closePath();
            context.stroke();
        },
        drawCamera: function(camera, context) {
            var a = camera.location,
                b = this.calcNextPoint(camera, 1);

            context.beginPath();
            context.moveTo(a.x, a.y);
            context.lineTo(b.x, b.y);
            context.stroke();

            context.beginPath();
            context.arc(a.x, a.y, baseLength, 0, Math.PI*2, true); 
            context.closePath();
            context.stroke();
        },
        calcNextPoint: function(camera, moment) {
            return {
                x: camera.location.x + ((camera.velocity*(1/moment))*Math.sin(camera.angle)),
                y: camera.location.y + ((camera.velocity*(1/moment))*(Math.cos(camera.angle)))
            };
        },
        isInside: function(point, shape) {
            var i, j, c = 0;
            for (i = 0, j = shape.length - 1; i < shape.length; j = i++) {
                if (((shape[i][1] > point.y) != (shape[j][1] > point.y)) && (point.x < (shape[j][0] - shape[i][0]) * (point.y - shape[i][1]) / (shape[j][1] - shape[i][1]) + shape[i][0])) {
                     c = !c;
                }
            }
            return c;
        }
    };

document.onkeydown = function(e) {
    e = e || window.event;
    if (e.keyCode == '37') {
        // left arrow
        camera.angle += degree*agility;
    }
    else if (e.keyCode == '39') {
        // right arrow
        camera.angle -= degree*agility;
    }
    else if (e.keyCode == '38') {
        // up arrow
        camera.velocity += 1;
        if(camera.velocity > maxVelocity) {
            camera.velocity = maxVelocity;
        }
    }
    else if (e.keyCode == '40') {
        // down arrow
        camera.velocity -= 1;
        if(camera.velocity < 0) {
            camera.velocity = 0;
        }
    }
}

engine.drawWorld(boundry, context);
engine.drawCamera(camera, context);

eventLoop = setInterval(function() {
    engine.drawWorld(boundry, context);
    engine.drawCamera(camera, context);
    if(engine.isInside(camera.location, boundry)) {
        camera.location = engine.calcNextPoint(camera, 1);
    }
}, 100);

私は、ThatGameCompany によるゲームFlowerの 2 次元バージョンをモデル化する JavaScript をいじくり回してきました。最終的には、Oculus Rift バージョンを試して実装したいと考えています。私が取り組んでいる次の問題は、エッジに衝突したプレイヤーをポリゴンに戻すルーチンです。

4

3 に答える 3

6

つまり、基本的には、ポリゴンのどのエッジが特定の線と交差しているかを知りたいと思いますよね?

これは、エッジを表すいくつかの線形方程式(より正確にはinequations )の非常に単純な処理です。操作の優れた実装が既にありinside、これもそれを行います。これらすべてのアルゴリズムの共通点は、線のどちら側にあるかを比較することです[x1, y1]。[x2, y2]ポイント[x, y]は次のとおりです。

compare = function (a, b) { // classical compare function, returns -1, 0, 1
    return a < b ? -1 : (a == b ? 0 : 1);
}
...
_lineSide: function (x, y, x1, y1, x2, y2) {
    return compare(x - x1, (x2 - x1) * (y - y1) / (y2 - y1));
}

この関数は[x, y]、ラインの片側にある場合は[x1, y1]-1を返し[x2, y2]、反対側の場合は 1 を返し、ライン上に正確にある場合は 0 を返します。ここでは、どちらがどちらであるかは重要ではなく、それらを分離するだけです。y2 - y1ただし、がゼロまたはゼロに近い場合、これは機能しません。その場合、状況を xy 反転する必要があります。

lineSide: function (x, y, x1, y1, x2, y2) {
    var eps = 1e-20; // some very small number
    if (Math.abs(y2 - y1) > eps)       // this way we avoid division by small number
        return _lineSide(x, y, x1, y1, x2, y2);
    else if (Math.abs(x2 - x1) > eps)  // flip the situation for horizontal lines
        return _lineSide(y, x, y1, x1, y2, x2);
    else // edge has close-to-zero length!
        throw new this.zeroLengthLineException()
},
zeroLengthLineException: function () {},

[x1, y1]2 つの線-[x2, y2]と[x3, y3]-が交差するかどうかをテストするの[x4, y4]は非常に簡単です。ifと - の反対側に横たわり、 if と-の反対[x1, y1]側に[x2, y2]横たわるだけです。はいの場合、線は交差します。[x3, y3][x4, y4][x3, y3][x4, y4][x1, y1][x2, y2]

// proper: true/false (default false) - if we want proper intersection, i.e. just 
// touching doesn't count
linesIntersect: function (x1, y1, x2, y2, x3, y3, x4, y4, proper) {
    var min_diff = proper ? 2 : 1;
    return Math.abs(this.lineSide(x1, y1, x3, y3, x4, y4) - 
                    this.lineSide(x2, y2, x3, y3, x4, y4)) >= min_diff 
        && Math.abs(this.lineSide(x3, y3, x1, y1, x2, y2) - 
                    this.lineSide(x4, y4, x1, y1, x2, y2)) >= min_diff;
},

最終的な解決策 - http://jsfiddle.net/gLTpT/7/

さて、最終的な解決策linesIntersectは簡単です。ループを呼び出して、指定されたラインとすべてのポリゴン エッジとの交点をチェックするだけです。

http://jsfiddle.net/gLTpT/7/

ここに画像の説明を入力

于 2014-01-03T16:03:32.510 に答える