Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: -1
Последний выпуск: 19.06.2015

Пересечение отрезка и окружности

54K
27 января 2010 года
dariys
4 / / 27.01.2010
Помогите с алгоритмом. Есть отрезок, координаты концов которого извесни и окружность с извесными координатами центра и радиусом. как определить пренадлежит ли хоть одна точка отрезка данной окружности?
416
27 января 2010 года
MaitreDesir
380 / / 02.01.2008
Самый очевидный способ. Открываем учебник по линейной алгебре и аналитической геометрии, смотрим там уравнения.
Записываем уравнение в общем виде для окружности и отрезка (уравнение прямой и два двойных неравенства, ограничивающих прямую до отрезка). Решаем систему из этих двух уравнений и четырех неравенств относительно (х,у). Если решение существует - пересечение или касание есть. В программе надо подставить коэффициенты (рассчитать их по исходным данным возможно) и попытаться найти корни.
К слову, если корень единствнный, то отрезок касается окружности, если корня два - является хордой.
341
27 января 2010 года
Der Meister
874 / / 21.12.2007
Цитата: dariys
Помогите с алгоритмом. Есть отрезок, координаты концов которого извесни и окружность с извесными координатами центра и радиусом. как определить пренадлежит ли хоть одна точка отрезка данной окружности?

Вот код на C# 3, умеющий пересекать явно заданные линии и окружности и даже определять принадлежность точки таким линиям. Это ~97% решения.

Код:
static class Doubles
{
    public static double Square(this double x)
    {
        return x * x;
    }

    public static double Sqrt(this double x)
    {
        return Math.Sqrt(x);
    }

    public static bool SafeEquals(this double left, double rigth)
    {
        const double epsilon = 1e-7;
        return Math.Abs(left - rigth) <= epsilon;
    }
}

struct Vector
{
    public Vector(double x, double y)
        : this()
    {
        X = x;
        Y = y;
    }

    public double Length
    {
        get { return (X.Square() + Y.Square()).Sqrt(); }
    }

    public double X { get; private set; }
    public double Y { get; private set; }

    public static Vector operator+(Vector left, Vector right)
    {
        return new Vector(left.X + right.X, left.Y + right.Y);
    }

    public static Vector operator-(Vector minuend, Vector substrahend)
    {
        return new Vector(minuend.X - substrahend.X, minuend.Y - substrahend.Y);
    }

    public static double operator*(Vector left, Vector right)
    {
        return left.X*right.X + left.Y*right.Y;
    }

    public static Vector operator *(double ratio, Vector v)
    {
        return new Vector(v.X*ratio, v.Y*ratio);
    }

    public static Vector operator * (Vector v, double ratio)
    {
        return ratio * v;
    }

    public Vector Normalize()
    {
        double length = Length;
        if (length.SafeEquals(0.0))
            throw new InvalidOperationException("Attempt to normalize zero-length vector");

        return new Vector(X / length, Y / length);
    }
}

struct Pair<T>
{
    public Pair(T first, T second)
        : this()
    {
        First = first;
        Second = second;
    }

    public T First { get; private set; }
    public T Second { get; private set; }
}

class Circle
{
    public Circle(Vector center, double radius)
    {
        Center = center;
        Radius = radius;
    }

    public Vector Center { get; private set; }
    public double Radius { get; private set; }
}

struct Line
{
    public Line(Vector pivot, Vector direction)
        : this()
    {
        U = pivot;
        V = direction;
    }

    public static Line FromPoints(Vector p1, Vector p2)
    {
        return new Line(p1, p2 - p1);
    }

    public Vector U { get; private set; }
    public Vector V { get; private set; }

    public Pair<Vector>? Intersect(Circle circle)
    {
        Vector g = U - circle.Center;
       
        double a = V * V;
        double b = 2 * (V * g);
        double c = g*g - circle.Radius.Square();
        double d = b.Square() - 4*a*c;

        if (d < 0)
            return null;

        double sqrt_from_d = d.Sqrt();
        double double_a = 2*a;

        double first = (-b - sqrt_from_d)/double_a;
        double second = (-b + sqrt_from_d)/double_a;

        return new Pair<Vector>(PointFromRatio(first), PointFromRatio(second));
    }

    public Line Normalize()
    {
        return new Line(U, V.Normalize());
    }

    public Vector PointFromRatio(double ratio)
    {
        return U + V*ratio;
    }

    public bool Contains(Vector p)
    {
        if (V.X.SafeEquals(0d))
            return p.X.SafeEquals(U.X);

        if (V.Y.SafeEquals(0d))
            return p.Y.SafeEquals(U.Y);
       
        return ((p.X - U.X) / V.X).SafeEquals((p.Y - U.Y) / V.Y);
    }
}
Линию можно задавать и по-другому (неявно). Почитать об этом можно (на аглицком), набрав в гугол запрос:
Glassner A. (ed.) Graphics gems, vol.1 (AP, 1995)(T)(666s).djvu
54K
27 января 2010 года
dariys
4 / / 27.01.2010
Впринципе эта задачя у меня сводится до того что б найти количество отрезков, в которых хотя бы одна точка лежит в кругу


Тоесть все отрезки кроме В подходят по условию.
1.9K
31 января 2010 года
GreenRiver
451 / / 20.07.2008
Цитата: dariys
Впринципе эта задачя у меня сводится до того что б найти количество отрезков, в которых хотя бы одна точка лежит в кругу


1. Находите расстояние от точки (центр окружности) до прямой заданной двумя точками (концы отрезков). Алгоритм например такой.
2. Если расстояние меньше, чем радиус окружности, значит с прямой пересекается.
3. Осталось проверить пересекается ли отрезок, лежащий на этой прямой - это можно сделать через проверку пересечения диапозонов по оси x, в которых лежит окружность и отрезок. Для окружности это [Cx - r, Cx + r], для отрезка [x1, x2].

341
31 января 2010 года
Der Meister
874 / / 21.12.2007
Цитата: GreenRiver
3. Осталось проверить пересекается ли отрезок, лежащий на этой прямой - это можно сделать через проверку пересечения диапозонов по оси x, в которых лежит окружность и отрезок. Для окружности это [Cx - r, Cx + r], для отрезка [x1, x2]

Прямая может проходить вертикально. Впрочем, ерунда: достаточно проверить на равенство нулю x-компоненты вектора направления прямой, и, в случае чего, проверить попадание ординат отрезка по аналогичной формуле.
Да, хорошее решение.

1.9K
31 января 2010 года
GreenRiver
451 / / 20.07.2008
Цитата: Der Meister
Прямая может проходить вертикально. Впрочем, ерунда: достаточно проверить на равенство нулю x-компоненты вектора направления прямой, и, в случае чего, проверить попадание ординат отрезка по аналогичной формуле.
Да, хорошее решение.


Эх, к сожалению, не очень хорошее... есть случае даже не с вертикальной прямой, когда это не сработает :(

Тогда однозначно решать систему уравнений, как предлагает MaitreDesir.
А для случая, когда отрезок внутри окружности и не пересекает ее - проверить расстояние от центра окружности до концов отрезка, которые должны быть меньше радиуса.

43K
02 февраля 2010 года
loki231
76 / / 27.09.2009
Нужно проверить, что хотя бы одно из расстояний от центра круга до концов отрезка или расстояние до прямой, которой принадлежит отрезок (только в том случае, если ближайшая точка прямой к центру круга принадлежит отрезку), меньше или равно радиусу круга.
341
03 февраля 2010 года
Der Meister
874 / / 21.12.2007
Цитата: loki231
Нужно проверить, что хотя бы одно из расстояний от центра круга до концов отрезка или расстояние до прямой, которой принадлежит отрезок (только в том случае, если ближайшая точка прямой к центру круга принадлежит отрезку), меньше или равно радиусу круга.


Концы отрезка могут лежать за пределами окружности.
Э-э-х, ладно:

Код:
...

struct Line
{
    ...
   
    public Pair<double>? Intersect(Circle circle)
    {
        Vector g = U - circle.Center;
       
        double a = V * V;
        double b = 2 * (V * g);
        double c = g*g - circle.Radius.Square();
        double d = b.Square() - 4*a*c;
   
        if (d < 0)
            return null;
   
        double sqrt_from_d = d.Sqrt();
        double double_a = 2*a;
   
        double first = (-b - sqrt_from_d)/double_a;
        double second = (-b + sqrt_from_d)/double_a;
   
        return new Pair<double>(first, second);
    }
}

struct Segment
{
    public readonly Vector Start;
    public readonly Vector End;
   
    public Segment(Vector start, Vector end)
    {
        Start = start;
        End = end;
    }
   
    public bool IntersectsWith(Circle circle)
    {
        Line line = Line.FromPoints(Start, End);
        Pair<double>? intersection = line.Intersect(circle);
       
        if (!intersection.HasValue)
            return false;
           
        Pair<double> value = intersection.Value;
        double first = value.First;
        double second = value.Second;
       
        // Не пересекает в двух случаях:
        // 1. first < 0 && second < 0;
        // 2. first > 1 && second > 1.
       
        // !((first < 0 && second < 0) || (first > 1 && secons > 1))
        return (first >= 0d || second >= 0d) && (first <= 1d || second <= 1d);
    }    
}
43K
03 февраля 2010 года
loki231
76 / / 27.09.2009
Вот и я о том же. В этом случае нужно проверять расстояние между центром и прямой, но только в случае, если ближайшая точка прямой в центру принадлежит отрезку.
56K
14 февраля 2010 года
elkiigolkiya
11 / / 11.02.2010
форумчане и гости форума.
Вопрос у меня такой - как построить В канве точку, которая двигалась бы по окружности? как построить точку я знаю . В общем вопрос сводится к круговому движению.
x-a2y-b2=R2 - формула окружности.
61K
23 мая 2010 года
bvvrnd
2 / / 23.05.2010
Попробуйте через параметрические уравнения окружности:
x = x0 + R*sin(t)
y = y0 + R*cos(t)
где t [0; 2*Pi]
, если я правильно вас понял.
61K
24 мая 2010 года
alex_vinogradar
2 / / 19.05.2010
Пересечение отрезка с вертикальным отрезком.

Проблема в том, что K если принимать линию, на которой лежит отрезок как описанную уравнением y= kx b тут не рассчитаешь получается, на ноль делить надо. Вопрос: как быть? Может, кто-то сталкивался с такой проблемой?
61K
26 мая 2010 года
bvvrnd
2 / / 23.05.2010
Не утверждаю, что это лучшее решение, я делал так: проверял значение на равенство нулю, и если равно, то присваивал конечно малое значение, например 0.00001. После чего все нормально считалось. Потом округлял, в конце вычислений.
339
26 мая 2010 года
verybadbug
619 / / 12.09.2005
Цитата: alex_vinogradar
Пересечение отрезка с вертикальным отрезком.

Проблема в том, что K если принимать линию, на которой лежит отрезок как описанную уравнением y= kx b тут не рассчитаешь получается, на ноль делить надо. Вопрос: как быть? Может, кто-то сталкивался с такой проблемой?



разверните систему на 90 градусов - считайте относительно y

x=y/k-b/k

1.9K
26 мая 2010 года
Rad87
123 / / 14.12.2005
когда мне нужно было пересекать различные фигуры, я применял функции из этой библиотеки

http://www.geometrictools.com

PS но там есть заморочки со сборкой.
339
27 мая 2010 года
verybadbug
619 / / 12.09.2005
Цитата: GreenRiver
1. Находите расстояние от точки (центр окружности) до прямой заданной двумя точками (концы отрезков). Алгоритм например такой.
2. Если расстояние меньше, чем радиус окружности, значит с прямой пересекается.
3. Осталось проверить пересекается ли отрезок, лежащий на этой прямой - это можно сделать через проверку пересечения диапозонов по оси x, в которых лежит окружность и отрезок. Для окружности это [Cx - r, Cx + r], для отрезка [x1, x2].



+1

оптимизируем немного алгоритм...
1. определяем расстояние от концов отрезка до центра окружности (d1, d2)
2. если ((d1<=r) && (d2>=r)) || ((d1>=r) && (d2<=r)) - отрезок пересекает окружность в одном месте, конец
3. если (d1<r) && (d2<r) - отрезок находится внутри окружности, не пересекая ее, конец
4. находим наименьшее расстояние от центра окружности до отрезка (d3)
5. если (d3 <= r) - либо касается, либо пересекает, конец
6. лежит за пределами

87K
05 декабря 2012 года
gisser
1 / / 05.12.2012
Была задача найти единственное пересечение отрезка с окружностью, если таковое существует (третья функция ниже).
По теме - пригодится вторая. min2, max2 - то же, что min и max.
Магические коэффициенты образовались при решении системы уравнений: первое - уравнение окружности, второе - уравнение прямой по двум точкам.
Работает при любых отрезках.

Код:
bool EqualDoubles(double n1, double n2, double precision_)
{
  return (fabs(n1-n2) <= precision_);
}


// пересечение линии, проходящей через отрезок, с окружностью;
// возвращает число точек пересечения: 0 или 1 или 2;
// если 1, результат в xa, xb
int LineCircleIntersection(double x0, double y0, double r, // центр и рдиус окружности
                           double x1, double y1,           // точки
                           double x2, double y2,           //    отрезка
                           double& xa, double &ya,         // резуль-
                           double& xb, double &yb)         //      тат
{
  double q = x0*x0+y0*y0-r*r;
  double k = -2.0*x0;
  double l = -2.0*y0;

  double z = x1*y2-x2*y1;
  double p = y1-y2;
  double s = x1-x2;

  if (EqualDoubles(s, 0.0, 0.001))
  {
    s = 0.001;
  }

  double A = s*s+p*p;
  double B = s*s*k+2.0*z*p+s*l*p;
  double C = q*s*s+z*z+s*l*z;

  double D = B*B-4.0*A*C;

  if (D < 0.0)
  {
    return 0;
  }
  else if (D < 0.001)
  {
    xa = -B/(2.0*A);
    ya = (p*xa + z)/s;
    return 1;
  }
  else
  {
    xa = (-B + sqrt(D))/(2.0*A);
    ya = (p*xa + z)/s;

    xb = (-B - sqrt(D))/(2.0*A);
    yb = (p*xb + z)/s;
  }

  return 2;
}

//---------------------------------------------------------------------------

// единственное пересечение отрезка с окружностью
// результат - если единственное, то точка пересечения xa, ya
bool SegmentCircleIntersection(double x0, double y0, double r, // центр и рдиус окружности
                               double x1, double y1,           // точки
                               double x2, double y2,           //    отрезка
                               double& xa, double &ya)         // результат
{
  double d1 = hypot(x1-x0,y1-y0);
  double d2 = hypot(x2-x0,y2-y0);
  if (d1 > r && d2 > r)
  {
    return false;
  }
  if (d1 < r && d2 < r)
  {
    return false;
  }

  double xa_ = 0.0;
  double ya_ = 0.0;
  double xb_ = 0.0;
  double yb_ = 0.0;

  if (LineCircleIntersection(x0,y0,r,x1,y1,x2,y2,xa_,ya_,xb_,yb_) < 1)
  {
    return false;
  }

  double xmin = min2(x1,x2);
  double xmax = max2(x1,x2);
  double ymin = min2(y1,y2);
  double ymax = max2(y1,y2);

  if (xa_ >= xmin && xa_ <= xmax && ya_ >= ymin && ya_ <= ymax)
  {
    xa = xa_;
    ya = ya_;

    return true;
  }

  if (xb_ >= xmin && xb_ <= xmax && yb_ >= ymin && yb_ <= ymax)
  {
    xa = xb_;
    ya = yb_;

    return true;
  }

  return false;

}

Знаете кого-то, кто может ответить? Поделитесь с ним ссылкой.

Ваш ответ

Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог