1

私が開発している Web アプリケーションでは、特定の画像の境界を検出し、検出された境界に沿って座標点の配列を生成しています。配列の生成方法により、座標点が特定の順序であるとは限りません。相対位置を決定するために、中心点から任意の 2 つの点のベクトルの外積を計算する比較関数を作成しました。これはクロムでは正常に機能していますが、Firefox 21.0 と IE 10 の両方で、座標ポイントの一部が正しくソートされていません。

比較関数と並べ替え関数のコードは次のとおりです。

function sortCounterClockwise(a, b) {
    return ((isALeftOfB(a, b)) ? 1 : -1);
    //return ((isALeftOfB(a, b)) ? 1 : ((isALeftOfB(b, a)) ? -1 : 0));
}

function isALeftOfB(a, b) {
    var det = (a.x - center.x) * (b.y - center.y) - (b.x - center.x) * (a.y - center.y);
    if (det < 0) {
        return false;
    } else if (det > 0) {
        return true;
    }

    var d1 = (a.x - center.x) * (a.x - center.x) + (a.y - center.y) * (a.y - center.y);
    var d2 = (b.x - center.x) * (b.x - center.x) + (b.y - center.y) * (b.y - center.y);
    return d1 < d2;
}

http://jsfiddle.net/Zsz3K/1/で完全に機能する jsfiddle を作成しました。Chrome で表示すると、モンタナ州の大まかな概要が表示されますが、FF と IE では次のようになります。座標点が混じっています。

上記のアルゴリズムのさまざまなバリエーションを試しましたが、FFまたはIEのすべてのテストケースで動作させることができず、クロムのみです。以前の反復では、IE と FF が並べ替えの周期的な性質によってつまずいたと考えて、1 つのポイントを参照ポイントとして固定しました。私のテストケースは米国の地図をアップロードしており、クロムはすべての国境を正しく検出して追跡することができます。プログラムを変更して、座標配列が中心点からシータを増減してソートされることを保証することはできません。実際には、ここにリストされているブラウザーで正しく機能するこれらの座標をソートする一貫した方法を見つける必要があります。私が知る限り、これは FF と IE のバグのように思えます。結果はブラウザー間で不変であるはずの数学的な結果に基づいているためです。

編集：答えを答えに移動しました。

4

1 に答える 1

0

私は漠然と、私自身の質問に答えると思われる jsfiddle の更新を作成しました。 http://jsfiddle.net/Zsz3K/3/

簡単なバブル ソートを大まかに行い、中心点に対する相対的な配置に関する比較関数の追加条件を追加しました。これは 3 つのブラウザーすべてで機能します。FF と IE での .sort() の実装は、この種のデータではうまく機能しないようです。jquery の内臓に飛び込む時間があればいいのにと思いますが、そうではありません。したがって、jquery で空間座標を並べ替えるという問題に誰かが遭遇した場合は、組み込みの並べ替え関数に頼らないでください。ただし、概念実証以外のものとして、バニラ バブル 並べ替えよりも効率的なものをお勧めします。 . 奇妙なことに、組み込みの .sort() を比較子で使用すると、クロムが一貫して機能しただけでなく、機能しませんでした。

そして、jsfiddle にリンクするためのコード要件を満たすためだけに、動作する並べ替えと比較子を次に示します。

do {
    swapped = false;
    for (var i=0; i < points.length-1; i++) {
        if (isALeftOfB(points[i + 1], points[i])) {
            var temp = points[i];
            points[i] = points[i+1];
            points[i+1] = temp;
            swapped = true;
        }
    }
} while (swapped);

function isALeftOfB(a, b) {
if (a.y <= center.y && b.y > center.y) {
        return true;
    } else if (a.y == center.y && b.y == center.y) {
        return a.x < b.x
    }
    var det = (a.x - center.x) * (b.y - center.y) - (b.x - center.x) * (a.y - center.y);
    if (det < 0) {
        return false;
    } else if (det > 0) {
        return true;
    }

    var d1 = (a.x - center.x) * (a.x - center.x) + (a.y - center.y) * (a.y - center.y);
    var d2 = (b.x - center.x) * (b.x - center.x) + (b.y - center.y) * (b.y - center.y);
    return d1 < d2;
}
于 2013-05-21T09:44:53.430 に答える