Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 39, средняя оценка - 4.59
Fantom.AS
2 / 1 / 2
Регистрация: 17.11.2010
Сообщений: 121
#1

Пересечение двух многоугольников - C++

30.10.2011, 14:53. Просмотров 5871. Ответов 10
Метки нет (Все метки)

Имеются два многоугольника, например два пятиугольника, координаты заданны массивом объектов класса точка.
Надо определить, пересекаются ли они?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.10.2011, 14:53
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Пересечение двух многоугольников (C++):

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

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

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

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

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

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

10
Mиxaил
534 / 439 / 162
Регистрация: 10.12.2009
Сообщений: 1,857
30.10.2011, 15:20 #2
Каждая сторона многоугольника - отрезок, следовательно, можно задать уравнение прямой, проходящей через концы этого отрезка. Имея уравнения двух прямых ( двух сторон разных многоугольников ), можно проверить, пересекаются ли прямые на плоскости. Решаем систему и находим точки пересечения.
А так как Вам нужно просто выяснить, пересекаются ли они, то достаточно просто написать условие, например, похожее на это:
(((x1<=x)and(x2>=x)and(x3<=x)and(x4 >=x))or((y1<=y)and(y2>=y)and(y3<=y) and(y4>=y)))
0
Fantom.AS
2 / 1 / 2
Регистрация: 17.11.2010
Сообщений: 121
30.10.2011, 15:24  [ТС] #3
Цитата Сообщение от Mиxaил Посмотреть сообщение
А так как Вам нужно просто выяснить, пересекаются ли они, то достаточно просто написать условие, например, похожее на это:
(((x1<=x)and(x2>=x)and(x3<=x)and(x4 >=x))or((y1<=y)and(y2>=y)and(y3<=y) and(y4>=y)))
Можете пояснить данное условие?

Добавлено через 1 минуту
И если решать систему, то как?
и каким образом хранить уравнения прямой ? в виде массива?
0
Mиxaил
534 / 439 / 162
Регистрация: 10.12.2009
Сообщений: 1,857
30.10.2011, 15:28 #4
Нарисуйте два отрезка, которые пресекаются, и придумайте условие пересечения, манипулируя координатами концов двух отрезков.
P.S. Писать долго...
0
Fantom.AS
2 / 1 / 2
Регистрация: 17.11.2010
Сообщений: 121
30.10.2011, 17:16  [ТС] #5
что-то я не могу сделать это в общем случае.... частные случаи разобрал... а вот в общем...
0
Евгений М.
1047 / 986 / 98
Регистрация: 28.02.2010
Сообщений: 2,858
Завершенные тесты: 2
30.10.2011, 20:02 #6
Цитата Сообщение от Fantom.AS Посмотреть сообщение
Можете пояснить данное условие?
http://e-maxx.ru/algo/segments_intersection_checking
1
Fantom.AS
2 / 1 / 2
Регистрация: 17.11.2010
Сообщений: 121
30.10.2011, 20:16  [ТС] #7
Цитата Сообщение от Евгений М. Посмотреть сообщение
Сообщение от Fantom.AS
Можете пояснить данное условие?
Допустим есть два пятиугольника, необходимо определить, пересекаются ли они? Т.е. имеют ли хотя бы одну общую точку
0
regmar
0 / 0 / 0
Регистрация: 18.10.2011
Сообщений: 19
30.10.2011, 20:41 #8
Многоугольники выпуклые?
0
OstapBender
584 / 523 / 75
Регистрация: 22.03.2011
Сообщений: 1,585
30.10.2011, 20:45 #9
многоугольники заданы в 2д или 3д координатах?
0
Евгений М.
1047 / 986 / 98
Регистрация: 28.02.2010
Сообщений: 2,858
Завершенные тесты: 2
30.10.2011, 22:01 #10
Цитата Сообщение от Fantom.AS Посмотреть сообщение
Допустим есть два пятиугольника, необходимо определить, пересекаются ли они? Т.е. имеют ли хотя бы одну общую точку
Берете одну "сторону" у первого многоугольника, и одну "сторону" второго многоугольника. Проверяйте пересекаются ли эти "стороны". И так со всеми остальными "сторонами".
0
Fantom.AS
2 / 1 / 2
Регистрация: 17.11.2010
Сообщений: 121
31.10.2011, 16:27  [ТС] #11
спасибо, это я уже реализовал следующим способом,
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
struct pt {
    int x, y;
};
 
inline int area (pt a, pt b, pt c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
 
inline bool intersect_1 (int a, int b, int c, int d) {
    if (a > b)  swap (a, b);
    if (c > d)  swap (c, d);
    return max(a,c) <= min(b,d);
}
 
bool intersect (pt a, pt b, pt c, pt d) {
    return intersect_1 (a.x, b.x, c.x, d.x)
        && intersect_1 (a.y, b.y, c.y, d.y)
        && area(a,b,c) * area(a,b,d) <= 0
        && area(c,d,a) * area(c,d,b) <= 0;
}
но там не проверки на тот случай, если они имеют только одну общую точку или общую сторону
0
31.10.2011, 16:27
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
31.10.2011, 16:27
Привет! Вот еще темы с решениями:

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

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

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

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


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

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

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