Как стать автором
Обновить

Комментарии 36

Однако данный способ становится достаточно громоздким при написании кода (возможно поэтому вы сейчас читаете эту статью), к тому же, он не является универсальным: если одна из прямых параллельна оси Y, мы получим ошибку деления на ноль при вычислении углового коэффициента, и нам придётся прописать код на этот случай; если две прямые параллельны, требуется повозиться с обработкой и этого случая. Такой код становится длинным и некрасивым.

Тем не менее, в вашем коде также приходится прописывать код на случай совпадающих и пересекающихся под прямым углом прямых. Где же преимущество?

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

Спасибо, в следующий раз буду аккуратнее в формулировках
Ничто не мешает подобрать более аккуратную формулировку и внести изменение и в эту статью
Какой результат будет на таких данных?
x1=1, y1=2
x2=4, y2=1
x3=2, y3=5
x4=8, y4=3
Ваш способ вычислительно идентичен способу с уравнениями прямых. Там тоже получается система из двух уравнений: p1 + k*a = p4 + n*b, где p1, p2 — координаты точек.

Но это же не уравнения прямых, по крайней мере, в том смысле, в котором я их упоминал в статье. Алгебраически они задаются как y = ax+b

Это в школе.

В это алгебраическое определение как-то не вписываются вертикальные прямые. Так что лучше задавать прямые в виде p+kv, где p — точка на прямой, v — вектор, параллельный прямой.

Ну нет, уравнение прямой всегда было ax + by + c = 0.

офф Может кто подскажет по стереометрии простой способ вычислить попадет ли отрезок (или прямая) в заданный цилиндр?
что значит «попадёт»? Математика вместе со своей сестрой Геометрией (а также кузиной Стереометрией) требует точных и недвусмысленных формулировок
Видимо имеется в виду «попадет» или «промахнётся» </шутка>
А если серьезно, то «расположена».
А если серьезно
нет, это не серьёзно:
если прямая, то расположена целиком? если отрезок, то расположен отрезок целиком в цилиндре или прямая, задаваемая отрезком, целиком расположена в цилиндре (здесь я имею в виду бесконечный цилиндр, а что имеет в виду автор вопроса, можно только гадать)

А это не имеет значения. Все равно основным моментом будет нахождение точек пересечения прямой с бесконечным цилиндром и двумя плоскостями (если цилиндр не бесконечный).


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

Это примерно то что надо. Уточните что искать?
В данном случае я сказал в практическом смысле зачем мне это надо — расчет траектории летящего объекта на столкновение с объектом. Для упрощения расчетов объект — это цилиндр.
Только это не сняло неполноты и неоднозначности вопроса.
Получается, что вас интересует пересечение двух бесконечных цилиндров?
рассчитайте расстояние между двумя прямыми (осями цилиндров) и если сумма полугабаритов (радиусов цилиндров) обоих объектов больше этого расстояния — дело плохо (или наоборот хорошо, если столкновение — это благоприятный исход)
Эта публикация навела на мысли что гуглить и я нашел — Intersection of two paths given start points and bearings (Пересечение двух путей с учетом начальных точек и направлений).

Вопрос я сам не очень-то мог сформулировать — что-то вроде упреждения при стрельбе по цели с известными начальными координатами и направлением движения, причем зона поражения стреляющего имеет форму конуса определенных угловых размеров.
Ниже я дал книжку, в пространстве: в 7 главе.
Все-таки «отрезок» это не «прямая». Как я понял, для вашего алгоритма надо предварительно выбрать подходящие отрезки, что бы пересечение гарантировано было внутри них. И весь смысл упрощений теряется.

Я к тому, что искать пересечение прямых (как в заголовке) это одно, а пересечение отрезков (как в статье) это другое немного.
Честно говоря, всегда удивляло, почему в играх как правило используется параметрическое представление кривых, а в школе этот тип представления либо не дается, либо о нем сами учителя не знают :) Иначе очень трудно объяснить почему народ пытается решать такие задачки в функциональном стиле, ведь на самом деле все очень просто. Самому было лень писать, поэтому просто приведу код первый попавшийся в запросе гугла на псевдо С++:
#include <iostream>
#include <cmath>
using namespace std;
 
int main() 
{
    double x1, y1, x2, y2, x3, y3, x4, y4;
    double Ua, Ub, numerator_a, numerator_b, denominator;
    
    cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;

    denominator=(y4-y3)*(x1-x2)-(x4-x3)*(y1-y2);

    if (denominator == 0) {
        if ( (x1*y2-x2*y1)*(x4-x3) - (x3*y4-x4*y3)*(x2-x1) == 0 && (x1*y2-x2*y1)*(y4-y3) - (x3*y4-x4*y3)*(y2-y1) == 0)
            cout << "Отрезки пересекаются (совпадают)";
        else 
            cout << "Отрезки не пересекаются (параллельны)";
    }
    else{
        numerator_a=(x4-x2)*(y4-y3)-(x4-x3)*(y4-y2);
        numerator_b=(x1-x2)*(y4-y2)-(x4-x2)*(y1-y2);
        Ua=numerator_a/denominator;
        Ub=numerator_b/denominator;

        cout << (Ua >=0 && Ua <=1 && Ub >=0 && Ub <=1 ? "Отрезки пересекаются" : "Отрезки не пересекаются");
    }

    return 0;
}
Ua и Ub и есть параметры каждого отрезка. Если они оба лежат в пределах 0.0 < 1.0 то отрезки пересекаются. Код кажется сложным, но на самом деле это просто развертка решения системы двух линейных параметрических уравнений относительно Ua и Ub, а также можно заметить что многие суммы совпадают и на практике их можно вычислить один раз. Подставив Ua или Ub обратно в любое из уравнений можно вычислить саму точку пересечения, например в векторном виде:
Pc = P(x1, y1) + P(x2, y2) * Ua;
Pc = P(x3, y3) + P(x4, y4) * Ub;

x = x1*Ua + x2*(1-Ua) = x3*Ub + x4*(1-Ub)
y = y1*Ua + y2*(1-Ua) = y3*Ub + y4*(1-Ub)

Если представить точки в виде (x,y,1) то их (двух точек) cross product даст уравнение прямой. L= P0xP1. Соответственно cross product двух линий — точка. И никаких сложных вычислений — простая алгебра. Что интересно, что нормализацию (деление ) на третий компонент, можно производить только в конце цепочки вычислений, а так линии и точки обрабатываются единообразно и без исключений особых случаев.
Причем можно метод расширить до плоскостей и точек в трехмерном пространстве, только плоскость будет образовываться тремя точками, а точка тремя плоскостями
Да, когда-то все эти вопросы разбирались в замечательной книжке: image, читайте 3 главу
И, по моему, в каких-то эхоконференциях регулярно ходил Faq на эту тему, возможно Ru.Graphics, но я нашёл только demo design 3d faq там нет пересечения линий, а чисто 3D
Однако данный способ [...] не является универсальным: если одна из прямых параллельна оси Y, мы получим ошибку деления на ноль при вычислении углового коэффициента, и нам придётся прописать код на этот случай

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


Я когда-то задавал эту задачку студентам-первокурсникам на лабах по C++. Ожидал увидеть какое-то такое решение:


— составить два общих уравнения прямой (в форме Аx + Bx + С = 0);
— подстановкой точек в левые части уравнений убедиться, что концы отрезков лежат по разные стороны от этих прямых;
— решить систему методом Крамера.


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

НЛО прилетело и опубликовало эту надпись здесь

Верно, проблема с устойчивостью — это огромная проблема при решении СЛАУ. А минимизация квадратичного отклонения — один из способов регуляризации.


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

НЛО прилетело и опубликовало эту надпись здесь

Какой там нафиг ряд может расходиться, когда оба метода используют лишь 4 базовые арифметические операции?


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

НЛО прилетело и опубликовало эту надпись здесь

Вот когда будет поставлена задача искать точку пересечения N гиперплоскостей в M-мерном пространстве, тогда и будем придумывать решение. А вот придумывать вундервафлю для решения простейшей задачи не стоит совершенно.

НЛО прилетело и опубликовало эту надпись здесь
Зарегистрируйтесь на Хабре, чтобы оставить комментарий

Публикации

Истории