Find top 3 closest targets in Actionscript 3

Question

I have an array of characters that are Points and I want to take any character and be able to loop through that array and find the top 3 closest (using Point.distance) neighbors. Could anyone give me an idea of how to do this?

Answer 1

This is a new and improved version of the code I posted last night. It's composed of two classes, the PointTester and the TestCase. This time around I was able to test it too!

We start with the 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");
      }
     }

    }

}

And this would be 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

It might be worth mentioning that, if the number of points is large enough for performance to be important, then the goal could be achieved more quickly by keeping two lists of points, one sorted by X and the other by Y. One could then find the closest 3 points in O(logn) time rather than O(n) time by looping through every point.

Answer 3

If you use grapefrukt's solution you can change the getDistance method to return x*x + y*y; instead of return Math.sqrt( x * x + y * y );