2D столкновение между движущейся окружностью и фиксированным отрезком

Question

В контексте игровой программы у меня есть движущийся круг и фиксированный отрезок. Сегмент может иметь произвольный размер и ориентацию.

• Я знаю радиус круга: r
• Я знаю координаты круга перед ходом: (xC1, yC1)
• Я знаю координаты круга после перемещения: (xC2, yC2)
• Я знаю координаты конечностей отрезка: (xL1, yL1) - (xL2, yL2)

У меня возникают трудности при попытке вычислить:

• A логическое значение : если какая-либо часть круга попадает на отрезок при перемещении от (xC1, yC1) к (xC2, yC2)
• Если логическое значение истинно, координаты (x, y) центра круга, когда он достигает отрезка (я имею в виду, когда окружность касается сегмента в первый раз)

Answer 1

Я собираюсь ответить с помощью псевдоалгоритма - без какого-либо кода. На мой взгляд, есть два случая, в которых мы можем вернуть true , как показано на рисунке ниже:

Здесь синим цветом обозначены ваши круги, пунктирная линия - это линия траектории, а красная линия - ваша заданная линия.

• Мы строим вспомогательную линию траектории от и до центра обеих окружностей. Если эта линия траектории пересекает данную линию - возвращает true . См. этот вопрос о том, как вычислить это пересечение.
• Во втором случае первое испытание провалило нас, но могло случиться так, что круги все равно подтолкнули линию, проходя по траектории. Нам понадобится следующая конструкция:

Из траектории мы строим нормальные линии к каждой точке A и B. Затем эти линии нарезаются или расширяются на вспомогательные линии (Ha и Hb), так что их длина от A и B равна точно радиус круга. Затем мы проверяем, пересекается ли каждая из этих вспомогательных линий с линией траектории. Если они вернут истину.

• В противном случае вернуть false .

Answer 2

Смотрите здесь:

Сегмент линии / пересечение окружности

Если значение, которое вы получите под квадратным корнем из вычисления x или y, является отрицательным, то сегмент не пересекается. Кроме того, вы можете остановить вычисления после того, как у вас есть x и y (примечание: вы можете получить два ответа)

Обновление Я пересмотрел свой ответ, чтобы очень конкретно решить вашу проблему. Я отдаю должное Doswa за это решение, так как я довольно много последовал и написал его для C #. Основная стратегия заключается в том, что мы собираемся расположить ближайшую точку вашего отрезка к центру круга. Исходя из этого, мы посмотрим на расстояние этой ближайшей точки, и, если оно находится в радиусе, найдите точку вдоль направления к ближайшей точке, которая лежит прямо на радиусе круга.

// I'll bet you already have one of these.
public class Vec : Tuple<double, double>
{
  public Vec(double item1, double item2) : base(item1, item2) { }
  public double Dot(Vec other) 
    { return Item1*other.Item1 + Item2*other.Item2; }
  public static Vec operator-(Vec first, Vec second) 
    { return new Vec(first.Item1 - second.Item1, first.Item2 - second.Item2);}
  public static Vec operator+(Vec first, Vec second) 
    { return new Vec(first.Item1 + second.Item1, first.Item2 + second.Item2);}
  public static Vec operator*(double first, Vec second) 
    { return new Vec(first * second.Item1, first * second.Item2);}
  public double Length() { return Math.Sqrt(Dot(this)); }
  public Vec Normalize() { return (1 / Length()) * this; }
}

public bool IntersectCircle(Vec origin, Vec lineStart, 
      Vec lineEnd, Vec circle, double radius, out Vec circleWhenHit)
{
    circleWhenHit = null;

    // find the closest point on the line segment to the center of the circle
    var line = lineEnd - lineStart;
    var lineLength = line.Length();
    var lineNorm = (1/lineLength)*line;
    var segmentToCircle = circle - lineStart;
    var closestPointOnSegment = segmentToCircle.Dot(line) / lineLength;

    // Special cases where the closest point happens to be the end points
    Vec closest;
    if (closestPointOnSegment < 0) closest = lineStart;
    else if (closestPointOnSegment > lineLength) closest = lineEnd;
    else closest = lineStart + closestPointOnSegment*lineNorm;

    // Find that distance.  If it is less than the radius, then we 
    // are within the circle
    var distanceFromClosest = circle - closest;
    var distanceFromClosestLength = distanceFromClosest.Length();
    if (distanceFromClosestLength > radius) return false;

    // So find the distance that places the intersection point right at 
    // the radius.  This is the center of the circle at the time of collision
    // and is different than the result from Doswa
    var offset = (radius - distanceFromClosestLength) *
                 ((1/distanceFromClosestLength)*distanceFromClosest);
    circleWhenHit = circle - offset;

    return true;
}

Answer 3

Вот некоторая Java, которая вычисляет расстояние от точки до линии (это не завершено, но даст вам основную картину).Код взят из класса «Vector».Предполагается, что векторный объект инициализируется вектором линии.Метод 'distance' принимает точку, с которой начинается линейный вектор (конечно, называемый 'at'), и точку интереса.Он рассчитывает и возвращает расстояние от этой точки до линии.

public class Vector
{
double x_ = 0;
double y_ = 0;
double magnitude_ = 1;

public Vector()
{
}

public Vector(double x,double y)
{
    x_ = x;
    y_ = y;
}

public Vector(Vector other)
{
    x_ = other.x_;
    y_ = other.y_;
}

public void add(Vector other)
{
    x_ += other.x_;
    y_ += other.y_;
}

public void scale(double val)
{
    x_ *= val;
    y_ *= val;
}

public double dot(Vector other)
{
    return x_*other.x_+y_*other.y_;
}

public void cross(Vector other)
{
    x_ = x_*other.y_ - y_*other.x_;
}

public void unit()
{
    magnitude_ = Math.sqrt(x_*x_+y_*y_);
    x_/=magnitude_;
    y_/=magnitude_;
}

public double distance(Vector at,Vector point)
{
    //
    // Create a perpendicular vector
    //
    Vector perp = new Vector();
    perp.perpendicular(this);
    perp.unit();

    Vector offset = new Vector(point.x_ - at.x_,point.y_ - at.y_);
    double d = Math.abs(offset.dot(perp));

    double m = magnitude();
    double t = dot(offset)/(m*m);
    if(t < 0)
    {
        offset.x_ -= at.x_;
        offset.y_ -= at.y_;
        d = offset.magnitude();
    }
    if(t > 1)
    {
        offset.x_ -= at.x_+x_;
        offset.y_ -= at.y_+y_;
        d = offset.magnitude();
    }
    return d;
}

private void perpendicular(Vector other)
{
    x_ = -other.y_;
    y_ = other.x_;
}

public double magnitude()
{
    magnitude_ = Math.sqrt(x_*x_+y_*y_);
    return magnitude_;
}
}