5

CPU時間の25％をむさぼり食う方法があります。このメソッドを 1 秒あたり約 27,000 回呼び出します。(ええ、頻繁に更新されているため、多くの呼び出しがあります)。2 つのポリゴンが重なっているかどうかを検出するより高速な方法を誰かが知っているかどうか疑問に思っています。基本的に、画面上で動いているオブジェクトと画面上で静止しているオブジェクトをチェックする必要があります。私は PathGeometry を使用しており、以下の 2 つの呼び出しは、プログラムが使用する CPU 時間の 25% を使用しています。私が渡している PointCollection オブジェクトには、ポリゴンの 4 つのコーナーを表す 4 つのポイントが含まれています。それらは長方形の領域を作成しない場合がありますが、すべての点が接続されています。形は台形になると思います。

これらのメソッドは短く、実装が非常に簡単でしたが、以下のコードよりも速く実行できる場合は、より複雑なソリューションを選択したいと思うかもしれません. 何か案は？

public static bool PointCollectionsOverlap(PointCollection area1, PointCollection area2)
{
    PathGeometry pathGeometry1 = GetPathGeometry(area1);
    PathGeometry pathGeometry2 = GetPathGeometry(area2);
    return pathGeometry1.FillContainsWithDetail(pathGeometry2) != IntersectionDetail.Empty;
}

public static PathGeometry GetPathGeometry(PointCollection polygonCorners)
{
    List<PathSegment> pathSegments = new List<PathSegment> 
                                         { new PolyLineSegment(polygonCorners, true) };
    PathGeometry pathGeometry = new PathGeometry();
    pathGeometry.Figures.Add(new PathFigure(polygonCorners[0], pathSegments, true));
    return pathGeometry;
}
4

1 に答える 1

10

わかりました、多くの調査と多くの部分的な答えを見つけた後、質問に完全に答えたものはありませんでした.私はより速い方法を見つけました.それは実際には古い方法よりも約4.6倍高速です.

この速度をテストするための特別なテストアプリを作成しました。テストアプリはこちらから入手できます。ダウンロードすると、アプリの上部にチェックボックスが表示されます。チェックを入れたり外したりして、古い方法と新しい方法を切り替えます。アプリは一連のランダムなポリゴンを生成し、ポリゴンが別のポリゴンと交差すると、ポリゴンの境界線が白に変わります。[再描画] ボタンの左にある数字は、ポリゴン数、辺の最大長、正方形からの最大オフセットを入力できるようにするためのものです (正方形を減らして奇妙な形にするため)。[更新] を押して、入力した設定で新しいポリゴンをクリアして再生成します。

とにかく、ここに 2 つの異なる実装のコードがあります。各ポリゴンを構成するポイントのコレクションを渡します。古い方法は少ないコードを使用しますが、新しい方法よりも4.6 倍遅くなります。

ああ、簡単なメモ。新しい方法には、「PointIsInsidePolygon」への呼び出しがいくつかあります。これがないと、1 つのポリゴンが別のポリゴン内に完全に含まれている場合にメソッドが false を返すため、これらが必要でした。しかし、PointIsInsidePolygon メソッドはその問題を解決します。

これがすべて、ポリゴンのインターセプトとオーバーラップで他の誰かを助けることを願っています.

古い方法 (4.6 倍遅い。 はい、本当に 4.6 倍遅い):

public static bool PointCollectionsOverlap_Slow(PointCollection area1, PointCollection area2)
{
    PathGeometry pathGeometry1 = GetPathGeometry(area1);
    PathGeometry pathGeometry2 = GetPathGeometry(area2);
    bool result = pathGeometry1.FillContainsWithDetail(pathGeometry2) != IntersectionDetail.Empty;
    return result;
}

public static PathGeometry GetPathGeometry(PointCollection polygonCorners)
{
    List<PathSegment> pathSegments = new List<PathSegment> { new PolyLineSegment(polygonCorners, true) };
    PathGeometry pathGeometry = new PathGeometry();
    pathGeometry.Figures.Add(new PathFigure(polygonCorners[0], pathSegments, true));
    return pathGeometry;
}

新しい方法 (4.6 倍高速。 はい、本当に 4.6 倍高速):

public static bool PointCollectionsOverlap_Fast(PointCollection area1, PointCollection area2)
{
    for (int i = 0; i < area1.Count; i++)
    {
        for (int j = 0; j < area2.Count; j++)
        {
            if (lineSegmentsIntersect(area1[i], area1[(i + 1) % area1.Count], area2[j], area2[(j + 1) % area2.Count]))
            {
                return true;
            }
        }
    }

    if (PointCollectionContainsPoint(area1, area2[0]) ||
        PointCollectionContainsPoint(area2, area1[0]))
    {
        return true;
    }

    return false;
}

public static bool PointCollectionContainsPoint(PointCollection area, Point point)
{
    Point start = new Point(-100, -100);
    int intersections = 0;

    for (int i = 0; i < area.Count; i++)
    {
        if (lineSegmentsIntersect(area[i], area[(i + 1) % area.Count], start, point))
        {
            intersections++;
        }
    }

    return (intersections % 2) == 1;
}

private static double determinant(Vector vector1, Vector vector2)
{
    return vector1.X * vector2.Y - vector1.Y * vector2.X;
}

private static bool lineSegmentsIntersect(Point _segment1_Start, Point _segment1_End, Point _segment2_Start, Point _segment2_End)
{
    double det = determinant(_segment1_End - _segment1_Start, _segment2_Start - _segment2_End);
    double t = determinant(_segment2_Start - _segment1_Start, _segment2_Start - _segment2_End) / det;
    double u = determinant(_segment1_End - _segment1_Start, _segment2_Start - _segment1_Start) / det;
    return (t >= 0) && (u >= 0) && (t <= 1) && (u <= 1);
}
于 2012-06-28T19:06:16.887 に答える