пересечение жирных отрезков
Добавлено: 18 фев 2022, 13:44
представим 2 отрезка как траектории движения 2х окружностей выполняемые за один
момент времени. где будет их точка или точки столкновения (если будут)? избегая
случай, когда объекты (окружности) удлиняются на всё пространство от начало до
конца... было бы приятно узнать самую раннюю точку. конечно, можно разбить время
на кванты и двигать объекты на какое-то малое расстояние, но это путь слабых.
(эти подробности от того, что я не могу придумать о чём пойдёт речь. надеюсь не
слишком бредово)
координаты: x1,y1, x2,y2
длины: a1,b1, a2,b2
расстояние: r
к чёрту точку, нужны другие точки, центры окружностей на отрезках. они должны
быть на одном коэффициенте длины обоих отрезков. ведь на 0 они оба на месте, а
на 1 они оба на целевой позиции. также, они должны быть на расстоянии в сумме
радиусов обоих окружностей друг от друга.
(к сожалению я не умею строить кривые, а кажется ими можно что-то визуально
показать... и так сойдёт)
тогда система уравнений:
/ x3 = x1 + a1 * k
{ y3 = y1 + b1 * k
{ x4 = x2 + a2 * k
{ y4 = y2 + b2 * k
\ (x3-x4)^2 + (y3-y4)^2 = r^2 <=> sqrt((x3-x4)^2 + (y3-y4)^2) = r
<=>
((x1+a1*k)-(x2+a2*k))^2 + ((y1+b1*k)-(y2+b2*k))^2 = r^2
<=>
x1^2 + 2*x1*a1*k + (a1*k)^2 + x2^2 + 2*x2*a2*k + (a2*k)^2
+ y1^2 + 2*y1*b1*k + (b1*k)^2 + y2^2 + 2*y2*b2*k + (b2*k)^2
- 2*x1*x2 - 2*a1*x2*k - 2*x1*a2*k - 2*a1*a2*k^2
- 2*y1*y2 - 2*b1*y2*k - 2*y1*b2*k - 2*b1*b2*k^2 = r^2
(раскладывал до самых нераскладываемых, привожу как крайность. гуглить формулы
сокращенного умножения)
<=>
((x1-x2)*(a1-a2) + (y1-y2)*(b1-b2))*2*k
+ ((a1-a2)^2 + (b1-b2)^2)*k^2
- r^2 + (x1-x2)^2 + (y1-y2)^2 = 0
(итог)
и это - квадратное уравнение (к моему недавнему удивлению):
/ a = ((a1-a2)^2 + (b1-b2)^2)
{ b = ((x1-x2)*(a1-a2) + (y1-y2)*(b1-b2))*2
{ c = - r^2 + (x1-x2)^2 + (y1-y2)^2
\ a*k^2 + b*k + c = 0
и чисто по формуле из учебника (например https://www.resolventa.ru/spr/algebra/kv.htm):
a*k^2 + b*k + c = 0
<=>
/D = b^2 - 4*a*c
\a * (k + (b + sqrt(D)) / (2*a)) * (k + (b - sqrt(D)) / (2*a)) = 0
(a не может быть 0 (из за деления на 0), и правая часть обоих (кроме a) членов
тоже. чтобы получился 0, один из этих членов должен должен быть 0. а это (в
данных условиях) может быть только если x равен одной из правых частей этих
членов со знаком минус)
(D<0 нет корня)
при D >= 0
k1 = - (b + sqrt(D)) / (2*a)
k2 = - (b - sqrt(D)) / (2*a)
(решения 2. они равны при D = 0)
далее, 0<=k<=1, потому что по условию иначе быть не может.
и доказывать я, естественно, ничего не буду (или и не надо), потому что не
барское это дело. одни примеры замучился делать, мне семечко зуб пробило (а
конкретно жопка попала на кариес), сижу с кинжалом в дисне (болеутоляюсь пивом
через трубочку).
ПРИМЕР 1
x1=-2, y1=-5, x2=8, y2=2
a1=0, b1=8, a2=-16, b2=0
r=5.65... = sqrt(4^2+4^2) (чтобы красиво было)
a = ((a1-a2)^2 + (b1-b2)^2) = ((0--16)^2 + (8-0)^2) = 320
b = ((x1-x2)*(a1-a2) + (y1-y2)*(b1-b2))*2 = ((-2-8)*(0--16) + (-5-2)*(8-0))*2 = -432
c = - r^2 + (x1-x2)^2 + (y1-y2)^2 = - 5.65...^2 + (-2-8)^2 + (-5-2)^2 = 116.(9)
D = b^2 - 4*a*c = -432^2 - 4*320*116.(9) = 36864.00...
D >= 0 - решение есть
k1 = (-b + sqrt(D)) / (2*a) = 0.975
k2 = (-b - sqrt(D)) / (2*a) = 0.375
x3 = x1 + a1 * k1
y3 = y1 + b1 * k1
x4 = x2 + a2 * k1
y4 = y2 + b2 * k1
x5 = x1 + a1 * k2
y5 = y1 + b1 * k2
x6 = x2 + a2 * k2
y6 = y2 + b2 * k2
disk.yandex.ru/i/u9_KcClgyhcAGQ
ну и, от k2 до k1 они (округлые объекты) пересекаются.
<<<тут были бы примеры, если бы мне не было лень>>>
ПРОГРАММА
вот программа на си. нужна линковка с sdl2, за окружности простите, в сдл их не
завезли так что сделал как смог.
<<<тут был бы файл fatline-inter.c, если бы мне не было лень>>>
момент времени. где будет их точка или точки столкновения (если будут)? избегая
случай, когда объекты (окружности) удлиняются на всё пространство от начало до
конца... было бы приятно узнать самую раннюю точку. конечно, можно разбить время
на кванты и двигать объекты на какое-то малое расстояние, но это путь слабых.
(эти подробности от того, что я не могу придумать о чём пойдёт речь. надеюсь не
слишком бредово)
координаты: x1,y1, x2,y2
длины: a1,b1, a2,b2
расстояние: r
к чёрту точку, нужны другие точки, центры окружностей на отрезках. они должны
быть на одном коэффициенте длины обоих отрезков. ведь на 0 они оба на месте, а
на 1 они оба на целевой позиции. также, они должны быть на расстоянии в сумме
радиусов обоих окружностей друг от друга.
(к сожалению я не умею строить кривые, а кажется ими можно что-то визуально
показать... и так сойдёт)
тогда система уравнений:
/ x3 = x1 + a1 * k
{ y3 = y1 + b1 * k
{ x4 = x2 + a2 * k
{ y4 = y2 + b2 * k
\ (x3-x4)^2 + (y3-y4)^2 = r^2 <=> sqrt((x3-x4)^2 + (y3-y4)^2) = r
<=>
((x1+a1*k)-(x2+a2*k))^2 + ((y1+b1*k)-(y2+b2*k))^2 = r^2
<=>
x1^2 + 2*x1*a1*k + (a1*k)^2 + x2^2 + 2*x2*a2*k + (a2*k)^2
+ y1^2 + 2*y1*b1*k + (b1*k)^2 + y2^2 + 2*y2*b2*k + (b2*k)^2
- 2*x1*x2 - 2*a1*x2*k - 2*x1*a2*k - 2*a1*a2*k^2
- 2*y1*y2 - 2*b1*y2*k - 2*y1*b2*k - 2*b1*b2*k^2 = r^2
(раскладывал до самых нераскладываемых, привожу как крайность. гуглить формулы
сокращенного умножения)
<=>
((x1-x2)*(a1-a2) + (y1-y2)*(b1-b2))*2*k
+ ((a1-a2)^2 + (b1-b2)^2)*k^2
- r^2 + (x1-x2)^2 + (y1-y2)^2 = 0
(итог)
и это - квадратное уравнение (к моему недавнему удивлению):
/ a = ((a1-a2)^2 + (b1-b2)^2)
{ b = ((x1-x2)*(a1-a2) + (y1-y2)*(b1-b2))*2
{ c = - r^2 + (x1-x2)^2 + (y1-y2)^2
\ a*k^2 + b*k + c = 0
и чисто по формуле из учебника (например https://www.resolventa.ru/spr/algebra/kv.htm):
a*k^2 + b*k + c = 0
<=>
/D = b^2 - 4*a*c
\a * (k + (b + sqrt(D)) / (2*a)) * (k + (b - sqrt(D)) / (2*a)) = 0
(a не может быть 0 (из за деления на 0), и правая часть обоих (кроме a) членов
тоже. чтобы получился 0, один из этих членов должен должен быть 0. а это (в
данных условиях) может быть только если x равен одной из правых частей этих
членов со знаком минус)
(D<0 нет корня)
при D >= 0
k1 = - (b + sqrt(D)) / (2*a)
k2 = - (b - sqrt(D)) / (2*a)
(решения 2. они равны при D = 0)
далее, 0<=k<=1, потому что по условию иначе быть не может.
и доказывать я, естественно, ничего не буду (или и не надо), потому что не
барское это дело. одни примеры замучился делать, мне семечко зуб пробило (а
конкретно жопка попала на кариес), сижу с кинжалом в дисне (болеутоляюсь пивом
через трубочку).
ПРИМЕР 1
x1=-2, y1=-5, x2=8, y2=2
a1=0, b1=8, a2=-16, b2=0
r=5.65... = sqrt(4^2+4^2) (чтобы красиво было)
a = ((a1-a2)^2 + (b1-b2)^2) = ((0--16)^2 + (8-0)^2) = 320
b = ((x1-x2)*(a1-a2) + (y1-y2)*(b1-b2))*2 = ((-2-8)*(0--16) + (-5-2)*(8-0))*2 = -432
c = - r^2 + (x1-x2)^2 + (y1-y2)^2 = - 5.65...^2 + (-2-8)^2 + (-5-2)^2 = 116.(9)
D = b^2 - 4*a*c = -432^2 - 4*320*116.(9) = 36864.00...
D >= 0 - решение есть
k1 = (-b + sqrt(D)) / (2*a) = 0.975
k2 = (-b - sqrt(D)) / (2*a) = 0.375
x3 = x1 + a1 * k1
y3 = y1 + b1 * k1
x4 = x2 + a2 * k1
y4 = y2 + b2 * k1
x5 = x1 + a1 * k2
y5 = y1 + b1 * k2
x6 = x2 + a2 * k2
y6 = y2 + b2 * k2
disk.yandex.ru/i/u9_KcClgyhcAGQ
ну и, от k2 до k1 они (округлые объекты) пересекаются.
<<<тут были бы примеры, если бы мне не было лень>>>
ПРОГРАММА
вот программа на си. нужна линковка с sdl2, за окружности простите, в сдл их не
завезли так что сделал как смог.
<<<тут был бы файл fatline-inter.c, если бы мне не было лень>>>