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

Помогите с алгоритмом - C++

Войти
Регистрация
Восстановить пароль
 
persalena
0 / 0 / 0
Регистрация: 02.12.2008
Сообщений: 23
09.09.2009, 19:19     Помогите с алгоритмом #1
Даны координаты вершин двух трапеций. нужно проверить вложена ли одна трапеция в другую . Подскажите какую-нибудь идею, а то у меня выходит как-то слишком громоздко, некрасиво и вероятнее всего неправильно...
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
TanT
эволюционирую потихоньку
 Аватар для TanT
464 / 462 / 43
Регистрация: 30.06.2009
Сообщений: 1,399
09.09.2009, 20:30     Помогите с алгоритмом #2
Что есть трапеция? С точки зрения меня - это область пространства, ограниченного отрезками прямых линий.
Каждая сторона трапеции, если её бесконечно продолжит, делит всю двумерную плоскоть пополам, и, оставшиеся две вершины, через которые не проходит воображаемая прямая, лежат по одну сторону этой самой прямой.
С точки зрения алгоритма кажется самым простым строить уравнение прямой y=kx+b для каждой пары точек одной из трапеций, находит в какой полуплоскости лежать оставшиеся две вершины и в какой полуплоскости лежать точки второй трапеции. Если точки второй трапеции лежат в разных полуплоскостях - уже точно не вписанных трапеции. Если по ходу проверки вершины второй трапеции лежат в одной и тойже полуплоскости что и оставшиеся вершины первой трапеции или всегда в противоположной. Тут ключевое слово "всегда". То соответственно можно вписать. иначе нет.
Вот как-то так.
P.S. можно конечно проверять где пересекаются уравнения прямых каждой из сторон обоих трапеций и проверять не попадаются эти точки в отрезках прямых, ограниченных вершинами трапеций. но это ИМХО сложнее.
АНК
124 / 115 / 2
Регистрация: 27.02.2007
Сообщений: 291
09.09.2009, 20:57     Помогите с алгоритмом #3
Опишите свой алгоритм, посмотрим ...
M128K145
Эксперт C++
 Аватар для M128K145
8276 / 3495 / 142
Регистрация: 03.07.2009
Сообщений: 10,707
09.09.2009, 22:01     Помогите с алгоритмом #4
Вот у нас есть такие данные
Помогите с алгоритмом
Тогда имеем
точка 1: если x1 > i1 и y1 < j1
точка 2: если x2 > i2 и y2 > j2
точка 3: если x3 < i3 и y3 > j3
точка 4: если x4 < i4 и y4 < j4
То трапеция А содержит трапецию B.
Вот небольшой
код
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
 
bool Content(int tr1[4][2], int tr2[4][2])
{
    return ((tr1[0][0] > tr2[0][0]) && (tr1[0][1] < tr2[0][1]) &&
        (tr1[1][0] > tr2[1][0]) && (tr1[1][1] > tr2[1][1]) &&
        (tr1[2][0] < tr2[2][0]) && (tr1[2][1] > tr2[2][1]) &&
        (tr1[3][0] < tr2[3][0]) && (tr1[3][1] < tr2[3][1])) ? true : false;
}
 
int main()
{
    setlocale(LC_ALL, "Russian");
    int trap1[4][2], trap2[4][2], i;
 
    std::cout<<"Введите координаты трапеции A:\n";
    for(i = 0; i < 4; ++i)
    {
        std::cout<<"Введите координаты точки A"<<i+1<<":\nx"<<i+1<<"> ", std::cin>>trap1[i][0];
        std::cout<<"y"<<i+1<<"> ", std::cin>>trap1[i][1];
    }
 
    std::cout<<"Введите координаты трапеции B:\n";
    for(i = 0; i < 4; ++i)
    {
        std::cout<<"Введите координаты точки B"<<i+1<<":\ni"<<i+1<<"> ", std::cin>>trap2[i][0];
        std::cout<<"j"<<i+1<<"> ", std::cin>>trap2[i][1];
    }
 
    if(Content(trap1, trap2))
        std::cout<<"Первая трапеция содержит вторую\n";
    else
        std::cout<<"Первая трапеция не содержит вторую\n";
    system("pause");
    return 0;
}
, который выполняет эту проверку.
Проверку на ввод некорректных данных не делал
АНК
124 / 115 / 2
Регистрация: 27.02.2007
Сообщений: 291
09.09.2009, 22:19     Помогите с алгоритмом #5
Цитата Сообщение от M128K145 Посмотреть сообщение
Проверку на ввод некорректных данных не делал
А если сначала введены вершины маленькой трапеции, или с правой вершины начали, или обход вершин в разные сторона, да и вообще вершины не попорядку. Вот это-то и усложняет алгоритм на порядок.
M128K145
Эксперт C++
 Аватар для M128K145
8276 / 3495 / 142
Регистрация: 03.07.2009
Сообщений: 10,707
09.09.2009, 23:53     Помогите с алгоритмом #6
АНК, ну где-то так, чтобы точно не
запутаться
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
bool Content(int tr1[4][2], int tr2[4][2])
{
    return (((tr1[0][0] > tr2[0][0]) && (tr1[0][1] < tr2[0][1]) &&
        (tr1[1][0] > tr2[1][0]) && (tr1[1][1] > tr2[1][1]) &&
        (tr1[2][0] < tr2[2][0]) && (tr1[2][1] > tr2[2][1]) &&
        (tr1[3][0] < tr2[3][0]) && (tr1[3][1] < tr2[3][1])) ||
        ((tr2[0][0] > tr1[0][0]) && (tr2[0][1] < tr1[0][1]) &&
        (tr2[1][0] > tr1[1][0]) && (tr2[1][1] > tr1[1][1]) &&
        (tr2[2][0] < tr1[2][0]) && (tr2[2][1] > tr1[2][1]) &&
        (tr2[3][0] < tr1[3][0]) && (tr2[3][1] < tr1[3][1]))) ? true : false;
}
char* Top(int i) 
{
    char *top;
    switch(i)
    {
    case 0: top = "Введите координаты верхней левой вершины";break;
    case 1: top = "Введите координаты верхней правой вершины";break;
    case 3: top = "Введите координаты нижней правой вершины";break;
    default:top = "Введите координаты нижней левой вершины";
    }
    return top;
}
int main()
{
    setlocale(LC_ALL, "Russian");
    int trap1[4][2], trap2[4][2], i;
 
    std::cout<<"Введите координаты трапеции A:\n";
    for(i = 0; i < 4; ++i)
    {
        std::cout<<Top(i)<<":\nx"<<i+1<<"> ", std::cin>>trap1[i][0];
        std::cout<<"y"<<i+1<<"> ", std::cin>>trap1[i][1];
    }
 
    std::cout<<"Введите координаты трапеции B:\n";
    for(i = 0; i < 4; ++i)
    {
        std::cout<<Top(i)<<":\ni"<<"> ", std::cin>>trap2[i][0];
        std::cout<<"j"<<i+1<<"> ", std::cin>>trap2[i][1];
    }
 
    if(Content(trap1, trap2))
        std::cout<<"Первая трапеция содержит вторую\n";
    else
        std::cout<<"Первая трапеция не содержит вторую\n";
    system("pause");
    return 0;
}
да, понимаю что я не учел углы и все такое, но основную суть я думаю выложил
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.09.2009, 10:36     Помогите с алгоритмом
Еще ссылки по теме:

C++ Помогите с алгоритмом
Помощь с алгоритмом C++
C++ Не могу разобраться с алгоритмом
Кодирование алгоритмом Хаффмана C++
Разобраться с алгоритмом задачи C++

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

Или воспользуйтесь поиском по форуму:
odip
Эксперт C++
 Аватар для odip
7226 / 3288 / 59
Регистрация: 17.06.2009
Сообщений: 14,165
10.09.2009, 10:36     Помогите с алгоритмом #7
M128K145 - твой алгоритм скорее всего неправильный.
Правильный алгоритм привел TanT в Помогите с алгоритмом
Yandex
Объявления
10.09.2009, 10:36     Помогите с алгоритмом
Ответ Создать тему
Опции темы

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