Trouver les 3 premières cibles les plus proches dans Actionscript 3

Question

J'ai un tableau de caractères qui sont des points et je veux prendre n'importe quel caractère et être capable de parcourir ce tableau et de trouver les 3 premiers voisins les plus proches (en utilisant Point.distance). Quelqu'un pourrait-il me donner une idée de la façon de faire cela?

Answer 1

Ceci est une nouvelle version améliorée du code que j'ai posté hier soir. Il est composé de deux classes, le PointTester et le TestCase. Cette fois, j'ai pu le tester aussi!

Nous commençons par les 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"); 
      } 
     } 

    } 

} 

Et ce serait 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

Il pourrait être utile de mentionner que, si le nombre de points est grand assez pour que la performance soit importante, alors l'objectif pourrait être atteint plus rapidement en gardant deux listes de points, l'une triée par X et l'autre par Y. On pourrait alors trouver les 3 points les plus proches dans O (log n) l'heure plutôt que l'heure O (n) en passant par tous les points.

Answer 3

Si vous utilisez la solution de GRAPEFRUKT vous pouvez changer la méthode de GetDistance à return x*x + y*y; au lieu de return Math.sqrt(x * x + y * y);