Форум программистов, компьютерный форум CyberForum.ru

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 39, средняя оценка - 4.59
Fantom.AS
2 / 1 / 0
Регистрация: 17.11.2010
Сообщений: 121
#1

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

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

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

C++ Пересечение двух окружностей
Пересечение двух кругов C++
C++ Пересечение двух окружностей
Строка: Добавить в строковый класс функцию, которая создает строку, содержащую пересечение двух строк, то есть общие символы для двух строк. C++
C++ Проверить лежит ли один из многоугольников строго внутри другого и определить площади многоугольников
C++ Найти пересечение двух массивов
Найти пересечение двух прямоугольников C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Mиxaил
531 / 436 / 37
Регистрация: 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)))
Fantom.AS
2 / 1 / 0
Регистрация: 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 минуту
И если решать систему, то как?
и каким образом хранить уравнения прямой ? в виде массива?
Mиxaил
531 / 436 / 37
Регистрация: 10.12.2009
Сообщений: 1,857
30.10.2011, 15:28     Пересечение двух многоугольников #4
Нарисуйте два отрезка, которые пресекаются, и придумайте условие пересечения, манипулируя координатами концов двух отрезков.
P.S. Писать долго...
Fantom.AS
2 / 1 / 0
Регистрация: 17.11.2010
Сообщений: 121
30.10.2011, 17:16  [ТС]     Пересечение двух многоугольников #5
что-то я не могу сделать это в общем случае.... частные случаи разобрал... а вот в общем...
Евгений М.
1034 / 975 / 53
Регистрация: 28.02.2010
Сообщений: 2,818
Завершенные тесты: 2
30.10.2011, 20:02     Пересечение двух многоугольников #6
Цитата Сообщение от Fantom.AS Посмотреть сообщение
Можете пояснить данное условие?
http://e-maxx.ru/algo/segments_intersection_checking
Fantom.AS
2 / 1 / 0
Регистрация: 17.11.2010
Сообщений: 121
30.10.2011, 20:16  [ТС]     Пересечение двух многоугольников #7
Цитата Сообщение от Евгений М. Посмотреть сообщение
Сообщение от Fantom.AS
Можете пояснить данное условие?
Допустим есть два пятиугольника, необходимо определить, пересекаются ли они? Т.е. имеют ли хотя бы одну общую точку
regmar
0 / 0 / 0
Регистрация: 18.10.2011
Сообщений: 19
30.10.2011, 20:41     Пересечение двух многоугольников #8
Многоугольники выпуклые?
OstapBender
583 / 521 / 35
Регистрация: 22.03.2011
Сообщений: 1,585
30.10.2011, 20:45     Пересечение двух многоугольников #9
многоугольники заданы в 2д или 3д координатах?
Евгений М.
1034 / 975 / 53
Регистрация: 28.02.2010
Сообщений: 2,818
Завершенные тесты: 2
30.10.2011, 22:01     Пересечение двух многоугольников #10
Цитата Сообщение от Fantom.AS Посмотреть сообщение
Допустим есть два пятиугольника, необходимо определить, пересекаются ли они? Т.е. имеют ли хотя бы одну общую точку
Берете одну "сторону" у первого многоугольника, и одну "сторону" второго многоугольника. Проверяйте пересекаются ли эти "стороны". И так со всеми остальными "сторонами".
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
31.10.2011, 16:27     Пересечение двух многоугольников
Еще ссылки по теме:

Пересечение двух колец. (не могу разобраться) C++
Найти пересечение множеств ключей двух map C++
Задача на пересечение двух окружностей C++
C++ Пересечение двух одномерных массивов N размера

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

Или воспользуйтесь поиском по форуму:
Fantom.AS
2 / 1 / 0
Регистрация: 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;
}
но там не проверки на тот случай, если они имеют только одну общую точку или общую сторону
Yandex
Объявления
31.10.2011, 16:27     Пересечение двух многоугольников
Ответ Создать тему
Опции темы

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