На питоне небольшая опечатка в коде. Строка 71. Вместо vector_cb указан vector_cd. VS подсветил неиспользуемую переменную vector_cb на 66 строке. Огромное спасибо за это видео! Использовал раньше другой алгоритм. Он начал давать мне пересечение в случае, когда отрезки находились на одной прямой. Вы меня выручили.
+ за тем же полез, тема имба, а если еще подучить линии пересечения плоскостей, и пересечение обьëмов то можно уже интересные коллизии выяснять. типа взмах меча между кадрам с помощью вычисления пересечения плоскости с обьектом, чтобы между кадрами меч не проскакивал через обьект и регистрировал нормально его.
По-моему проще решить систему линейных уравнений =). 1) Прямая AB: x = Ax*(1-t1)+Bx*t1; y = Ay*(1-t1)+By*t1; 2) прямая CD: x = Cx*(1-t2)+Dx*t2; y = Cy*(1-t2)+Dy*t2; Имеем на входе 8 координат, а на выходе получим два числа - t1 и t2. Если оба лежат в промежутке [0;1], значит отрезки пересекаются. Плюс мы ещё и сможет сразу найти ТОЧКУ пересечения, а не только сам факт пересечения. Единственный минус - если отрезки лежат на одной прямой, то мы получим деление на ноль =(. Но эту ошибку можно сразу расценить как тот факт, что они лежат на одной прямой. И далее легко понять пересекаются они или нет сравнив координаты.
Добрый день. Спасибо за проявленный интерес. Предложенное вами решение действительно хорошо себя покажет в математике, но с точки зрения вычислительной геометрии оно уже не так хорошо. Как вы верно заметили для решения системы уравнений нужно использовать деление (и не один раз), а это медленная операция на ПК. А вот решение на основе псевдоскалярного произведения только умножение (быстро) и вычитание (очень быстро). Также огорчает необходимость отдельной обработки отрезков на одной прямой. И что еще хуже из за ограничения машинного представления вещественного числа, отрезки с очень близким углом наклона в вашем алгоритме будут считаться лежащими на одной прямой (разница различимых вещественных чисел, легко становиться не различимой от нуля). Хотя как вы верно заметили ваш алгоритм позволяет найти еще точку пересечения, но в ряде задач это не нужно. Это видео больше о таких задачах :).
@@oleksandrtsymbaliuk Спасибо за развёрнутый ответ. Действительно в ряде случаев достаточно лишь факта пересечения. На ум приходит необходимость проверки лежит ли точка внутри фигуры или нет. Можно проверить лишь факты пересечения какого-либо луча выпущенного из данной точки со сторонами фигуры. Если кол-во пересечений чётное, значит мы вне фигуры. Если нечётное - значит внутри. Единственное опять-таки есть сложность. Если луч проходит строго через вершину, то результат может быть неверным. Поэтому неплохо бы отличать такой случай пересечения от других. Если я верно понял, то в вашем примере в такой ситуации одно из псевдоскалярных произведений будет равно нулю?
Ну если фигура более менее правильный многоугольник то факт попадания точки лучше опять же проверять с помощью псевдоскалярного произведения. Исключительных ситуаций типа попадание в вершину или на сторону опять же не будет. А вот если фигура что то типа эллипса то да тут прийдеться думать. Ну или в конце концов просто использовать выметание которое работает почти всегда но сложное :)
@@oleksandrtsymbaliuk Про эллипс сложно =). Нет, я имел ввиду произвольный многоугольник, не обязательно выпуклый (иначе совсем просто). Единственное у меня вопрос: если я ищу пересечение через уравнения, то для луча (полупрямой) мне достаточно снять ограничение для t1 или t2 (чтобы он мог быть >1 или
@@oleksandrtsymbaliuk А хотя я понял =). Сглупил. Достаточно просто потребовать разных знаков для точек отрезка, а для второй пары векторов это требование убрать. Это значит что отрезок пересёк ПРЯМУЮ. Точнее нас устроит два случая: если знаки разные и если они оба либо положительные, либо отрицательные (в зависимости от направления луча). Прохождение же луча через вершину означает, что одно из произведений (первых) будет равно нулю. Такие ситуации лучше обрабатывать отдельно в зависимости от задачи.
Правильней, наверное, было бы в структуре Вектор хранить одну точку. Направление от 0,0 до этой точки. Так удобно рассчитывать направление из любой точки в любу точку вычитанием одной точки из другой.
А вот с точкой слегка сложнее. Нужно определить пересекаются они или нет.Потом определить параллельны они или нет. И если они не параллельны, то построить уравнения прямых по точкам концов отрезка и решить полученную систему уравнений.
На Java заметил 2 ошибки, которые лучше исправить. 1. Сравнение начальной точки и конечной лучше делать не в методе rangeIntersectoin, а в конструкторе Segment. Если так сделать, то точки отрезков можно записывать в любой последовательности. 2. Скорее исключение, в методе boundingBox нужно прописать 2 if, которые сравнивают точки B и C и A и D, если они равны, то возвращать true. Это будет проверять, является ли конец одного отрезка началом другого. У меня это выглядит так = if ((ab.getB().getX() == a1b1.getA().getX()) && ((ab.getB().getY() == a1b1.getA().getY()))) return true; if ((ab.getA().getX() == a1b1.getB().getX()) && ((ab.getA().getY() == a1b1.getB().getY()))) return true; А так, огромное спасибо за видео, сам бы никода не додумался до этого способа!
Вопрос: Для псевдоскалярного произведения векторов нужно ранжирование X - ов и Y-ов для определения начала векторов или это только нужно для определения пересечения проекций векторов, а при псевдоскалярном произведении используются координаты точек как есть?
Для псевдоскалярного произведения используют компоненты вектора. ru.wikipedia.org/wiki/%D0%9F%D1%81%D0%B5%D0%B2%D0%B4%D0%BE%D1%81%D0%BA%D0%B0%D0%BB%D1%8F%D1%80%D0%BD%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B8%D0%B7%D0%B2%D0%B5%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5
@@oleksandrtsymbaliuk Я понимаю, компонента это по сути проекция на оси...т е. началом вектора в любом случае будет меньшая координата?(тут вопрос это) по оси Х, а компонента соответственно (Х2 - Х1). И по Y так же. Мы же можем обходить точки векторами как с право налево(против часовой) так и наоборот. Или же компонента в любом случае из большего значения по оси меньшее вычитаем, даже если отрицательные координаты. Ведь по Х оси например имеем координаты: ( -7 < -2 ), по оси получим компоненту +5 (-2 - (-7) = +5). Решаю задачу, для определения пересечения точек А,В,С. Причем конец вектора AB это начало вектора BC, и соответственно конец BC, это начало вектора CA. Через систему линейных уравнений решил и точки пересечения нашел. Но там при колинеарности(которой тут нет исходя из визуала даже) "пробел" в определении пересечения получается, хоть он и как исключение -- решение о не пересечении. Как мне в этом случае с векторами доказать что есть пересечение?
В этом алгоритме все равно какую точку отрезка вы выберите (вы же из нее строите все три вектора она и будет началом). Так, что выбор точки, порядок обхода и прочее в этом алгоритме не влияет на результат. Просто первый раз вы берете любую точку на конце отрезка AB, второй раз любую точку на конце отрезка CD в качестве начала для трех векторов. Вопрос о коллинеарных отрезках рассматривался в видео лекции, если псевдоскаляроное произведение равно 0, то они коллинеарны, а уж из пересечения проекций понимаете пересекаються или нет, а дальше просто берете конечную точку одного отрезка и из уравнения прямой узнаете лежит ли она на другом.
Большое спасибо, именно то, что искал :) Очень понятно
На питоне небольшая опечатка в коде. Строка 71. Вместо vector_cb указан vector_cd. VS подсветил неиспользуемую переменную vector_cb на 66 строке.
Огромное спасибо за это видео!
Использовал раньше другой алгоритм. Он начал давать мне пересечение в случае, когда отрезки находились на одной прямой. Вы меня выручили.
Спасибо. Поправил в примерах кода.
спасибо тебе! теперь я смогу делать коллизию!
+ за тем же полез, тема имба, а если еще подучить линии пересечения плоскостей, и пересечение обьëмов то можно уже интересные коллизии выяснять.
типа взмах меча между кадрам с помощью вычисления пересечения плоскости с обьектом, чтобы между кадрами меч не проскакивал через обьект и регистрировал нормально его.
По-моему проще решить систему линейных уравнений =).
1) Прямая AB:
x = Ax*(1-t1)+Bx*t1;
y = Ay*(1-t1)+By*t1;
2) прямая CD:
x = Cx*(1-t2)+Dx*t2;
y = Cy*(1-t2)+Dy*t2;
Имеем на входе 8 координат, а на выходе получим два числа - t1 и t2.
Если оба лежат в промежутке [0;1], значит отрезки пересекаются.
Плюс мы ещё и сможет сразу найти ТОЧКУ пересечения, а не только
сам факт пересечения.
Единственный минус - если отрезки лежат на одной прямой, то мы получим деление на ноль =(.
Но эту ошибку можно сразу расценить как тот факт, что они лежат на одной прямой. И далее
легко понять пересекаются они или нет сравнив координаты.
Добрый день. Спасибо за проявленный интерес. Предложенное вами решение действительно хорошо себя покажет в математике, но с точки зрения вычислительной геометрии оно уже не так хорошо. Как вы верно заметили для решения системы уравнений нужно использовать деление (и не один раз), а это медленная операция на ПК. А вот решение на основе псевдоскалярного произведения только умножение (быстро) и вычитание (очень быстро). Также огорчает необходимость отдельной обработки отрезков на одной прямой. И что еще хуже из за ограничения машинного представления вещественного числа, отрезки с очень близким углом наклона в вашем алгоритме будут считаться лежащими на одной прямой (разница различимых вещественных чисел, легко становиться не различимой от нуля). Хотя как вы верно заметили ваш алгоритм позволяет найти еще точку пересечения, но в ряде задач это не нужно. Это видео больше о таких задачах :).
@@oleksandrtsymbaliuk Спасибо за развёрнутый ответ. Действительно в ряде случаев достаточно лишь факта пересечения. На ум приходит необходимость проверки лежит ли точка внутри фигуры или нет. Можно проверить лишь факты пересечения какого-либо луча выпущенного из данной точки со сторонами фигуры. Если кол-во пересечений чётное, значит мы вне фигуры. Если нечётное - значит внутри. Единственное опять-таки есть сложность. Если луч проходит строго через вершину, то результат может быть неверным. Поэтому неплохо бы отличать такой случай пересечения от других. Если я верно понял, то в вашем примере в такой ситуации одно из псевдоскалярных произведений будет равно нулю?
Ну если фигура более менее правильный многоугольник то факт попадания точки лучше опять же проверять с помощью псевдоскалярного произведения. Исключительных ситуаций типа попадание в вершину или на сторону опять же не будет. А вот если фигура что то типа эллипса то да тут прийдеться думать. Ну или в конце концов просто использовать выметание которое работает почти всегда но сложное :)
@@oleksandrtsymbaliuk Про эллипс сложно =). Нет, я имел ввиду произвольный многоугольник, не обязательно выпуклый (иначе совсем просто).
Единственное у меня вопрос: если я ищу пересечение через уравнения, то для луча (полупрямой) мне достаточно снять ограничение для t1 или t2 (чтобы он мог быть >1 или
@@oleksandrtsymbaliuk А хотя я понял =). Сглупил. Достаточно просто потребовать разных знаков для точек отрезка, а для второй пары векторов это требование убрать. Это значит что отрезок пересёк ПРЯМУЮ. Точнее нас устроит два случая: если знаки разные и если они оба либо положительные, либо отрицательные (в зависимости от направления луча). Прохождение же луча через вершину означает, что одно из произведений (первых) будет равно нулю. Такие ситуации лучше обрабатывать отдельно в зависимости от задачи.
Правильней, наверное, было бы в структуре Вектор хранить одну точку. Направление от 0,0 до этой точки. Так удобно рассчитывать направление из любой точки в любу точку вычитанием одной точки из другой.
А как можно получить саму точку пересечения на Java?
А вот с точкой слегка сложнее. Нужно определить пересекаются они или нет.Потом определить параллельны они или нет. И если они не параллельны, то построить уравнения прямых по точкам концов отрезка и решить полученную систему уравнений.
@@oleksandrtsymbaliuk сделаете видео с пояснением? 🙏
На Java заметил 2 ошибки, которые лучше исправить. 1. Сравнение начальной точки и конечной лучше делать не в методе rangeIntersectoin, а в конструкторе Segment. Если так сделать, то точки отрезков можно записывать в любой последовательности. 2. Скорее исключение, в методе boundingBox нужно прописать 2 if, которые сравнивают точки B и C и A и D, если они равны, то возвращать true. Это будет проверять, является ли конец одного отрезка началом другого. У меня это выглядит так =
if ((ab.getB().getX() == a1b1.getA().getX()) && ((ab.getB().getY() == a1b1.getA().getY()))) return true;
if ((ab.getA().getX() == a1b1.getB().getX()) && ((ab.getA().getY() == a1b1.getB().getY()))) return true;
А так, огромное спасибо за видео, сам бы никода не додумался до этого способа!
А почему в учебниках так: формула для вычисления скалярного произведения имеет вид: АВ = a x * bx + a y * b y. А в вашей формуле минус?
В лекции используется псевдоскалярное произведение, которое отличается от скалярного. Вы приводите формулу для обычного скалярного произведения.
Вопрос: Для псевдоскалярного произведения векторов нужно ранжирование X - ов и Y-ов для определения начала векторов или это только нужно для определения пересечения проекций векторов, а при псевдоскалярном произведении используются координаты точек как есть?
Для псевдоскалярного произведения используют компоненты вектора. ru.wikipedia.org/wiki/%D0%9F%D1%81%D0%B5%D0%B2%D0%B4%D0%BE%D1%81%D0%BA%D0%B0%D0%BB%D1%8F%D1%80%D0%BD%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B8%D0%B7%D0%B2%D0%B5%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5
@@oleksandrtsymbaliuk
Я понимаю, компонента это по сути проекция на оси...т е. началом вектора в любом случае будет меньшая координата?(тут вопрос это) по оси Х, а компонента соответственно (Х2 - Х1). И по Y так же.
Мы же можем обходить точки векторами как с право налево(против часовой) так и наоборот. Или же компонента в любом случае из большего значения по оси меньшее вычитаем, даже если отрицательные координаты. Ведь по Х оси например имеем координаты: ( -7 < -2 ), по оси получим компоненту +5 (-2 - (-7) = +5).
Решаю задачу, для определения пересечения точек А,В,С. Причем конец вектора AB это начало вектора BC, и соответственно конец BC, это начало вектора CA. Через систему линейных уравнений решил и точки пересечения нашел. Но там при колинеарности(которой тут нет исходя из визуала даже) "пробел" в определении пересечения получается, хоть он и как исключение -- решение о не пересечении. Как мне в этом случае с векторами доказать что есть пересечение?
В этом алгоритме все равно какую точку отрезка вы выберите (вы же из нее строите все три вектора она и будет началом). Так, что выбор точки, порядок обхода и прочее в этом алгоритме не влияет на результат. Просто первый раз вы берете любую точку на конце отрезка AB, второй раз любую точку на конце отрезка CD в качестве начала для трех векторов. Вопрос о коллинеарных отрезках рассматривался в видео лекции, если псевдоскаляроное произведение равно 0, то они коллинеарны, а уж из пересечения проекций понимаете пересекаються или нет, а дальше просто берете конечную точку одного отрезка и из уравнения прямой узнаете лежит ли она на другом.