Wataru

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

Самая концептуально простая реализация будет, если сделать функцию для отсечения группы многоугольников полуплоскостью. Прямоугольник ваш - это 4 полуплоскости: 2 вертикальные и 2 горизонтальные. Пересечение с полуплоскостью проще - там тупо прямая же одна. Вот пресеките многоугольник с первой, полученные ответ со второй, потом что осталось с третьей и потом с четвертой полуплоскостью.

Удобно хранить множество точек и для каждой - указатель на сделующую в обходе многоугольника (ориентированного так, что слева от отрезка внутренность многоугольника). В таком виде входные данные, в таком виде будет и ответ.

Точки будем помечать, как обработанные.

Обойдите все точки циклом, для всех необработанных еще, которые лежат внутри полуплоскости, начинайте с них строить ломанную-ответ. Идите к следующей точке, пока отрезок не пересечет полуплоскость (это значит конец строго внутри удаляемой области), помечая точки обработанными. До этого момента добавляйте точки в ответ сохраняя указатель на следующую точку. Для текущей следующей сделайте новую точку - точку пересечения. Еще запомните где-то эту точку пересечения, это потом понадобится. Продолжайте обход, пока отрезок не выйдет из полуплоскости (конец строго снаружи удаляемой области). Тут создайте точку пересечения, запишите ее в ответ, и для нее следующей сделайте конец отрезка снаружи. Продолжайте обход как в начале. Если встретили уже обработанную точку, вы закончили строить ломанную ответ.

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

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

Удобно прямую хранить в виде Ax+By+C=0. И знак подобрать так, что точки внутри хорошей области, если их подставить в это уравнение дают положительные значения (а точки снаружи - будут отрицательные). Соответственно, проверка, что с точки можно начать обход - просто посмотреть на знак. Проверка, что есть пересечение - конец отрезка дает отрицательный знак (а потом - положительный). Точки удобно хранить в виде массива координат и массива номеров следующей точки в обходе. Никаких сишных указателей - номера следующей точки в массиве. Сортировать точки пересечения надо будет по значению Ay-Bx.

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

Это все удовольстивие будет работать за O(n log n) - потому что надо потом точки пересечения на прямой отсортировать.

Угол 0 куда смотрит? Куда смотрит 90 градусов? Обычно считают, что 0 смотрит строго враво, а 90 - вверх.

Шаг 1. Вам неважно, где именно находятся башня и цель, важно их относительное положение, поэтому посчитайте dx=x2-x1, dy = y2-y1

Шаг 2. Подставьте в какую-нибудь обратную тригонометрическую функцию, например arctan(dy/dx). Тут правда незадача, если dx=0, то надо смотреть на знак dy и выдавать sign(dy)*90. Еще проблема, что arctan вам вернет значение от -90 до 90 всегда. Если dx отрицательно, то надо прибавить 180.

Возьмите вектор любой из двух оставшихся сторон и ориентируйте его от вершины на проверяемой стороне. Потом посмотрите на знак векторного произведения. Оно отрицательно для нормалей наружу.

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

Ваш ромб - это 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;