геометрия: пересечение окружности отрезком

← →
tButton © (2006-06-30 09:26) [0]

насколько я тут успел намыслить задачу можно свести к вычислению расстояния от точки до отрезка.
"кратчайшее расстояние от точки до прямой - перпендикуляр" (с) учебник геометрии

осталось только разобраться с мат частью.
координаты центра окружности есть. координаты начальной и конечной точки отрезка есть. сижу. рисую. думаю.

← →
Alx2 © (2006-06-30 09:35) [1]

>tButton © (30.06.06 09:26)

Если только факт пересечения, то довольно просто решается по условию
min(D1,D2,D3)<=R
D1 - расстояние от начала отрезка до центра окружности.
D2 - расстояние от конца отрезка до центра окружности.
D3 - расстояние от центра окружности до прямой.
Чтобы не считать радикалы, достаточно вместо расстояний брать их квадраты.

Если нужна именно точка пересечения,
то обозначим P0 - начало отрезка. P1 - конец отрезка.
P - точка на отрезке.
Тогда
P(t) = P0*(1-t)+t*P1 где t in [0..1]
Решаем уравнение
(P(t)-C)^2 = R^2 где C - центр окружности. Находим t.
При t in [0..1] имеет место пересечение в точке(ах) P(t)

← →
Putnik © (2006-06-30 09:37) [2]

Пожалуйста уточните, Вам нужны координаты или сам факт пересекает/не пересекает?

← →
Alx2 © (2006-06-30 09:39) [3]

К посту Alx2 © (30.06.06 09:35) [1]

В первой части некооректно написал.

вот это неверно:
----------------------
Если только факт пересечения, то довольно просто решается по условию
min(D1,D2,D3)<=R
D1 - расстояние от начала отрезка до центра окружности.
D2 - расстояние от конца отрезка до центра окружности.
D3 - расстояние от центра окружности до прямой.
Чтобы не считать радикалы, достаточно вместо расстояний брать их квадраты.
-----------------------

← →
tButton © (2006-06-30 10:09) [4]

вот что у меня нарисовалось
X-----A-----B | | | | | C

AB - отрезок
C - центр окружности
X - точка пересечения перпендикуляра опущеного из точки С на продолжение отрезка (на прямую)

теперь проверка факта пересечения сводится к двум шагам
1) принадлежит ли точка Х отрезку (проверка по расстояниям AX и BX)
2) если прошла первая проверка, то проверяем расстояние CX, если оно меньше либо равно радиусу окружности - имеет место пересечение/касание окружности отрезком

общая задача проверки факта пересечения сведена к вычислению координат точки Х

← →
ЮЮ © (2006-06-30 10:41) [5]

2) если прошла первая проверка,

а если нет? что из этого следует? Абсолютно ничего.

← →
Desdechado © (2006-06-30 10:44) [6]

А из аналитической геометрии не хочешь воспользоваться формулами?
Есть уравнение окружности, есть уравнение прямой. Решаешь систему. Если решение есть, пересечение есть.

← →
tButton © (2006-06-30 11:01) [7]

> 2) если прошла первая проверка,
>
> а если нет? что из этого следует? Абсолютно ничего.

а для этого как раз более примитивные проверки типа
CA < R
CB < R

> А из аналитической геометрии не хочешь воспользоваться формулами?
>
> Есть уравнение окружности, есть уравнение прямой. Решаешь
> систему. Если решение есть, пересечение есть.

хочу, нужно только подумать как это уложить в Дельфи
думаю.

← →
ЮЮ © (2006-06-30 11:07) [8]

> а для этого как раз более примитивные проверки типа
> CA < R
> CB < R

В приведенном тобой алгоритме их нет "теперь проверка факта пересечения сводится к двум шагам"
Иначе, после выбрасывания твоего 1) все сводится к Alx2 © (30.06.06 09:39) [3]

хочу, нужно только подумать как это уложить в Дельфи
вряд ли там будет намного проще вычисления расстояний. Да и факт пересечения прямой ещё не означает пересечечения отрезком

> Да и факт пересечения прямой ещё не означает пересечения отрезком
Верно. Но так же верно и то, что точку(и) пересечения с окружностью всегда можно проверить на принадлежность отрезку.

нашёл. всё предельно просто =)
X-----B-----A | | | C
CX = AC * sinA
AX = AC * cosA
AC находится применением теоремы пифагора к приращениям координат.
аналогично можно найти BX

осталось прийти домой и проверить на работоспособность =)

> tButton © (30.06.06 11:55) [10]
>
> нашёл. всё предельно просто =)
>

1. y=y0 + kx; // k=(y1-y0)/(x1-x0);
2. (x-x0r)^2 + (y-y0r)^2 = r^2;
=>

x^2 - (2*x0r)x + x0r^2 + (y0 - y0r + kx)^2 = r^2; =>

(1 + k^2)x^2 + (2k(y0 - y0r) - 2x0r)x + ( x0r^2 + (y0 - y0r)^2 - R^2) = 0;

Обычное квадратное уравнение. Решение мне лень писать.
Точка проверяется на вхождение в интервал отрезка, например, по X.

В твоем же способе есть проблемы:
Тебе еще SinA,CosA найти надо, да и сами стороны CX и AX - не есть ответ
в задаче. Отсюда вывод - он будет менленнее работать.
Если скорость очень важна, старайся забыть про Sin и Cos.

В контексте [1]
function CIntersect(P0, P1, C: TPoint; R: Integer): Boolean; // P0, P1 - координаты отрезка // C - центр окружности // R - радиус var V, MC, M: TPoint; LV, LMC, D, s: Double; // Пришлось сделать Double. Иначе переполняется :) begin R := R * R; V := point(P1.X - P0.X, P1.Y - P0.Y); // Вектор отрезка LV := sqr(V.X) + sqr(V.Y); // квадрат длины отрезка M := point(P1.X + P0.X, P1.Y + P0.Y); // Середина отрезка, увеличенная в два раза MC := point(M.X - 2 * C.X, M.Y - 2 * C.Y); // Вектор от центра окружности к середине отрезка LMC := sqr(Mc.X) + sqr(mc.Y); // Квадрат длины предыдущего вектора s := V.X * Mc.X + V.Y * Mc.Y; // Скалярное произведение D := sqr(s) + (4 * R - LMC) * LV; // Дискриминант Result := D >= 0; // Если есть решения if Result then begin D := sqrt(D); // то смотрим, чтобы хотя бы один из t оказался в допустимом диапазоне. Result := (abs(D - s) <= LV) or (abs(s + D) <= LV); end; end;

геометрия: пересечение окружности отрезком Найти похожие ветки