calcul de la distance entre un point et une boîte rectangulaire (le point le plus proche)

Ici est une formule unique qui permet d'éviter tous les cas de la logique. (J'arrive de travailler en JS, donc voici un JS de mise en œuvre). Laissez rect = {max:{x:_, y:_}, min:{x:_, y:_}} et p={x:_, y:_}

function distance(rect, p) {
  var dx = Math.max(rect.min.x - p.x, 0, p.x - rect.max.x);
  var dy = Math.max(rect.min.y - p.y, 0, p.y - rect.max.y);
  return Math.sqrt(dx*dx + dy*dy);
}

Explication:
Cette décompose le problème dans le calcul de la distance x dx et y la distance dy. Il utilise ensuite la formule de la distance.

Pour le calcul de dx, voici comment cela fonctionne. (dy est analogue)

Regarder le tuple fourni à la fonction max: (min-p, 0, p-max). Nous allons désigner ce n-uplet (a,b,c).

Si p est à gauche de min, puis nous avons du p < mn < max, ce qui signifie que le tuple permettra d'évaluer à (+,0,-), et donc la fonction max renvoie correctement a = min - p.

Si p est compris entre min et max, puis nous avons min < p < max, ce qui signifie que le tuple permettra d'évaluer à (-,0,-). Encore une fois, la fonction max renvoie correctement b = 0.

Enfin, si p est à la droite de max, puis nous avons, min < max < p et le n-uplet évalue à (-,0,+). Une fois de plus, les Maths.max retourne correctement c = p - max.

Ainsi, il s'avère tous les cas, la logique est pris en charge par les Mathématiques.max, ce qui conduit à une belle 3-ligne, de flux de contrôle-fonction libre.

Disons que le point est nommé P et ABCD est notre rectangle. Ensuite, le problème peut être décomposé en un ensemble de sous-problèmes:

(1) Développer une fonction dist(P, AB) qui calcule la distance entre un point P et arbitraire segment AB.

(2) Calculer les quatre distances entre votre point de P et de chaque côté du rectangle (de chaque côté est un segment) et de prendre le plus court des quatre

  distance = min(dist(P, AB), dist(P,BC), dist(P, CD), dist(P, DA))

C'est votre réponse.

Maintenant, nous avons besoin de savoir comment calculer la distance entre le point P et l'arbitraire d'un segment AB, c'est à dire comment calculer dist(P, AB). Cela se fait comme suit

(1) Effectuer une projection du point P à la ligne AB. Vous obtenez le nouveau point P' sur AB.

(2) Si P' se situe entre A et B, puis dist(P, AB) est la distance entre P et P'.

(3) Sinon, dist(P, AB) est la distance entre P et soit A ou B, selon la période la plus courte.

Que c'est. Il y a bien des façons d'optimiser la procédure, mais même si sa mise en œuvre littéralement, il fonctionne très bien déjà.

P. S. bien sûr, on peut se demander comment effectuer une projection d'un point à la ligne. Je le laisse en exercice au lecteur 🙂

Légèrement optimisé C# alternative (bien qu'il devrait probablement avoir une certaine tolérance lorsque l'on compare les doubles contre 0). Je recommande également la création d'une sorte de Rect ou Point des méthodes d'extension pour ces.

public static class GeometryUtils
{
    public static double Distance(Point point, Rect rect)
    {
        var xDist = MinXDistance(point, rect);
        var yDist = MinYDistance(point, rect);
        if (xDist == 0)
        {
            return yDist;
        }
        else if (yDist == 0)
        {
            return xDist;
        }

        return Math.Sqrt(Math.Pow(xDist, 2) + Math.Pow(yDist, 2));
    }

    private static double MinXDistance(Point point, Rect rect)
    {
        if (rect.Left > point.X)
        {
            return rect.Left - point.X;
        }
        else if (rect.Right < point.X)
        {
            return point.X - rect.Right;
        }
        else
        {
            return 0;
        }
    }

    private static double MinYDistance(Point point, Rect rect)
    {
        if (rect.Bottom < point.Y)
        {
            return point.Y - rect.Bottom;
        }
        else if (rect.Top > point.Y)
        {
            return rect.Top - point.Y;
        }
        else
        {
            return 0;
        }
    }
}

J'ai été la recherche de ce et je pense avoir une solution, pour le cas où la case est axis-aligned (un cas habituel)

Je crois que dans ce cas, vous pouvez calculer la distance comme ceci:

function distance_aux(p, lower, upper)
  if p < lower then return lower - p end
  if p > upper then return p - upper end
  return min(p - lower, upper - p)
end

function distance(point, box)
  local dx = distance_aux(point.x, box.left, box.right)
  local dy = distance_aux(point.y, box.top, box.bottom)
  return sqrt(dx * dx + dy * dy)
end

Cela peut être étendu à z, bien sûr.

Est-ce une boîte 3D ou 2D rectangle? de toute façon, vous êtes probablement mieux de se la point de ligne de (pour la 2D) ou point-plan (3D) de la distance de chaque côté, puis en sélectionnant au minimum.

Edit: il y a une bien meilleure façon décrite ici (dernier post). Il s'agit de transformer vos coordonnées d'un point dans l'espace, puis "saturer" les coordonnées avec la taille de la boîte pour trouver le point sur la boîte la plus proche du point. Je n'ai pas essayé, mais il regarde à droite pour moi.