Algorithme pour trouver la distance minimale entre les pixels et les groupes de pixels

Question

J'ai besoin d'un algorithme (de préférence en C++ bien que le pseudo code soit correct) pour trouver un groupe parmi les groupes de pixels qui ont une distance minimale d'un pixel particulier.

La distance est définie comme la somme des distances de chaque pixel du groupe au pixel particulier alors que chaque distance est égale à | x | + | y ​​| coordonnées.

Si ce ne est pas assez clair, je vais essayer de vous préciser

Merci

Answer 1

Mise à jour

La première version de cette solution calculée géométrique (euclidienne) distances lorsque le questian appelé Manhattan distances

Cela rend plus simple à optimiser.

1. Pour chaque groupe de pixels choisissent un pixel comme pixel primaire. Peu importe lequel.

2. Pour chaque autre pixel du groupe, calculez son décalage (x et y) à partir du pixel primaire. Contrairement à une distance de Manhattan, gardez le signe de ce décalage.

3. Somme tous les offsets (décalages x et y) dans un seul nombre, appelez cette total_offsets.

4. Lorsque vous avez besoin de la distance d'un pixel spécifié, calculez la distance (Manhattan) pour le pixel primaire. Multipliez ceci par le nombre de pixels et ajoutez les total_offsets pour obtenir la distance totale de Manhattan.

Les étapes 1 à 3 doivent seulement être effectuées une fois pour chaque groupe, puis l'étape 4 peut être effectuée selon les besoins.

par exemple.

Area A consists of 4 pixels: (8, 8), (8, 9), (9, 8) and (9, 9). 

    Declare (8, 9) as primary pixel. Offsets are 
     (8, 9) --> (8, 8) = (0, -1) 
     (8, 9) --> (9, 8) = (1, -1) 
     (8, 9) --> (9, 9) = (1, 0) 
    total_offset = 0 + -1 + 1 + -1 + 1 + 0 
       = 0 
    num_pixels = 4 

To compute Manhattan distance from pixel (2, 4) 

    distance to primary pixel 
    (2, 4) --> (8, 9) = (6, 5) 
        = 11 
    dist * num_pixels + total_offsets = 11 * 4 + 0 
            = 44 

Pour vérifier cela, nous pouvons le calculer le long chemin:

 (2, 4) --> (8, 8) = (6, 4) 
     (2, 4) --> (8, 9) = (6, 5) 
     (2, 4) --> (9, 8) = (7, 4) 
     (2, 4) --> (9, 9) = (7, 5) 

    distance = 6 + 4 + 6 + 5 + 7 + 4 + 7 + 5 
      = 44 

Answer 2

On dirait que vous savez déjà comment calculer la distance.

Une boucle for-too est-elle trop lente pour vous? Est-ce que votre boucle serait N^2?

Si oui, vous pouvez utiliser un BSP ou un Quadtree. Le seul problème que je vois est que vous essayez de faire un test de proximité, où ceux-ci sont principalement conçus pour les tests de collision. Cela pourrait vous permettre d'éliminer plus rapidement des groupes de groupes. Quelque chose qui fonctionnerait certainement (bien que son efficacité dans la réduction de votre nombre de calculs dépend fortement de la distribution de vos groupes) est simplement de diviser le monde en une grille régulièrement espacée et peu peuplée. Si un groupe tombe dans plusieurs sections de votre grille, ajoutez-le aux deux entrées de la grille. Lorsque vous exécutez votre comparaison, vous sélectionnez l'entrée de grille la plus proche et exécutez uniquement votre algorithme point à groupe sur les groupes de cette entrée de grille.

Answer 3

Ce qui suit est un exemple simplifié. Vous aurez besoin d'une fonction "distance int (Point p1, Point p2)" pour calculer la distance (en utilisant n'importe quel algorithme).

Point pxTest = ... // the single pixel to use for distance checking 
List<Point> pxGroup = ... // the group of pixels to check 

Point pxMin = null; // the pixel with the minimum distance 
int iMin = int.MAX; // the minimum distance so far 

foreach(Point pxOther in pxGroup) 
    if(iMin > distance(pxTest, pxOther)) 
    { 
     iMin = distance(pxTest, pxOther); // this could be cached in the line before as well to save this call 
     pxMin = pxOther; 
    } 

// now pxMin will include the closest point, iMin the distance