Wataru

Не надо объект поворачивать. надо его рисовать сразу правильно ориентированным.

Ваш ромб - это 4 точки. Одну вы знаете - она на окружности, под заданным углом в зависимости от скорости. Вы эту точку вычислять умеете - вы туда стрелочку спидометра рисуете.

Противоположную точку вы можете легко найти - она под тем же углом, но на окружности большего радиуса.

Две оставшееся точки на окружности какого-то среднего радиуса под углами с небольшим отклонением от предыдущего угла в обе стороны.

Эти углы надо будет рассчитать на бумажке. Нарисуйте 2 коружности заданого радиуса, постройте между ними ромб, проведите его диагонали, найдете там парочку прямоугольних треугольников. В программе можно будет просто эти длины засунуть в формулы и скормить какой-нибудь atan2() функции.

Точно, расстояние до вектора надо? А не экстремальную точку вдоль вектора? В GJK алгоритме ищут точку, которая как уектор дает максимальное скалярное полизведение с заданым вектором - т.е. самую далекую вдрль вектора, дающую самую дальную проекцию.

Я бы в таком случае добавлял обе вершины от второго многоугольника, которые лежат на первом. Так все новые ребра каждого многоугольника или целиком не пересекаются со вторым, или целиком лежат внутри него, или целиком на его границе.

Т.е. действительно, в вашем случае надо в AIJH добавить точки ABKJH.

Образуются ребра длины 0 - значит повторяющиеся вершины надо просто выкинуть.

Для начала, надо бы уточнить условие. Ибо непясно, по какому принципу выбирается, какая из двух отсекаемых прямой половин берется в ответ.

Картинке удовлетворяет такая интерпретация: Берется область, остекаемая прямыми, содержащая центр квадрата. Предполагаем, что прямые через центр не проходят.

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

Эта задача решается за O(n log n). Задайте каждую прямую в виде ax+by+c=0. Т.ч. вектор {a,b} выпущенный с прямой, торчит в сторону полуплоскости, которую надо взять. Если вдруг не так, то надо поменять знак у всех трех коэффициентов.

Разбейте все прямые на 2 множества, те - которые смотрят "вверх" и те, которые смотрят "вниз". Если вектор нормали имеет положительную y координату - это смотрит вверх. Вертикальные прямые можно включить, допустим, в верхнее множество.

В каждом множестве построим ломанную, отделяющую нужную область. Это будет выпуклая область с двумя бесконечными лучами в конце.

Потом отсортируйте все прямые по углу наклона вектора {a,b}. Это можно сделать без тригонометрии, сравнивая векторы по векторному произведению. Ну, или просто какую-нибудь функцию вроде atan2() используйте.

Потом будем поддерживать ломанную, описывающую пересечение первых k проуплоскостей. Изначально это просто одна прямая (для первой полуплоскости). Будем хранить это как стек из прямых и рядом стек из точек пересечения. Изначально там только одна прямая и 0 точек пересечения.

Потом добавляем полуплоскости по одной. Пока последняя вершина на ломанной не лежит в нужной полуплоскости, выбрасываем ее. Для этого убираем из обоих стеков последний элемент. Это можно проверить, просто подставив координаты точки в уравнение ax+by+c. Если даст отрицательное значение - выбрасываем.
Если точек не осталось, или точка лежит где надо, то новую прямую надо пересечь с последней прямой. Точку пересечения и новую прямую добавляем в стек.

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

Есть еще вот такое решение. Выводится так: задаем обе прямые параметрически (точка + t или u, помноженная на вектор вдоль прямой). Получаем выражение для квадрата расстояния между точками как функцию от t и u. Ищем ее минимум, приравняв к 0 частичные производные. Там получаются 2 линейных уравнения.

Vector3 a = axis2.first - axis1.first;
Vector3 v1 = axis1.second - axis1.first;
Vector3 v2 = axis2.second - axis2.first;
float v11 = Vector3::DotProduct(v1, v1);
float v12 = Vector3::DotProduct(v1, v2);
float v22 = Vector3::DotProduct(v2, v2);
float av1 = Vector3::DotProduct(a, v1);
float av2 = Vector3::DotProduct(a, v2);
// Решаем систему методом Крамера:
// t*v11-u*v12=av1
// t*v12-u*v22=av2
float d1 = -av1*v22+v12*av2;
float d2 = v11*av2-v22*av1;
float d = -v11*v22+v12*v12;
float t = d1/d;
float u = d2/d;
point1 = axis1.first + v1 * t;
point2 = axis2.first + v2 * u;

Тут нужна школьная геометрия. Класс на 9, наврено даже раньше. Координаты центров шаров через время t будут (x1(t),y1(t))=(x1+vx1*t, y1+vy1*t)

Во-первых, проверьте, что шары сейчас не пересекаются. Иначе выталкивайте их вдоль прямой через центры.
Потом вам надо решить уравнение квадратное уравнение (x1(t)-x2(t))^2+(y1(t)-y2(t))^2 = 4*r^2.

Найдите минимальное положительное решение. Вот через это время шары столкнуться. Как вы там со стенами считаете - надо будет взять минимальное время и на него сдвинуть шары, а потом обработать столкновение.

Если 2 шара столкнулись, то их скорости поменяются вдоль вектора на их ценры. Надо решить уравнения сохрнения импульса и энергии. Решение смотрите тут (Формулы в комментарии в моем ответе там).

P.s. у вас там в коде вижу ошибку. Вы где считате пересечение со стенами знаки напутали. Должно быть:

float t1 = (0.5 * Lxmax - (cords[i].x + r)) / cords[i].vx;
float t2 = (-0.5 * Lxmax - (cords[i].x - r)) / cords[i].vx;

Ну и вы там не проверяете, вдруг скорость нулевая, тогда время до пересечения - бесконечность.

Удобно ввести новую систему координат и потом откладывать ее базисные векторы нужное количество раз.
Эта система будет иметь центр на радиусе сферы к центру оружности и лежать на "хорде" - плоскости в которой лежит многоугольник. В ней ваш многоугольник будет просто на плоскости.

Из простейшей геметрии вы знаете, что этот центр координат будет на расстоянии sqrt(R^2-r^2) от центра сферы - так радиус окружности на сфере будет r.

Первый базисный вектор будет вдоль радиуса из центра сферы к центру многоугольника и координата там будет всегда 0.
Теперь вам надо найти еще какой-то вектор в плоскости многоугольника, а третий вектор потом найдете через векторное произведение. Хорошо бы этот второй вектор взять на север, тогда ясно куда класть первую точку по условию. Если только центр окружности не лежит строго на свере, то можно взять и спроецировать на плоскость вертикальный вектор (0, 0, 1) и все (а в противном случае проецируйте, допустим (1, 0, 0). А дальше останется только взять формулы для многоугольника на плоскости x = cos(2*pi/n*k)*r y = sin(2*pi/n*k)*r, ну и не забыть перевести все в обычную систему координат.

Итак, пусть xo,yo,zo - точка на сфере, где лежит центр. xo и yo не нули одновременно. Еще даны R, r и n.

Центр новых координат:

L = sqrt(R^2 - r^2)
x1 = xo/R*L
y1 = yo/R*L
z1 = zo/R*L

Первый базисный вектор:
e1 = (x0, y0, z0) / R
Второй базисный вектор (нормализованный (0,0,1) - (0,0,1)*e1):

e2 = (-x0*z0/R/sqrt(R^2- z0^2), -y0*z0/R/sqrt(R^2- z0^2), sqrt(R^2-z0^2)/R)

третий базисный ветор, найдите сами через векторное произведение.

А дальше координаты k-ой точки:

p = (x1,y1,z1) +e2*cos(2*pi/n*k)*r+e3*sin(2*pi/n*k)

Чтобы расставить жуков оптимально, надо бинпоиском перебрать максимально разрешенное растояние и дальше проверить, что в графе из расстояний, не больше заданного, есть полное паросочетание.

Еще, угол поворота надо искать троичным поиском, ибо функция не монотонна, а пооизводную фиг найдете. В итоге у вас будет троичный поиск, запускающий двоичный поиск, щапускающий поиск паросочетания.

Нет. Потому что кривая называется "кубической" не потому, что там 4 разные точки, а потому что она задается уравнением третьей степени (кубы): a(1-t)^3+bt(1-t)^2+ct^2(1-t)+dt^3. Если вы приравняете b и c, то уравнение так и останется кубическим и в квадртаичное не превратится.

Кажется, надо составить уравнение/функцию, которая говорит, что точка попала в данную фигуру. Фигуры, скорее всего, задаются цветом.

x, y - переменные. Они изображаются на графике. x0, y0, a - какие-то фиксированные параметры прямой, числа. Точка, через которую она проходит и наклон.

Синяя линяя, наверно, прямая, описываемая этим уравнением.