Ответы пользователя по тегу Геометрия
  • Как грамотно остановить объект при столкновении?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    Во-первых, если скорости маленькие и движение происходит на маленькие отрезки за итерацию, то можно выталкивать объект в любую сторону.

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

    Есть концептуально простой но далеко не самый эффективный метод - бинарный поиск. Вот вы уже умеете определять, пересекаются ли 2 объекта. Изначально они не пересекались, после сдвигания на 1.0 едениц веремени они пересеклись. Делайте бинарный поиск по времени в отрезке (0, 1): посморите, есть ли пересечение при сдвиге на 0.5 единиц времени. Потом или 0.25 или 0.75 в зависимости от результата проверки. И так пока текущий отрезко в бинпоиске не станет достаточно мал. Но у этого метода большая проблема с большими скоростями - если за время итерации объекты пройдут сквозь друг друга - вы этого не заметите.

    Более быстрый метод - это реально искать пересечение тракетории. Для этого пустите лучи из каждой вершины одного объекта параллельные его скорости движения относительно второго объекта. Потом пересеките каждый луч со вторым многоугольником и найдите кратчайший луч. Аналогично надо пустить лучи из всех вершин второго многоугольника в обратную сторону и пересечь их все с первым многоугольником (это если движущийся наткнется на вершину препятствия стороной). Нашли длину минимального луча - на нее и сдвигайтесь. Если задавать лучи параметрически в виде point+t*v, то фактически вы ищете минимальное значение параметра t при пересечении у всех лучей (тут v - вектор скорости за один квант времени,point - вектор координат точки, из который выпустили луч).

    В этом методе не надо даже проверять, попадает ли после полного шага объект в препятствие. Нашли минимальное расстояние до пересечения (может быть и бесконечностью, если пересечений нет) - если оно больше сдвига за квант времени, то сдвигайтесь просто на квант времени. в параметрическом подходе, это значит, что сдвигаетесь вы на min(1.0, t).

    Этот метод можно соптимизировать с квадратичного до линейного. Представьте, что вектор движения горизонтален (и направлен влево). Можно просто повернуть все точки каждого многоугольника вместе со всем пространством или применять векторные/скалярные произведения для определения, какая точка ниже/левее/правее.

    Найдите в каждом многоугольнике самую нижнюю и самую верхнюю точку. Если эти промежутки по OY не пересекаются - то два объекта не столкнутся, можно останавливать проверки. Если промежутки по OY пересекаются, но второй обхект находится правее первого - то они отдаляются и опять можно дальше не проверять. Тут можно сравнить по одной любой точке с каждого объекта.

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

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

    Можно его до сублинейного соптимизировать через бинарный поиск опять, но тут уже очень сложно. Можно низшую и высшую точки искать за логарифм бинпоиском, а не как выше полным перебором всех точек. Потом тернарным поиском перебираете значение координаты Y и считаете расстояние между двумя многоугольниками вдоль этого горизонтального отрезка. Для этого, опять же бинпоиском, находите 2 отрезка пересекающих эту горизонталь в обоих многоуголниках и пересекаете с горизонталью, чтобы найти 2 конца расстояния. Эта функция расстояния dist(y) будет выпуклой. Поэтому уможно найти ее минимум тернарным поиском.
    Ответ написан
  • Как построить симуляцию луча?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    Как это часто бывает в задачах на отражение света, не надо отражать луч. Представьте, что зеркало - это портал в Зазеркалье. Луч идет прямо и, проходя через зеркало, попадает в соседнюю треугольную комнату.

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

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

    Но в этой задаче это вам не поможет никак - ибо симулировать эти 100500 отражений и квантилионы возможных начальных углов никакого времени не хватит.
    Ответ написан
  • Как разделить правильный пятиугольник на 3 равные части?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    Возьмите центр вписанной (и описанной) окружности. Разделите каждую сторону на 3 равные части. Проведите отрезки из центра во все 5 вершин и 10 точек на сторонах. Вы получите 15 треугольников, с одинаковыми внешними сторонами (1/3 стороны пятиугольника). Еще у всех этих треугольников одинаковые высоты (радиус вписанной окружности). Поэтому они все одинаковой площади. Теперь разбейте их на 3 группы по 5 подряд идущих треугольников - вот и ваши 3 равные по площади куска пятиугольника.

    Это работает не только для правильных пятиугольников - достаточно чтобы можно было вписать окружность в многоугольник. После чего проведите отрезки из центра вписанной окружности на границу так, чтобы длины периметров получившихся частей были одинаковыми. Площади будут равны длинам периметра * радиус окружности пополам.
    Ответ написан
  • Как узнать координаты точки, имея координаты исходного тела и расстояния до нее?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    Вот описание алгоритма пересечения двух окружностей.
    Стройте 2 окружности и пересекаете по этим формулам. У вас будет 2 точки. Проверьте, какая из них лежит на третьей окружности - это и будет искомый ответ.

    Аккуратно с крайними случаями - три центра окружностей не должны лежать на одной и той же прямой, иначе вы не сможете понять, какая из двух точек вам нужна.
    Ответ написан
  • Как определить положение круга на координатной плоскости?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    Рассмотрите варианты. Что значит, что круг касается одной четверти? Значит он не пересекается ни с одной из осей координат, т.е. самая нижняя точка круга выше OX, или самая верхняя ниже OX и аналогично для OY.
    Может ли круг касаться двух четвертей? Запросто. Если исключить первый случай сначала, то получится, что круг должен пересекать ровно одну из осей. Далее, может ли круг касаться трех четвертей? Порисуйте, подумайте, и поймите, что нет (подсказка - круг выпуклая фигура, отрезок между любыми двумя точками в круге целиком лежит в круге). Остается только четвертый вариант. Т.е. если не 1 и не 2 четверти, то точно 4.
    Ответ написан
  • Как разложить полигон на дерево вершин?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, гуглер, экс-олимпиадник.
    Похоже автор напутал. Слышал где-то про логарифмический алгоритм, знает, что за логарифм обычно работают сбалансированные бинарные деревья, вот и связал это воедино.

    В случае с трассировкой лучей, за логарифм нет реализации вообще - ибо у невыпуклого многоугольника может быть O(n) пересечений с лучем (представьте себе пилу).

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

    За логарифм есть решение через бинарный поиск.
    Разбейте пространство на вертикальные колонны всеми x координатами всех вершин многоугольника. Внутри каждой из них будет проходить четное количество сторон. Составьте для каждой стороны уравнение и отсортируйте их по высоте.

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

    Проблема этого метода, что он требует O(n^2) памяти в худшем случае и такую же предобработку.
    Но, для выпуклых многоугольников, прямых в каждой колонне будет всего две. Вот описание метода с реализацией для этого упрощенного случая.
    Ответ написан
  • Как проверить, попадает ли географическая точка в правильный шестиугольник?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    Вычтите координаты центра из координат точки. Теперь шестиугольник лежит центром в (0, 0).

    Составьте 6 уравнений сторон шестиугольника в виде Ax+By+C=0, так что C положительно (если нет - домножте на -1). Подставьте в эти 6 уравнений координаты точки, все они должны дать положительные значения (или нули, если точка на границе считается лежащей внутри в вашей задаче).

    Почему это работает? Мы просто проверяем, что точка лежит с той же стороны от всех 6 прямых, что и центр (0, 0).

    Как составить уравнения? Найдите координаты 6-ти углов. Если сторона = a, то координаты точек (a, 0), (a/2, sqrt(3)*a/2), (-a/2, sqrt(3)*a/2), (-a, 0) ...

    Для уравнения одной из сторон возьмите в виде A разность по у у соседних точек, а в виде B разность по x (но с другим знаком). Потом подставьте туда координаты одной из точек и возьмите C так, чтобы был 0.

    Можно все 6 уравнений составить на бумажке и закодировать в программе.

    Пример для первой стороны:
    A = sqrt(3)*a/2-0 = sqrt(3)*a/2
    B = a - a/2 = a/2
    C = -A*a - B*0 = -sqrt(3)*a*a/2.

    Поскольку C отрицательно, меняем знаки:
    A = -sqrt(3)*a/2
    B = -a/2
    C = sqrt(3)*a*a/2

    Для второй прямой будет 0*x-a*y+sqrt(3)*a*a/2 = 0

    И да, это работает, если предположить, что шестиугольник маленький или на плоскости. если у вас кривизна земли играет роль, то все сильно усложняется.
    Ответ написан
  • Python. Найти расстояние от точки до прямой, зная координаты этой точки?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    Составьте уравнение прямой вида a*x+b*y+c=0.
    Подставьте в это уравнение координаты точки. Возьмите по модулю и поделите на sqrt(a^2+b^2).
    Ответ написан
  • Почему основное тригонометрическое тождество работает всегда?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    > а почему тут работает ОТТ, если оно доказывается с помощью теоремы Пифагора?

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

    ОТТ применимо всегда! Для любых аргументов. Но, возможно вас именно это и запутало, после применения ОТТ и взятия корня, по идее, у вас получится +-sqrt(...). Потому что x^2=9 => x=3 или -3. Два варианта извлечения корня, 2 варианта для синуса.

    Но, поскольку вы знаете, что угол в треугольнике не может превышать 180 градусов, вы знаете, что синус этого угла всегда неотрицательный. Поэтому -sqrt() можно отбросить как лишнее значение и получить вашу формулу. В формальном доказательстве эти рассуждения надо учитывать.
    Ответ написан
  • Можно ли как-то оптимизировать/ускорить этот код?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    Как я уже писал в другом вопросе - вам не нужны касательные из каждой точки на все полигоны. Нужны лишь общие касательные к каждой паре полигонов. Если полигоны не пересекаются, то таких всего 4 штуки. Если же они пересекаются, то их может быть сколько угодно.

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

    Еще, возможно, тут проблема не в касательных. Вот у вас 20 полигонов, в каждом по 8 точек - это 160 точек начал. Для нахождения касательных к полигону можно перебрать все вершины. Это еще раз по 20*8=160. Итого, получается 160^2=25600 операций. Операции сложные (найти 3 вектора, взять векторные произведения), да. Но жаже если умножить это на 50, получается 1,280,000 элементарных операций. Современные процессоры выполняют миллиарды таких операций в секунду. Т.е по этой грубой прикидке - построение всех касательных занимает считанные миллисекунды.

    У вас очень тормозит проверка на пересечения возможных кандидатов с полигонами.
    Во-первых, как только вы нашли пересечение - можно дальше не проверять. Разделите циклы по intersect_any_1 и intersect_any_2 и останавливайтесь, как только нашли пересечение. Во-вторых, вы для каждой касательной заново строите объекты turf.js. Это, возможно, очень медленно.

    Ну и, похоже turf.js слишком тормозной. Моя демка на C++ для 100 полигонов находит все хорошие касательные без пересечений за 30мс. А если отсекать полигоны по bounding box, то 16-20мс. Ну в 10 раз javascript медленнее. У вас явно что-то совсем не то делается где-то.
    Ответ написан
  • Найти третью точку правильного треугольника?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    Логика у вас правильная - взять середину отрезка AB и отложить от него перпендикуляр длинной sqrt(3)/2*d.

    Но не надо искать углы, вектор перпендикуляр находится тривиально - это {y2-y1, x1-x2} (Можно доказать перпендикулярность через скалярное произведение, например). Более того, длина этого вектора будет уже d (это ведь повернутый на 90 градусов вектор по стороне треугольника). Значит его остается тупо домножить на sqrt(3)/2.

    Таким образом формула x3 = (x1+x2)/2 +sqrt(3)/2*(y2-y1).
    Ответ написан
  • Как найти точку, между двумя точками?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    векторная формула: A + (B-A)/sqrt(|A-B|)*3

    В числах
    x = Ax+(Bx-Ax)*3/sqrt((Ax-Bx)^2+(Ay-By)^2)
    y = Ay+(By-Ay)*3/sqrt((Ax-Bx)^2+(Ay-By)^2)
    Ответ написан
  • Как решаются эти задачи из аналитической геометрии?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    Сначала "решите" задачу на бумаге. Есть 2 точки, как построить третью вершину равностороннего треугольника? Пересечь 2 окружности. Или построить серединный перпендикуляр и отложить sqrt(3)/2*<длина отрезка> вдоль него.

    Пересечение окружностей - стандартная задача.
    Окружности с центрами в заданных точках и радиусом - расстояние между точками.

    Второе решение, если точки A и B - это взять (A+B)/2 (середина отрезка) и отложить от нее {By-Ay, Ax-Bx}*sqrt(3)/2 (перпендикулярный вектор, домноженный на коэффициент).

    Формулу второго решения можно получить если аналитически пересечь окружности. Итог будет тот же самый.
    Ответ написан
  • Как разделить все точки на плоскости на пары с минимальным расстоянием?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, гуглер, экс-олимпиадник.
    После сведения к теории графов есть решение за O(n^3) через венгерский алгоритм (реализация) или через алгоритм посика максимального потока минимальной стоимости (Там реализация, медленнее венгерского метода. Вот решение за n^3, но код готовый я не нашел).

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

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


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

    Пример
    3 вершины (0, 0), (1, 0) и (0, 1).
    Матрица расстояний (с 1e90 на диаганали вместо 0):
    ((1e90, 1, 1),
    (1, 1e90, 1.414),
    (1, 1.414, 1e90)).

    Решение ценой 3.414 (3-ий элемент в 1-ой строке, 1-ый во 2-ой строке и 2-ой в 3-ей)
    ((*, *, 1),
    (1, *, * ),
    (*, 1.414, *)).

    Это значит, что вы берете пары 1-3 2-1 3-2.
    Ответ написан
  • Как найти вектор сигнала в плоскости?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    Похожую задачу решает GPS (если забить на всякие физические эффекты).

    У вас будет 3 переменные - координаты источника сигнала (x, y) и время отправки сигнала (t).
    Вам даны координаты трех точек (x_i, y_i, i=0..2), три времени получения сигнала (t_1, t_2, t_3) и скорость сигнала (v).

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

    Уравнения, что сигнал проходит заданное расстояние за заданное время с известной скоростью:

    (x_i-x)^2+(y_i-y)^2 = ((t-t_i)*v)^2

    Можно время считать не в секундах, а в 1/v, тогда уравнения чуть упрощаются (коэффициент перед t^2 везде 1, а не v^2).

    Можно решать аналитически. Вычтите первое уравнение из двух остальных. У вас получится 2 линейных уравнения с тремя неизвестными x, y, t. Считайте, что t - это константа и решите уравнения относительно x и y (Через определители, или метод Краммера). У вас будет какая-то линейная зависимость x и у от t (большие формулы, да). Можно упростить вычисления, если cначала записать уравнения в виде A1x+B1y=C1+D1t.

    Потом подставьте эти зависимости в первое уравнение и у вас будет квадратичное уравнение на t.

    Решите его. Подставьте t в известные уравнения для x и y - и вот ваш центр (заодно вы знаете, когда был отравлен сигнал).

    Из двух значений t, одно будет в будущем (положительное), его надо будет отбросить.
    Ответ написан
  • Как узнать угол между двумя прямыми, если известны координаты через которые они проходят?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    Получите 2 вектора вдоль этих прямых (если прямые заданы параметрически - вы их уже знаете, если Ax+By+C=0, то это {-B,A}). Теперь угол между двумя векторами a и b - ваш искомый угол. Тут надо вспомнить, что векторное произведение - это |a|*|b|*sin x, а скалярное - |a|*|b|*cos x. Теперь вы знаете sin и cos искомого угла (поделив скалярное/векторное произведение на длины векторов). Можно скормить эти значения atan или еще какой-то обратной тригонометрической функции. Но на практике сам угол редко нужен, нужны в вычеслениях его sin и cos, а их вы уже знаете.
    Ответ написан
  • Какие существуют алгоритмы поиска равноудаленных прямоуголиников?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, гуглер, экс-олимпиадник.
    Ваш алгоритм надо лишь немного доработать.

    1) найти ближайший сверху (слева/снизу/справа) из тех, которые имеют перекрытие.
    2) повторить операцию, найдя следующий сверху. Расстояние между ними взять за d.
    3) продолжить идти вверх. Если следующий ближайший тоже на расстоянии d - нарисовать промежуток. Если нет, то остановится.
    4) Зная ближайший прямоугольник из пункта 1) и расстояние d - можно его отступить вниз и у вас есть точка примагничивания.

    Можно ускорить алгоритм немного. Сначала за один проход выделите все прямоугольники, которые выше данного, но пересекаются с ним по оси X. Отсортируйте их снизу вверх по нижней границе. Теперь в пунктах 1,2,3 надо рассматривать только один следующий прямоугольник из списка.

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

    Что бы ускорить еще больше, когда у вас очень много прямоугольников на экране, можно хранить их в quad tree и из него вытаскивать прямоугольники, которые перекрываются с заданным и выше его уже в правильном порядке. Но скорее всего просто пройтись по списку всех прямоугольников будет достаточно.
    Ответ написан
  • Пересечение двух линии в 3D?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, гуглер, экс-олимпиадник.
    Во первых, определите, что линии лежат на одной плоскости и не паралельны.
    Обозначим точки первой прямой как A1 и B1, а второй - A2 и B2.

    Введем вектора D1 = B1-A1 и D2 = B2-A2. Введем векторное уравнение.

    D1*t + D2*r + (A1-A2) = 0.

    Тут 2 неизвестные t и r, 3 уравнения (расписать по x, y и z).

    Если система уравнений решается, то точка пересечения A1+D1*t или A2 - D2*r.

    Тут правда предется повозиться со случаями. Надо попробовать решить систуму только для x, y, потом проверить в z. Если не получилось, то еще надо попробовать решить в x, z, потом поробовать подставить полученные r и t в у.
    Ответ написан