← →
Yuraz
(2003-07-16 13:58)
[0]
Вопрос наверное относится больше к математике, но всё же, есть 2 фигуры, с 3 и 4 вершинами, соответственно, т.е. треугольник и квадрат. Имеют координаты x,y у каждой вершины. Местоположение фигур может менятся, т.е. x,y, форма не меняется.
Я генерирую, случайно, вручную, положение фигуры в пространстве, и хотелось бы узнать, перекрывает ли она вторую фигуру. Т.е. тут могут быть варианты, или True/False (пересекает, не пересекает), или мы можем узнать кроме этого ещё и координаты точек пересечения. Не знаю, может быть вопрос слишком сложный, сам не могу выйти на нужную литературу, но в школе точно это не проходили 
Буду рад любому ответу.
PS. Спасибо MBo за вчерашний ответ о повороте фигуры, я даже не ожидал такаго грамотного ответа на вопрос 
← →
Digitman
(2003-07-16 14:01)
[1]
> в школе точно это не проходили
да ну ?! что, и решение системы двух линейных уравнений не проходили ?! ни одним из известных способов ?!
мда … тили-тили, трали-вали…
← →
BOA_KAA
(2003-07-16 14:15)
[2]
http://algolist.manual.ru/maths/geom/
← →
Andrey007
(2003-07-16 14:16)
[3]
Надо делать два вложенных цикла — внешний по координатам одной фигуры, вложенный — по координатам другой фигуры. В цикле брать отрезок одной фигуры и смотреть его пересечение с отрезком другой фигуры. Алгоритм подходит для любых n-угольников.
← →
default
(2003-07-16 14:18)
[4]
можешь проверять пересечение линий — сторон этих фигур
← →
Юрий Федоров
(2003-07-16 14:18)
[5]
Можно средствами API —
создать два региона и проверить, пересекаются или нет
← →
Vlad Oshin
(2003-07-16 14:18)
[6]
просто рассуждение, поправте знатоки
а если Винды заставить думать? Есть же там регионы, вот и создать 2 региона, и стандартными функциями проверить?
(я понимаю, что геометрически лучше, но просто, возможно ведь, когда думать лень? или нет?)
← →
Vlad Oshin
(2003-07-16 14:19)
[7]
> Юрий Федоров ©
Простой алгоритм определения пересечения двух отрезков
Время на прочтение
4 мин
Количество просмотров 204K
Введение
В былые времена я увлекался компьютерной графикой, как 2х так и 3х мерной, в том числе математическими визуализациями. Что называется just for fun, будучи студентом, написал программу визуализирующую N-мерные фигуры, вращающиеся в любых измерениях, хотя практически меня хватило только на определение точек для 4-D гиперкуба. Но это только присказка. Любовь к геометрии осталась у меня с тех пор и по сей день, и я до сих пор люблю решать интересные задачи интересными способами.
Одна из таких задач попалась мне в 2010 году. Сама задача достаточно тривиальна: необходимо найти, пересекаются ли два 2-D отрезка, и если пересекаются — найти точку их пересечения. Более интересно решение, которое, я считаю, получилось достаточно элегантным, и которое я хочу предложить на суд читателя. На оригинальность алгоритма не претендую (хотя и хотелось бы), но в сети подобных решений я найти не смог.
Задача
Даны два отрезка, каждый из которых задан двумя точками: (v11, v12), (v21, v22). Необходимо определить, пересекаются ли они, и если пересекаются, найти точку их пересечения.
Решение
Для начала необходимо определить, пересекаются ли отрезки. Необходимое и достаточное условие пересечения, которое должно быть соблюдено для обоих отрезков следующее: конечные точки одного из отрезков должны лежать в разных полуплоскостях, если разделить плоскость линией, на которой лежит второй из отрезков. Продемонстрируем это рисунком.
На левом рисунке (1) показаны два отрезка, для обоих из которых условие соблюдено, и отрезки пересекаются. На правом (2) рисунке условие соблюдено для отрезка b, но для отрезка a оно не соблюдается, соответственно отрезки не пересекаются.
Может показаться, что определить, с какой стороны от линии лежит точка — нетривиальная задача, но у страха глаза велики, и всё не так сложно. Мы знаем, что векторное умножение двух векторов даёт нам третий вектор, направление которого зависит от того, положительный или отрицательный угол между первым и вторым вектором, соответственно такая операция антикоммутативна. А так как все вектора лежат на плоскости X-Y, то их векторное произведение (которое обязано быть перпендикулярным перемножаемым векторам) будет иметь ненулевой только компоненту Z, соответственно и отличие произведений векторов будет только в этой компоненте. Причем при изменении порядка перемножения векторов (читай: угла между перемножаемыми векторами) состоять оно будет исключительно в изменении знака этой компоненты.
Поэтому мы можем умножить попарно-векторно вектор разделяющего отрезка на векторы направленные от начала разделяющего отрезка к обеим точкам проверяемого отрезка.
Если компоненты Z обоих произведений будет иметь различный знак, значит один из углов меньше 0 но больше -180, а второй больше 0 и меньше 180, соответственно точки лежат по разные стороны от прямой. Если компоненты Z обоих произведений имеют одинаковый знак, следовательно и лежат они по одну сторону от прямой.
Если один из компонент Z является нулём, значит мы имеем пограничный случай, когда точка лежит аккурат на проверяемой прямой. Оставим пользователю определять, хочет ли он считать это пересечением.
Затем нам необходимо повторить операцию для другого отрезка и прямой, и убедиться в том, что расположение его конечных точек также удовлетворяет условию.
Итак, если всё хорошо и оба отрезка удовлетворяют условию, значит пересечение существует. Давайте найдём его, и в этом нам также поможет векторное произведение.
Так как в векторном произведении мы имеем ненулевой лишь компоненту Z, то его модуль (длина вектора) будет численно равен именно этой компоненте. Давайте посмотрим, как найти точку пересечения.
Длина векторного произведения векторов a и b (как мы выяснили, численно равная его компоненте Z) равна произведению модулей этих векторов на синус угла между ними (|a| |b| sin(ab)). Соответственно, для конфигурации на рисунке мы имеем следующее: |AB x AC| = |AB||AC|sin(α), и |AB x AD| = |AB||AD| sin(β). |AC|sin(α) является перпендикуляром, опущенным из точки C на отрезок AB, а |AD|sin(β) является перпендикуляром, опущенным из точки D на отрезок AB (катетом ADD’). Так как углы γ и δ — вертикальные углы, то они равны, а значит треугольники PCC’ и PDD’ подобны, а соответственно и длины всех их сторон пропорциональны в равном отношении.
Имея Z1 (AB x AC, а значит |AB||AC|sin(α) ) и Z2 (AB x AD, а значит |AB||AD|sin(β) ), мы можем рассчитать CC’/DD’ (которая будет равна Z1/Z2), а также зная что CC’/DD’ = CP/DP легко можно высчитать местоположение точки P. Лично я делаю это следующим образом:
Px = Cx + (Dx-Cx)*|Z1|/|Z2-Z1|;
Py = Cy + (Dy-Cy)*|Z1|/|Z2-Z1|;
Вот и все. Мне кажется что это действительно очень просто, и элегантно. В заключение хочу привести код функции, реализующий данный алгоритм. В функции использован самодельный шаблон vector<typename, int>, который является шаблоном вектора размерностью int с компонентами типа typename. Желающие легко могут подогнать функцию к своим типам векторов.
1 template<typename T>
2 bool are_crossing(vector<T, 2> const &v11, vector<T, 2> const &v12, vector<T, 2> const &v21, vector<T, 2> const &v22, vector<T, 2> *crossing)
3 {
4 vector<T, 3> cut1(v12-v11), cut2(v22-v21);
5 vector<T, 3> prod1, prod2;
6
7 prod1 = cross(cut1 * (v21-v11));
8 prod2 = cross(cut1 * (v22-v11));
9
10 if(sign(prod1[Z]) == sign(prod2[Z]) || (prod1[Z] == 0) || (prod2[Z] == 0)) // Отсекаем также и пограничные случаи
11 return false;
12
13 prod1 = cross(cut2 * (v11-v21));
14 prod2 = cross(cut2 * (v12-v21));
15
16 if(sign(prod1[Z]) == sign(prod2[Z]) || (prod1[Z] == 0) || (prod2[Z] == 0)) // Отсекаем также и пограничные случаи
17 return false;
18
19 if(crossing) { // Проверяем, надо ли определять место пересечения
20 (*crossing)[X] = v11[X] + cut1[X]*fabs(prod1[Z])/fabs(prod2[Z]-prod1[Z]);
21 (*crossing)[Y] = v11[Y] + cut1[Y]*fabs(prod1[Z])/fabs(prod2[Z]-prod1[Z]);
22 }
23
24 return true;
25 }
Точки пересечения треугольников определяются в следующем порядке:
1.) Согласно заданию строятся точки по координатам.
2.) Теперь важным шагом является определение плоскости относительно которой будем искать точки пересечения треугольников.
Вы можете сказать: «можно найти точки относительно плоскости АВС», но нет. Почему!? Я объясню, посмотрев на рисунок, расположенный внизу, можно увидеть что треугольник D2E2F2, а точнее две стороны пересекают треугольник А2В2С2 в четырех точках, соответственно используем треугольник D2E2F2,как опорную плоскость.
- Сторона D2E2 пересекает плоскость А2В2С2 в точках 12 и 22, эти точки переносим на нижнее изображение: на стороны относительно которых они были найдены и обозначаем 11 и 21.
- Точки 11 и 21 соединяются.
- Прямая 1121 пересекает сторону D1E1 в точке, обозначим Р1 (первая точка найдена).
3.) Сторона E2F2 пересекает стороны B2C2 и A2C2 в точках 42 и 32. Опускаем их на нижний рисунок и обозначаем 41 и 31.
4.) Соединяются точки 31 и 41.
5.) Продливается прямая 3141 до пересечения с отрезком E1F1. В месте пересечения ставим точку и обозначаем Н.
6.) Точки P1 и H соединяются. Полученная прямая P1H пересекает отрезок А2С2 в точке K1 (найдена вторая точка).
7.) Переносятся точки P1 и K1, расположенные на отрезках D1E1 и E1F1, на отрезки D2E2 и E2F2. И обозначаются P2 и K2.
8.) Соединяются P2 и K2.
9.) А теперь главный момент: указать видимые и невидимые стороны.
Посмотрите на рисунок снизу. На нем точки D, F, B, C и E находятся в двух проекциях «свободно», но не точка A. Соответственно, относительно ее и необходимо начинать чертить линии.
Пример выполненной работы на эту тему смотрите здесь.
Немного добавлю по этой статье: «Точки пересечения треугольников»
По своему опыту скажу: «чтобы начертить подобный чертеж, необходимо обладать пространственным воображением» и понимать, относительно какой плоскости отталкиваться для решения подобной задачи. Но благодаря этой статьи надеюсь у Вас получится разобраться с темой: пересечение плоских фигур.
Просмотрели 401
Как найти площадь пересечения двух прямоугольников?
Есть два прямоугольника стороны, которых параллельны осям и они пересекаются. Нам известно:
(x1,y1) — левая нижняя точка первого прямоугольника
(x2,y2) — правая верхняя точка первого прямоугольника
(x3,y3) — левая нижняя точка второго прямоугольника
(x4,y4) — правая верхняя точка второго прямоугольника
И нужно найти площадь их пересечения. Но пересекатся они могут с разних сторон.
Хотя вопрос и простой, оставлю в качестве шпаргалки-сниппета:
Исходя из вопроса, полагаю, что координаты растут из нижнего левого угла (если же Y растет сверху вниз, то необходимо внести соответствующие поправки).
Идея простая, иллюстрируется на картинке (показано как определяется ширина общего прямоугольника, высота определяется аналогично):
Всё ещё ищете ответ? Посмотрите другие вопросы с метками c++ математика геометрия прямоугольники или задайте свой вопрос.
Site design / logo © 2022 Stack Exchange Inc; user contributions licensed under cc by-sa. rev 2022.6.10.42345
Нажимая «Принять все файлы cookie», вы соглашаетесь, что Stack Exchange может хранить файлы cookie на вашем устройстве и раскрывать информацию в соответствии с нашей Политикой в отношении файлов cookie.
геометрия — Пересечение прямоугольников
Как вывести общую формулу для построения пересечения прямоугольников? Ведь бывает, что один прямоугольник находится внутри другого или координаты первого прямоугольника по х больше, чем у второго и при этом меньше по у, чем у второго. Как свести разные случаи в один?
задан 30 Май ’17 20:59
1 ответ
Задача для прямоугольников сводится к аналогичной задаче для отрезков. По каждой оси смотрим на пересечения отрезков, а потом берём получившийся прямоугольник (как декартово произведение). Если хотя одно пересечение отрезков окажется пустым, то и пересечение прямоугольников пусто.
По определению, отрезок [a,b] есть множество решений двойного неравенства a<=x<=b. Для двух отрезков имеем систему неравенств a<=x, c<=x, x<=b, x<=d. Она равносильна системе max(a,c)<=x, x<=min(b,d). То есть надо взять максимум левых концов и минимум правых. Получится отрезок [max(a,c),min(b,d)]. Если первое число больше второго, то это пустое множество.
отвечен 30 Май ’17 21:15
@falcao: Я уж сороковой год использую неравенство $%max(a,c)le min(b,d)$% в для проверки пересечения отрезков. Проверять пересечение прямоугольников не приходилось. Это я о программировании.
@EdwardTurJ: я вспомнил по ходу дела, что вопрос о прямоугольниках уже звучал здесь. Там площадь надо было найти. Наверное, на практике такое редко требуется, а в тренировочных задачах частенько встречается.
Получить точки пересечения из 2 прямоугольников
Допустим, у нас есть два прямоугольника, определенные их нижним левым и верхним правым углами. Например: rect1 (x1, y1) (x2, y2) а также rect2 (x3, y3) (x4, y4).
Я пытаюсь найти координаты (внизу слева и вверху справа) пересеченного прямоугольника.
Любые идеи, алгоритм, псевдокод, будет принята с благодарностью.
постскриптум Я нашел похожие вопросы, но они проверяют, только если 2 прямоугольника пересекаются.
Решение
Если входные прямоугольники нормализованы, то есть вы уже знаете, что x1 < x2 , y1 < y2 (и то же самое для второго прямоугольника), тогда все, что вам нужно сделать, это рассчитать
и это даст вам ваше пересечение в виде прямоугольника (x5, y5)-(x6, y6) , Если исходные прямоугольники не пересекаются, результатом будет «вырожденный» прямоугольник (с x5 >= x6 и / или y5 >= y6 ), который вы можете легко проверить.
Постскриптум Как обычно, мелкие детали будут зависеть от того, нужно ли учитывать трогательный прямоугольники как пересекающиеся.
Другие решения
Чтобы найти пересечение, вам нужно сделать несколько простых сравнений точек:
Итак, как мы можем видеть из изображения, если x3, y3 больше или равно x1, y1 и меньше или равно x2, y2, то оно находится внутри первого прямоугольника, аналогично вам нужно будет проверить, попадает ли x4, y4 внутрь диапазон от х1, у1 до х2, у2, а также.
если оба условия оказываются верными, то вы можете быть уверены, что второй прямоугольник полностью охватывается первым. 
Вам нужно будет проверить и обратное, если узнаете, что внутри, что важно для вас.
Также необходимо, чтобы прямоугольники были выровнены по оси, иначе это не будет работать надежно.
Дайте мне знать, если вам нужно больше подробностей, хотя я думаю, что быстрый поиск в Google очень легко раскроет для вас более подробную информацию, но дайте мне знать, и я могу сделать учебник по столкновению с прямоугольником, если хотите.
Более подробно:
Чтобы выяснить, имеют ли прямоугольники пересечения, вы можете проверить координаты их определяющих точек, для наших целей мы будем использовать координаты верхнего левого и нижнего правого углов.
Мы можем использовать класс, чтобы сделать это проще для нас, и для максимального удобства использования кода мы можем использовать 2d Vector и 2d Point:
2dVectorPoint.h
Используемый код адаптирован из Вот чтобы сохранить мои пальцы.
Тогда мы можем использовать это, чтобы легко сравнить:
мы можем определить прямоугольник 1 как имеющий P1 и P2 как его границы и прямоугольник 2 как имеющий P3 и P4 как его границы, давая нам следующее сравнение:
Это вернет истинное значение для любого экземпляра пересечения или для прямоугольника 1, полностью охватывающего прямоугольник 2.
Чтобы проверить только пересечения, просто удалите проверку на равенство (возьмите все = из вышеприведенного уравнения), и вы будете проверять только на пересечения. Если у вас есть пересечение, вы можете использовать линейную алгебру для оценки точных координат.
Скажем, у блока есть радиус X и радиус Y (я знаю, что его нет, но этот термин здесь полезен).
Вы будете иметь:
Теперь, если прямоугольные средние точки находятся дальше, чем сумма их радиусов в соответствующем направлении — они не сталкиваются.
В противном случае они делают — этого намека должно хватить.
Теперь вы должны быть в состоянии выполнить задание.
ОБНОВИТЬ:
Хорошо — давайте решим это для 1D — позже вы решите это для 2D. Посмотрите на этот кусок … искусства
Вы видите 2 сегмента — теперь некоторые расчеты:
Теперь, как проверить, происходит ли столкновение? Как я уже сказал, если сумма «радиусов» меньше расстояния сегментов — столкновения нет:
Теперь ваша задача — вычислить пересечение / общую часть в 1D и 2D. Теперь все зависит от вас (вы можете прочитать ответ Андрея).
Здесь та же самая ситуация, но в 2D — две одномерные ситуации:
Вы можете иметь дело с x а также y Направление отдельно.
Предположим, что x1 <= x3 (первая коробка как минимум так же далеко, как и вторая). Тогда есть совпадение, если и только если x1 <= x3 <= x2 ,
Аналогично предположим y1 <= y3 (первая коробка, по крайней мере, так же далеко, как и вторая). Тогда есть совпадение, если и только если y1 <= y3 <= y2 ,
Если в обоих направлениях перекрытие, то перекрытие прямоугольника. Вы можете найти координаты, отсортировав x а также y координаты и выбрав два средних.
Добрый день!
Есть Теория R-функций. Мне кажеться это наиболее достойное решение. Суть его в том, что имея уравнения всех полигонов, или нужных вам, вы с помощью R-функции можете получить новую функцию, которая у вас будет описывать пересечение, объеденение или отрицание примитивов.
Вот пример:
1. У вас есть круг, уравнение которого в двумерном пространстве имеет вид: f1 = R*R-x*x-y*y >= 0
2. У вас есть плоскость, уравнение которой f2 = x >= 0
Вам нужно найти, пересечение (коньюнкцию).
Составляете такую формулу: f1&f2 = f1 + f2 — sqrt(f1*f1 + f2*f2)
В результате получаете: f3 = f1&f2 = R*R-x*x-y*y + x — sqrt((R*R-x*x-y*y)*(R*R-x*x-y*y) + x*x)
И теперь, если эта функция хотя бы в одной точке больше нуля, то фигуры накладываются.
Подробнее еще можно здесь.
| Комментарий модератора | ||
|
