actionscript-3 - Actionscript 3 で上位 3 つの最も近いターゲットを見つける

Question

ポイントである文字の配列があり、任意の文字を取得してその配列をループし、(Point.distance を使用して) 最も近い上位 3 つの近傍を見つけたいと考えています。誰でもこれを行う方法を教えてもらえますか?

Answer 1

これは、昨夜投稿したコードの新しく改良されたバージョンです。これは、PointTesterとTestCaseの2つのクラスで構成されています。今回は私もテストできました！

TestCase.asから始めます

package  {

    import flash.geom.Point;
    import flash.display.Sprite;

    public class TestCase extends Sprite {

        public function TestCase() {
            // some data to test with
            var pointList:Array = new Array();
            pointList.push(new Point(0, 0));
            pointList.push(new Point(0, 0));
            pointList.push(new Point(0, 0));
            pointList.push(new Point(1, 2));
            pointList.push(new Point(9, 9));

            // the point we want to test against
            var referencePoint:Point = new Point(10, 10);

            var resultPoints:Array = PointTester.findClosest(referencePoint, pointList, 3);

            trace("referencePoint is at", referencePoint.x, referencePoint.y);
            for each(var result:Object in resultPoints) {
                trace("Point is at:", result.point.x, ", ", result.point.y, " that's ", result.distance, " units away");
            }
        }

    }

}

そしてこれはPointTester.asになります

package  {

    import flash.geom.Point;

    public class PointTester {

        public static function findClosest(referencePoint:Point, pointList:Array, maxCount:uint = 3):Array{

            // this array will hold the results
            var resultList:Array = new Array();

            // loop over each point in the test data
            for each (var testPoint:Point in pointList) {

                // we store the distance between the two in a temporary variable
                var tempDistance:Number = getDistance(testPoint, referencePoint);

                // if the list is shorter than the maximum length we don't need to do any distance checking
                // if it's longer we compare the distance to the last point in the list, if it's closer we add it
                if (resultList.length <= maxCount || tempDistance < resultList[resultList.length - 1].distance) {

                    // we store the testing point and it's distance to the reference point in an object
                    var tmpObject:Object = { distance : tempDistance, point : testPoint };
                    // and push that onto the array
                    resultList.push(tmpObject);

                    // then we sort the array, this way we don't need to compare the distance to any other point than
                    // the last one in the list
                    resultList.sortOn("distance", Array.NUMERIC );

                    // and we make sure the list is kept at at the proper number of entries
                    while (resultList.length > maxCount) resultList.pop();
                }
            }

            return resultList;
        }

        public static function getDistance(point1:Point, point2:Point):Number {
            var x:Number = point1.x - point2.x;
            var y:Number = point1.y - point2.y;
            return Math.sqrt(x * x + y * y);
        }
    }
}

Answer 2

ポイントの数がパフォーマンスを重視するのに十分な大きさである場合、ポイントの 2 つのリストを維持することで、目標をより迅速に達成できることに言及する価値があるかもしれません。1 つは X でソートされ、もう 1 つは Y でソートされます。すべてのポイントをループすることにより、O(n) 時間ではなく O(logn) 時間で最も近い 3 ポイント。

Answer 3

グレープフルーツのソリューションを使用する場合は、getDistance メソッドをreturn x*x + y*y;代わりに変更できます。return Math.sqrt( x * x + y * y );