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

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

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

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

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

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

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

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

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

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

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

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

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

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Mиxaил
533 / 438 / 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ил
533 / 438 / 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
что-то я не могу сделать это в общем случае.... частные случаи разобрал... а вот в общем...
Евгений М.
1035 / 976 / 54
Регистрация: 28.02.2010
Сообщений: 2,829
Завершенные тесты: 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д координатах?
Евгений М.
1035 / 976 / 54
Регистрация: 28.02.2010
Сообщений: 2,829
Завершенные тесты: 2
30.10.2011, 22:01     Пересечение двух многоугольников #10
Цитата Сообщение от Fantom.AS Посмотреть сообщение
Допустим есть два пятиугольника, необходимо определить, пересекаются ли они? Т.е. имеют ли хотя бы одну общую точку
Берете одну "сторону" у первого многоугольника, и одну "сторону" второго многоугольника. Проверяйте пересекаются ли эти "стороны". И так со всеми остальными "сторонами".
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
31.10.2011, 16:27     Пересечение двух многоугольников
Еще ссылки по теме:

Пересечение двух колец. (не могу разобраться) - C++
Всем привет. Условие таково. Ввести два кольца. Определить пересекаются ли они. Учесть все возможные случаи. не могу понять как...

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

Найти пересечение множеств ключей двух map - C++
Добрый день! Имеется 2 map'а: map&lt;string, double&gt; map1; map&lt;string, double&gt; map2; Требуется сложить ключи, являющиеся общими...

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

Площадь многоугольников - C++
Дана задача: Компонент ListBox содержит названия правильных многоугольников. Составить программу, вычисляющую площадь выбранного...


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

Или воспользуйтесь поиском по форуму:
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