Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.50/4: Рейтинг темы: голосов - 4, средняя оценка - 4.50
imjonhson
8 / 8 / 7
Регистрация: 02.01.2017
Сообщений: 205
#1

Пересечение двух прямых и проверка на пересечение

16.03.2017, 10:23. Просмотров 752. Ответов 18
Метки нет (Все метки)

Доброго времени суток слизал функцию проверки отсюда:/segments_intersection_checking
на всякий случай у меня она выглядит так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int miarea (point a, point b, point c)
{
     return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
 }
bool miintersect_1 (int a, int b, int c, int d) {
    if (a > b)  std::swap (a, b);
    if (c > d)  std::swap (c, d);
    return std::max(a,c) <= std::min(b,d);
}
 
bool miintersect (point a, point b, point c, point d) {
    return miintersect_1 (a.x, b.x, c.x, d.x)
        && miintersect_1 (a.y, b.y, c.y, d.y)
        && miarea(a,b,c) * miarea(a,b,d) <= 0
        && miarea(c,d,a) * miarea(c,d,b) <= 0;
}
проверяю квадрат(по очереди стороны на пересечение с линией) входные данные:
размер ветора точек области 4
линия разделитель a.x 600 a.y 0 b.x 600 b.y 8000
точка1 х 41 у 1359
точка2 x 41 y 41
точка3 x 1159 y 41
точка4 x 1159 y 1359
выдает true только на одной линии из 4-х , вспоминаю школу, читаю статьи
Шо не так ?? подскажите пож.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.03.2017, 10:23
Ответы с готовыми решениями:

Пересечение прямых
Не могу сделать так,чтобы находил пересечения двух прямых(n штук) и выводил...

Проверить отрезки прямых на пересечение
Мне нужно сделать програму которая будет проверять пересекаются отрезки и...

Пересечение двух окружностей
На плоскости даны две окружности. Требуется проверить, пересекаются ли они. ...

Пересечение двух кругов
Привет. Есть входной файл такого формата: Первый ряд цифр относится к...

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

18
DemolitionMan
129 / 155 / 87
Регистрация: 06.04.2016
Сообщений: 992
16.03.2017, 13:07 #2
Почему там inline во 2-й функции(miintersect_1), если она далеко не inline.

Добавлено через 1 минуту
А, автор убрал у себя этот inline. Тогда вопрос снят.

Добавлено через 34 минуты
Площадь неверно считает. Я проверил на прямоугольном треугольнике:
http://cpp.sh/3d76b
Здесь площадь треугольника должна быть 6, а получилась 12, т.е. в 2 раза больше.
1
imjonhson
8 / 8 / 7
Регистрация: 02.01.2017
Сообщений: 205
16.03.2017, 13:14  [ТС] #3
В самом низу есть сноска по этой функции
Следует отметить, что если исходные координаты точек уже были вещественнозначными, то следует нормировать прямые (т.е. привести их к такому состоянию, что сумма квадратов коэффициентов a и b равна единице), иначе погрешности при сравнении прямых на параллельность и на совпадение могут оказаться слишком большими.
это может быть причиной?
0
DemolitionMan
129 / 155 / 87
Регистрация: 06.04.2016
Сообщений: 992
16.03.2017, 13:30 #4
Не знаю. Муть какая-то. У меня целые координаты. Здесь мути сильно много. Я бы порекомендовал найти более простой, явный, ясный, понятный и наглядный способ. Попробуйте заглянуть в нашу советскую научную литературу, американцы нам вечно какое-то фуфло подсовывают. По-моему нужно взять лист бумаги с ручкой и самому сделать этот алгоритм определения пересечения прямых.
1
imjonhson
8 / 8 / 7
Регистрация: 02.01.2017
Сообщений: 205
16.03.2017, 14:10  [ТС] #5
я не силен в геометрии но по-моему площадь половины квдрата 5х4(прямоугольный треугольник со сторонами 5 и 4) равна 10
Цитата Сообщение от DemolitionMan Посмотреть сообщение
американцы нам вечно какое-то фуфло подсовывают
даже не знаю что сказать.... сайт .ru за что вы его американским называете))

Добавлено через 19 минут
накопал рабочий алгорит причем далеко ходить не надо было......
http://www.cyberforum.ru/post1877381.html

Добавлено через 2 минуты
плохо что в гугле это неподобство раньше встречается и многие пройдутся по моим граблям.

Добавлено через 1 минуту
Цитата Сообщение от DemolitionMan Посмотреть сообщение
По-моему нужно взять лист бумаги с ручкой и самому сделать этот алгоритм определения пересечения прямых.
по моему изобретать велосипед неблагодарное занятие
0
nmcf
6265 / 5575 / 2534
Регистрация: 14.04.2014
Сообщений: 23,468
16.03.2017, 14:36 #6
imjonhson, а второй алгоритм с той страницы проверял?
0
imjonhson
8 / 8 / 7
Регистрация: 02.01.2017
Сообщений: 205
16.03.2017, 14:43  [ТС] #7
нет, и вряд ли буду,уже .....

Добавлено через 3 минуты
мне первого хватило )))) перебрал по запчастям пол программы,даже не приходила мысль в голову что кто-то выложил нерабочий код
0
nmcf
6265 / 5575 / 2534
Регистрация: 14.04.2014
Сообщений: 23,468
16.03.2017, 15:02 #8
Ну а сам алгоритм почему не перебрал?
0
DemolitionMan
129 / 155 / 87
Регистрация: 06.04.2016
Сообщений: 992
16.03.2017, 17:20 #9
Цитата Сообщение от imjonhson Посмотреть сообщение
По-моему изобретать велосипед неблагодарное занятие.
- А учиться благодарное занятие? Впрочем я с Вами согласен - учиться неблагодарное занятие.
А вообще я это сказал для того чтобы Вы поняли суть вещей. Попробуйте прямо сейчас честно сказать уравнения прямой на плоскости. Ну как? Получилось?(И что получилось?) А уравнение прямой на плоскости это y = kx + b, где k - это угловой коэффициент или тангенс.

Добавлено через 1 минуту
А b - это смещение вверх(положительное b) или вниз(отрицательное b) на столько единиц.

Добавлено через 24 минуты
Алгоритм работает, да, я проверил.
1
nmcf
6265 / 5575 / 2534
Регистрация: 14.04.2014
Сообщений: 23,468
16.03.2017, 19:23 #10
DemolitionMan, я тоже проверял - не работает. В чём там хитрость?
0
DemolitionMan
129 / 155 / 87
Регистрация: 06.04.2016
Сообщений: 992
17.03.2017, 01:56 #11
Создаете файл "input.txt". Там точки должны быть в таком формате:
A.x A.y
B.x B.y
C.x C.y
D.x D.y
и потом в файл "ouptut.txt" выводится результат.
0
Fulcrum_013
Заблокирован
17.03.2017, 02:39 #12
Цитата Сообщение от DemolitionMan Посмотреть сообщение
А уравнение прямой на плоскости это y = kx + b, где k - это угловой коэффициент или тангенс.
Уравнение прямой на плоскости - ax+by+c=0. И в общем случае стоит пользовать именно это уравнение т.к. у вертикальной прямой k бесконечность. Для задач пересечения очень часто пользуется уравнение в параметрическом виде x=at+c; y=bt+d.
Цитата Сообщение от imjonhson Посмотреть сообщение
проверяю квадрат(по очереди стороны на пересечение с линией) входные данные:
Уточните плиз у вас задача пересечения четырехугольника с прямой или с отрезком? это разные задачи и решаются они по разному.
1
DemolitionMan
129 / 155 / 87
Регистрация: 06.04.2016
Сообщений: 992
17.03.2017, 03:10 #13
Удалено.
0
imjonhson
8 / 8 / 7
Регистрация: 02.01.2017
Сообщений: 205
17.03.2017, 04:57  [ТС] #14
Цитата Сообщение от Fulcrum_013 Посмотреть сообщение
Уточните плиз у вас задача пересечения четырехугольника с прямой или с отрезком?
Хороший вопрос)....
У меня ограниченная система координат, и все точки многоугольников принадлежат этой системе координат, в принципе без разницы как решать для результата входные данные могут быть и отрезком и прямой,тут уже вопрос в ресурсозатратах на выполнение алгоритма,стоит выбрать менее ресурсозатратный.
Цитата Сообщение от nmcf Посмотреть сообщение
Ну а сам алгоритм почему не перебрал?
Цитата Сообщение от imjonhson Посмотреть сообщение
даже не приходила мысль в голову что кто-то выложил нерабочий код
Добавлено через 1 час 31 минуту
если кому-то пригодится, с дельфи переделал, и немного точности добавил
нахождение точки пересечения
C++
1
2
3
4
5
6
7
8
9
10
11
12
point getPointOfIntersection(point p1, point p2, point p3,point p4)
{
  int d=(p1.x - p2.x) * (p4.y - p3.y) - (p1.y - p2.y) * (p4.x - p3.x);
  int da=(p1.x - p3.x) * (p4.y - p3.y) - (p1.y - p3.y) * (p4.x - p3.x);
  int db=(p1.x - p2.x) * (p1.y - p3.y) - (p1.y - p2.y) * (p1.x - p3.x);
  double ta=(double)da/(double)d;
  double tb=(double)db/(double)d;
  point p;
  p.x= (int)rint(((double)p1.x+ta*(double)(p2.x-p1.x)));
  p.y= (int)rint(((double)p1.y+ta*(double)(p2.y-p1.y)));
  return p;
}
Добавлено через 1 минуту
хотя опять-же первое что попадается в поиске:
C++
1
2
3
4
5
6
7
point cross(point a,point b,point c,point d) //точки a и b концы первого отрезка  c и d второго
{
    point T;
    T.x=-((a.x*b.y-b.x*a.y)*(d.x-c.x)-(c.x*d.y-d.x*c.y)*(b.x-a.x))/((a.y-b.y)*(d.x-c.x)-(c.y-d.y)*(b.x-a.x));
    T.y=((c.y-d.y)*(-T.x)-(c.x*d.y-d.x*c.y))/(d.x-c.x);
    return T;
}
Добавлено через 38 секунд
не всегда выдает корректные результаты
0
Fulcrum_013
Заблокирован
17.03.2017, 07:42 #15
Цитата Сообщение от imjonhson Посмотреть сообщение
в принципе без разницы как решать для результата входные данные могут быть и отрезком и прямой
В принципе разница огромна. Для отрезка проверяется пересечение каждого отрезка многоугольника с заданным отрезком. Делается это просто. Вычисляются неявные уравнения сторон и самого отрезка. потом для каждой стороны проверяется пересечение с отрезком. В уравнение отрезка подставляются концы стороны. Если результаты имеют разный знак то в уравнение стороны подставляются концы отрезка. Если знак тоже разный то есть пересечение.
Для прямой/луча же такой метод слишком тормознутый есть и гораздо более быстрые но при этом математически намного сложнее для понимания и выдвигают условия выпуклости многоугольника(невыпуклые должны быть разделены на набор выпуклых и для ускорения проверки должен быть построен охватывающий выпуклый).
0
imjonhson
8 / 8 / 7
Регистрация: 02.01.2017
Сообщений: 205
17.03.2017, 09:03  [ТС] #16
Цитата Сообщение от Fulcrum_013 Посмотреть сообщение
Для прямой/луча
это уже интересно, один нюанс у меня в любом случае один отрезок, а вторая линия разделитель может быть и прямой и отрезком, в таком случае можно ли выиграть по скорости?
0
Fulcrum_013
Заблокирован
17.03.2017, 09:31 #17
Цитата Сообщение от imjonhson Посмотреть сообщение
это уже интересно, один нюанс у меня в любом случае один отрезок, а вторая линия разделитель может быть и прямой и отрезком, в таком случае можно ли выиграть по скорости?
При выпуклых или предобработанных полигонах можно. Суть в том что в поиске пересечений гораздо важнее быстро определять отсутствие пересечения чем находить само пересечение. С взаимной подстановкой координат как для отрезка для определения факта отсутствия пересечения нужно проверить все отрезки. С прямой и конвексом отсутствие пересечения может быть определено гораздо раньше даже при первом шаге если повезет. При этом для всех параллельных сторон можно определять пересечение фактически один раз. Суть в чем для очередной стороны ищется пересечение прямой/луча и прямой содержащей сторону. если луч пересекает ее в направлении входа в многоугольник то считается то он в него вошел, если в направлении выхода - то считается что вышел. НАправление определяется по направлению нормали. Дальше все просто - первый выход - пересечения нет, Если вошел во все пересечение есть, минимальное положительное t луча при этом есть точка входа.

Добавлено через 6 минут
Кстати точно так же работает для проверки пересечения выпуклого многогранника и луча в 3D, только ищутся пересечения не с прямыми содержащими стороны, а с плоскостями содержащими грани

Добавлено через 5 минут
Цитата Сообщение от imjonhson Посмотреть сообщение
это уже интересно, один нюанс у меня в любом случае один отрезок, а вторая линия разделитель может быть и прямой и отрезком, в таком случае можно ли выиграть по скорости?
Да кстати, если у вас только прямоугольник выровненный по осям как в примере исходных данных, то для этого случая существуют специальные алгоритмы быстрого отсечения отрезка:
http://algolist.manual.ru/graphics/clip_seg.php
1
imjonhson
8 / 8 / 7
Регистрация: 02.01.2017
Сообщений: 205
17.03.2017, 09:56  [ТС] #18
Цитата Сообщение от Fulcrum_013 Посмотреть сообщение
Да кстати, если у вас только прямоугольник выровненный
к сожалению это только цветочки, многоугольники выпуклые, но в перспективе еще и с дугами
0
Fulcrum_013
Заблокирован
17.03.2017, 10:05 #19
Цитата Сообщение от imjonhson Посмотреть сообщение
но в перспективе еще и с дугами
Дуга это такая же прямая только в искривленном пространстве. Кстати поверка на пересечение прямой с дугой тоже тривиальна только уравнение квадратное. И принцип входит-выходит тоже работает только с некоторыми финтами ушами. В принципе для упрощения можно продлить стороны касательные к дуге до пересечения и если пересечение найдено в продленных частях тогда уже определять пересекает оно или нет дугу.
1
17.03.2017, 10:05
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.03.2017, 10:05

Пересечение двух многоугольников
Имеются два многоугольника, например два пятиугольника, координаты заданны...

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

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


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
19
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru