пересечение жирных отрезков

Ответить
lenin1st
Сообщения: 84
Зарегистрирован: 02 фев 2022, 10:15

пересечение жирных отрезков

Сообщение lenin1st »

представим 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, если бы мне не было лень>>>
Аватара пользователя
krt17
Сообщения: 377
Зарегистрирован: 17 апр 2018, 23:45

Сообщение krt17 »

семечки вредно, от них кариес и аппендицит
lenin1st
Сообщения: 84
Зарегистрирован: 02 фев 2022, 10:15

Сообщение lenin1st »

короче конвертнул org файл в html. дописал, исправил, в комплекте исходник программы. https://disk.yandex.ru/d/ozVEV6SfhTWUHw
Аватара пользователя
alex1ke
Сообщения: 225
Зарегистрирован: 11 мар 2021, 11:49

Сообщение alex1ke »

22 года назад выводил формулы вращения в 3д базисе через якобиан. и ведь вывел
а мог купить книжку со всем готовым)
картинки должны быть квадратными
Аватара пользователя
krt17
Сообщения: 377
Зарегистрирован: 17 апр 2018, 23:45

Сообщение krt17 »

Похоже на экзаменационный билет в школе или для поступающих.
lenin1st
Сообщения: 84
Зарегистрирован: 02 фев 2022, 10:15

Сообщение lenin1st »

ну так и есть, только для себя самого
Аватара пользователя
alex1ke
Сообщения: 225
Зарегистрирован: 11 мар 2021, 11:49

Сообщение alex1ke »

зацени математику jpeg на досуге)
картинки должны быть квадратными
lenin1st
Сообщения: 84
Зарегистрирован: 02 фев 2022, 10:15

Сообщение lenin1st »

alex1ke 87726 писал(а):22 года назад выводил формулы вращения в 3д базисе через якобиан. и ведь вывел
а мог купить книжку со всем готовым)
у меня так уже месяца 2 в голове якобиан - что это такое? (не вопрос). но до своего поворота вектора я дошёл так:
/ A точка
| B B*C!=0 векторы плоскости
| M точка плоскости
| S проекция точки A на плоскости в 2мерном пространстве
| S = ((A - M)*B / |B|,
\ (A - M)*C / |C|)

щас загружу демуху
lenin1st
Сообщения: 84
Зарегистрирован: 02 фев 2022, 10:15

Сообщение lenin1st »

блин, что я несу? поворот же нужен а не проекция.

поворот вектора A (по часовой) на плоскости AC, вокруг B - нормаль плоскости.
/ A, B, при |A| = |B| = 1, deg(A, B) = 90
| D, при deg(D, A) = g
| C = [A*B] но для правой ориентации, для левой (против часовой) [B*A]
\ D = A * cos(g) + C * sin(g) ненормализированный
Последний раз редактировалось lenin1st 30 апр 2022, 12:29, всего редактировалось 1 раз.
lenin1st
Сообщения: 84
Зарегистрирован: 02 фев 2022, 10:15

Сообщение lenin1st »

Ответить