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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 39, средняя оценка - 4.59
Fantom.AS
 Аватар для Fantom.AS
2 / 1 / 0
Регистрация: 17.11.2010
Сообщений: 121
30.10.2011, 14:53     Пересечение двух многоугольников #1
Имеются два многоугольника, например два пятиугольника, координаты заданны массивом объектов класса точка.
Надо определить, пересекаются ли они?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.10.2011, 14:53     Пересечение двух многоугольников
Посмотрите здесь:

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

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

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

Или воспользуйтесь поиском по форуму:
Fantom.AS
 Аватар для 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     Пересечение двух многоугольников
Ответ Создать тему
Опции темы

Текущее время: 08:07. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru