Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
imjonhson
8 / 8 / 5
Регистрация: 02.01.2017
Сообщений: 205
#1

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

16.03.2017, 10:23. Просмотров 680. Ответов 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
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Пересечение двух прямых и проверка на пересечение (C++):

Пересечение прямых - C++
Не могу сделать так,чтобы находил пересечения двух прямых(n штук) и выводил координаты пересечении. Вот что вышло. #include &quot;stdafx.h&quot; ...

Проверить отрезки прямых на пересечение - C++
Мне нужно сделать програму которая будет проверять пересекаются отрезки и если пересекаются то где? НО я не знаю формулу как это...

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

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

Пересечение двух кругов - C++
Привет. Есть входной файл такого формата: Первый ряд цифр относится к первому кругу, 1 - координата по х, 1 - координата по y, 1...

Пересечение двух окружностей - C++
На плоскости даны две окружности. Требуется проверить, пересекаются ли они. Входные данные Входной файл INPUT.TXT состоит из двух...

18
DemolitionMan
99 / 155 / 47
Регистрация: 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 / 5
Регистрация: 02.01.2017
Сообщений: 205
16.03.2017, 13:14  [ТС] #3
В самом низу есть сноска по этой функции
Следует отметить, что если исходные координаты точек уже были вещественнозначными, то следует нормировать прямые (т.е. привести их к такому состоянию, что сумма квадратов коэффициентов a и b равна единице), иначе погрешности при сравнении прямых на параллельность и на совпадение могут оказаться слишком большими.
это может быть причиной?
0
DemolitionMan
99 / 155 / 47
Регистрация: 06.04.2016
Сообщений: 992
16.03.2017, 13:30 #4
Не знаю. Муть какая-то. У меня целые координаты. Здесь мути сильно много. Я бы порекомендовал найти более простой, явный, ясный, понятный и наглядный способ. Попробуйте заглянуть в нашу советскую научную литературу, американцы нам вечно какое-то фуфло подсовывают. По-моему нужно взять лист бумаги с ручкой и самому сделать этот алгоритм определения пересечения прямых.
1
imjonhson
8 / 8 / 5
Регистрация: 02.01.2017
Сообщений: 205
16.03.2017, 14:10  [ТС] #5
я не силен в геометрии но по-моему площадь половины квдрата 5х4(прямоугольный треугольник со сторонами 5 и 4) равна 10
Цитата Сообщение от DemolitionMan Посмотреть сообщение
американцы нам вечно какое-то фуфло подсовывают
даже не знаю что сказать.... сайт .ru за что вы его американским называете))

Добавлено через 19 минут
накопал рабочий алгорит причем далеко ходить не надо было......
Пересечение отрезков.

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

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

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

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

Добавлено через 24 минуты
Алгоритм работает, да, я проверил.
1
nmcf
6198 / 5509 / 1929
Регистрация: 14.04.2014
Сообщений: 23,131
16.03.2017, 19:23 #10
DemolitionMan, я тоже проверял - не работает. В чём там хитрость?
0
DemolitionMan
99 / 155 / 47
Регистрация: 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
99 / 155 / 47
Регистрация: 06.04.2016
Сообщений: 992
17.03.2017, 03:10 #13
Удалено.
0
imjonhson
8 / 8 / 5
Регистрация: 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
17.03.2017, 07:42
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.03.2017, 07:42
Привет! Вот еще темы с ответами:

Задача на пересечение двух окружностей - C++
Всем привет! Прошу вашей помощи в решении задачи так как я уже дней пять над ней мучаюсь и все не выходит. Даны две окружности в...

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

Найти пересечение двух массивов - C++
Даны два массива : А и B. Необходимо создать третий массив, в котором нужно собрать:-Общие элементы двух массивов. общие элементы...

Пересечение двух одномерных массивов N размера - C++
Всем привет! Было задание: Испробовал кучу кодов (пересечение с сортировкой, без сортировки, удаление повторяющихся элементов в...


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

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

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