Calcul de la translation minimale pour séparer deux lignes

Question

Étant donné que deux segments de droite se croisent (AB et CD) dans R2, on trouve la translation ayant la plus petite amplitude à appliquer à CD de sorte qu'elle n'intersecte plus AB.

Ce que j'ai essayé. Je calcule la distance entre chaque point de chaque ligne et la ligne opposée. Ensuite, je choisis la plus petite des 4 valeurs et je l'applique à la perpendiculaire de la ligne. Cependant, la traduction que je calcule est souvent dans la mauvaise direction. Comment puis-je réparer ça?

#include <iostream> 
#include <cmath> 
#include <algorithm> 
#include <vector> 
#include <iterator> 

class Vector2 
{ 
public: 
    double x; 
    double y; 

    Vector2() : x(x), y(y) {} 
    Vector2(double x, double y) : x(x), y(y) {} 

    Vector2 operator*(double val) { return Vector2(x*val, y*val);} 
    Vector2 operator/(double val) { return Vector2(x/val, y/val);} 
    Vector2 operator+(Vector2 &v) { return Vector2(x+v.x, y+v.y);} 
    Vector2 operator-(Vector2 &v) { return Vector2(x-v.x, y-v.y);} 

    Vector2 Perpendicular() { return Vector2(y, -x); } 
    double Dot(Vector2 &v) {return (x * v.x) + (y * v.y); } 
    double Magnitude() { return std::sqrt(Dot(*this)); } 
    Vector2 Normal() { return *this/Magnitude(); } 
    double GetDistance(Vector2 &v) { Vector2 d = *this - v; return d.Magnitude(); } 
}; 


class Line 
{ 
public: 
    Line() : a(Vector2()), b(Vector2()) {} 
    Line(Vector2 a, Vector2 b) : a(a), b(b) {}; 
    double DistanceFromPoint(Vector2 &p) ; 
    Vector2 GetTranslation(Line &l) ; 
    Vector2& GetPoint(unsigned i) {if (i==0) return a; else return b;} 
    double GetLength() { return GetPoint(0).GetDistance(GetPoint(1)); } 

    Vector2 a; 
    Vector2 b; 
}; 

double Line::DistanceFromPoint(Vector2 &p) 
{ 
    double l2 = GetLength() * GetLength(); 
    Vector2 pv = p - GetPoint(0); 
    Vector2 wv = GetPoint(1) - GetPoint(0); 
    double t = std::max(0.d, std::min(1.d, pv.Dot(wv)/l2)); 
    Vector2 projection = (wv * t) + GetPoint(0); 

    return p.GetDistance(projection); 
} 

Vector2 Line::GetTranslation(Line &l) 
{ 
    // Calculate Distances from each point to rthe opposite line 
    std::vector<double> dist(4); 
    dist[0] = DistanceFromPoint(l.GetPoint(0)); 
    dist[1] = DistanceFromPoint(l.GetPoint(1)); 
    dist[2] = l.DistanceFromPoint(GetPoint(0)); 
    dist[3] = l.DistanceFromPoint(GetPoint(1)); 

    //Get the smallest distance 
    auto it = std::min_element(std::begin(dist), std::end(dist)); 
    double min = *it; 
    unsigned pos = std::distance(std::begin(dist), it); 

    // Get the normalized perpendicular of line 
    Vector2 axis; 
    if (pos == 2 || pos == 3) 
     axis = (GetPoint(1) - GetPoint(0)).Perpendicular().Normal(); 
    else 
     axis = (l.GetPoint(1) - l.GetPoint(0)).Perpendicular().Normal(); 

    std::cout << "min: " << min << std::endl; 
    std::cout << "axis: (" << axis.x << "," << axis.y << ")" << std::endl; 

    //Apply that min to the perpendicular 
    return axis * min; 
} 

int main() 
{ 
    Line A; 
    Line B; 

    Vector2 t; 

    std::cout << "Left" << std::endl; 
    A = Line(Vector2(0, 4), Vector2(8, 4)); 
    B = Line(Vector2(2, 0), Vector2(2, 6)); 
    t = A.GetTranslation(B); 
    std::cout << "Expected: (-2, 0)" << std::endl; 
    std::cout << "Got: (" << t.x << "," << t.y << ")" << std::endl << std::endl; 

    std::cout << "Right" << std::endl; 
    B = Line(Vector2(6, 0), Vector2(6, 6)); 
    t = A.GetTranslation(B); 
    std::cout << "Expected: (2, 0)" << std::endl; 
    std::cout << "translation: (" << t.x << "," << t.y << ")" << std::endl << std::endl; 

    std::cout << "Top" << std::endl; 
    B = Line(Vector2(4, 0), Vector2(4, 6)); 
    t = A.GetTranslation(B); 
    std::cout << "Expected: (0, -2)" << std::endl; 
    std::cout << "translation: (" << t.x << "," << t.y << ")" << std::endl << std::endl; 

    std::cout << "Bottom" << std::endl; 
    B = Line(Vector2(4, 6), Vector2(4, 8)); 
    t = A.GetTranslation(B); 
    std::cout << "Expected: (0, -2)" << std::endl; 
    std::cout << "translation: (" << t.x << "," << t.y << ")" << std::endl; 
} 

Answer 1

Votre idée va fonctionner. Vous avez seulement besoin d'avoir une fonction de distance signée comme @Tommy. En outre, notez que vous devrez également obtenir la direction perpendiculaire , en fonction de vos conventions de signe dans la fonction de distance.

Here is a demo

Answer 2

Vous avez la bonne approche. En raisonnant sur la somme de Minkowski, le vecteur de séparation le plus court sera perpendiculaire à l'une des lignes et sera juste assez long pour pousser l'un des points d'extrémité à la surface de l'autre ligne.

Cependant, votre DistanceFromPoint renvoie une distance non signée: elle est toujours zéro ou positive. Vous utilisez ensuite une seule perpendiculaire par ligne pour multiplier cela par. Donc, vous devriez finir dans le mauvais sens 50% du temps parce que votre distance n'a aucun signe.

Vous préférez peut-être réorganiser, notamment parce qu'il va sauver une partie de vos racines carrées:

1. obtenir les deux axes;
2. Pour chaque ligne, projetez le vecteur de n'importe quel point de la ligne à chaque extrémité de l'autre ligne sur l'axe de cette ligne. Cela produit un résultat signé;
3. choisir le plus court de ces résultats par grandeur;
4. calculer l'axe de séparation comme le négatif du nombre le plus petit multiplié par l'axe sur lequel il a été calculé.

... parce que si vous êtes par embedded n unités le long de l'axe q alors la façon de résoudre c'est-à déplacer -n unités le long q; alors choisissez le moins n.