алгоритм определения точки пересечения окружности, в которой отрезок пересекается изнутри наружу окружности - PullRequest
Новая
       29

алгоритм определения точки пересечения окружности, в которой отрезок пересекается изнутри наружу окружности

1 голос
/ 30 апреля 2019

У меня есть отрезок между точками A и B. A находится внутри круга с центром в 0,0 с радиусом R. Я в тупике, пытаясь придумать эффективный способ вычисления пересечения отрезка линии AB с этим кругом.

Ответы [ 2 ]

0 голосов
/ 04 мая 2019

Тогда вам просто нужно определить, какой из двух полученных ответов дает точку между A и B.

Давайте назовем два результата I1 и I2.Чтобы определить, какой из них является ответом, необходимо проверить направления векторов A->I1 и A->I2 против A->B, где A - точка, расположенная внутри круга: 

% line: y = mx + b
m = (yB - yA) / (xB - xA);
b = yA - m * xA;

% circle: x^2 + y^2 = r^2
% intersection: x^2 + (mx + b)^2 = r^2
% ...           x^2 + m^2x^2 + b^2 + 2mbx - r^2 = 0
% ...           (1 + m^2)x^2 + 2mbx + (b^2 - r^2) = 0

A = 1 + m^2;
B = 2 * m * b;
C = b^2 - r^2;
sqrtD = sqrt(B^2 - 4*A*C);

xI = (-B+sqrtD) / (2*A);
yI = m * xI + b;

if (abs(atan2(yB - yA, xB - xA)-atan2(yI - yA, xI - xA)) > 1e-5)
    xI = (-B-sqrtD) / (2*A);
    yI = m * xI + b;
end

Замечание # 1: Я не проверял дельту на предмет ее отрицательности, поскольку вы сказали, что одна точка находится внутри круга, а другая - вне его.

Замечание # 2: Вам необходимо покрыть особый случай, где A == B.

Замечание № 3: Вам необходимо покрыть особый случай, когда xA == xB.

Замечание # 4: Вы можете выбрать правильный ответ с гораздо меньшими затратами, чем найти наклон двух векторов, рассчитать абсолютную дисперсию между ними и сравнить результат с эпсилоном!:)

0 голосов
/ 02 мая 2019

Это разрешение уравнения второй степени

Линия - это y = A.x + B, где A и B - постоянные Круг равен y ^ 2 = R ^ 2 - x ^ 2, где R - радиус, а центр круга - 0,0

т. Е. (A.x + B) ^ 2 = R ^ 2-x ^ 2 => A ^ 2.x ^ 2 + 2.A.x.B + B ^ 2 = R ^ 2 -x ^ 2 => (A ^ 2 + 1) .x ^ 2 + 2.A.B.x + B ^ 2-R ^ 2 = 0

Алгоритм:

пусть P = A ^ 2 + 1, G = 2.A.B, H = B ^ 2-R ^ 2 Уравнение: P.x ^ 2 + G.x + H = 0

, что дает 3 случая в зависимости от дельты дельта = G ^ 2-4 * Р * Н

Если дельта <0 => нет пересечений если дельта = 0 => пересекаются в 1 точке: x = -G / 2 * P и y = Ax + B если дельта> 0 => пересекаются в 2 точках: x1 = (- G-sqrt (delta)) / (2 * P), y1 = Ax1 + B и x2 = (- G + sqrt (delta)) / (2 * P), y2 = Ax2 + B (где sqrt - квадратный корень)

...