Форум программистов, компьютерный форум, киберфорум
Turbo Pascal
Войти
Регистрация
Восстановить пароль
 
3 / 3 / 8
Регистрация: 14.10.2012
Сообщений: 288
1

Перебор четырехугольников и нахождение выпуклого

22.02.2016, 22:34. Показов 450. Ответов 10
Метки нет (Все метки)

Такое задание, у меня есть N точек, я прохожусь по ним и формирую четырехугольники. После, мне из этих четырехугольников нужно выбрать выпуклый четырехугольник.
Есть такой цикл:
Pascal
1
2
3
4
5
6
7
for i := 1 to N do
  for j := 1 to N do
    for k := 1 to N do
      for t := 1 to N do
      begin
         // условие на проверку выпуклости работает
      end;
в этом коде минус- проход по одному и тому же четырехугольнику несколько раз. Как устранить лишние проходы по четырехугольку?
0

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
22.02.2016, 22:34
Ответы с готовыми решениями:

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

Вычисление площади четырехугольников
Составить процедуру,определяющую,можно ли по трем сторонам построить треугольник и вычисляющую в...

Пусть дано n произвольных четырехугольников. Найти четырехугольник с максимальной площадью
Пусть дано n произвольных четырехугольников, заданных координатами своих вершин. Найдите...

Нахождение площади четырехугольников (с выбором фигуры) в MFC
помогите создать программу на нахождения площади четырехугольников, по выбору фигуры, т.е. квадрат,...

10
318 / 208 / 162
Регистрация: 08.12.2015
Сообщений: 861
22.02.2016, 23:28 2
Не ясен алгоритм формирования четырехугольников. И как выбираете выпуклый? Чем больше кода приведете - тем точнее будет совет.
0
3 / 3 / 8
Регистрация: 14.10.2012
Сообщений: 288
23.02.2016, 00:30  [ТС] 3
есть список координат типа TPoint. после циклов выполняется функция, которая принимает индексы точек и возвращает значение true, если четырехугольник выпуклый. N- количество точек
0
3190 / 1761 / 472
Регистрация: 28.02.2015
Сообщений: 3,582
23.02.2016, 09:55 4
Цитата Сообщение от Nike1995 Посмотреть сообщение
проход по одному и тому же четырехугольнику несколько раз. Как устранить лишние проходы по четырехугольку
Pascal
1
2
3
4
5
6
7
for i := 1 to N-3 do
  for j := i+1 to N-2 do
    for k := j+1 to N-1 do
      for t := k+1 to N do
      begin
         // условие на проверку выпуклости работает
      end;
0
Платежеспособный зверь
8743 / 4169 / 1604
Регистрация: 28.10.2009
Сообщений: 11,302
23.02.2016, 18:06 5
Мне кажется, всё можно сделать за один проход, а не за 4. Достаточно, чтобы на 2 шаге увеличивался y, а на 3 шаге увеличивались обе координаты. На худой конец можно сделать сортировку по х и начать с меньшего. Даже так будет оптимальнее.
0
3 / 3 / 8
Регистрация: 14.10.2012
Сообщений: 288
23.02.2016, 19:08  [ТС] 6
не работает. в любом случае придется делать так, как я изначально предложил. если точки будут располагаться в порядке 0 7 3 2(если точек будет 7) и образовывать четырехугольник, то Ваш цикл до них не дойдет

Добавлено через 1 минуту
а можно код? не совсем понял
0
318 / 208 / 162
Регистрация: 08.12.2015
Сообщений: 861
23.02.2016, 19:18 7
Nike1995,
Цитата Сообщение от capricornus CF Посмотреть сообщение
Чем больше кода приведете - тем точнее будет совет.
-
я же намекал.
Вы ваш код покажите, а вам подскажут, как цикл Constantin Cat привязать туда.
0
3 / 3 / 8
Регистрация: 14.10.2012
Сообщений: 288
23.02.2016, 19:49  [ТС] 8
Извините, что на c# в том паблике никто не отвечает. тут сновное-это алгоритм. синтаксис, лумаю, понятен)
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
 
float[] sum = new float[pnt.Count * 4]; //так как по четырехугольнику несколько раз пробегаюсь, то выделяю //память под массив в четыре раза больше
            int count_point = 0;
                if (pnt.Count < 4)
                    MessageBox.Show("Количество точек должно быть не менее четырех!");
                else
                {
                    for (int i = 0; i < pnt.Count; i++)
                        for (int j = 0; j < pnt.Count; j++)
                            for (int k = 0; k < pnt.Count; k++)
                                for (int t = 0; t < pnt.Count; t++)
                                {
// тут вырожденность проверяется
                                    if (is_convex(i, j, k, t) == true)
                                    {
//в задании нужен выпуклый четырехугольник, у которого разница максимального и минимального треугольников, 
//образованных пересечение диагоналей четырехугольника, минимальна. тут я передаю четырехугоьник и ///.возвращаю разницу
                                        sum[count_point] = max_min_area(pnt[i].X, pnt[i].Y, pnt[k].X, pnt[k].Y,
                                                                        pnt[j].X, pnt[j].Y, pnt[t].X, pnt[t].Y);
//далее получаю четыре точки, чтобы потом их соединить линиями
                                       
                                        if (count_point >= 1)
                                        {
                                            for (int y = 1; y < count_point; y++)
                                                if (sum[y] < sum[y - 1] && sum[y] >= 0)
                                                {
                                                    a = pnt[i];
                                                    b = pnt[k];
                                                    c = pnt[j];
                                                    d = pnt[t];
                                                }
                                        }
                                        else
                                        {
                                            a = pnt[i];
                                            b = pnt[k];
                                            c = pnt[j];
                                            d = pnt[t];
                                        }
                                        count_point++;
                                    }
                                }
                }
                draw_line(a, c);
                draw_line(c, b);
                draw_line(b, d);
                draw_line(d, a);
            }
0
3190 / 1761 / 472
Регистрация: 28.02.2015
Сообщений: 3,582
23.02.2016, 20:18 9
Nike1995,
Смотрите на индексы цикла:
1 2 3 4
1 2 3 5
1 2 3 6
1 2 3 7
1 2 4 5
1 2 4 6
1 2 4 7
1 2 5 6
1 2 5 7
1 2 6 7
1 3 4 5
1 3 4 6
1 3 4 7
1 3 5 6
1 3 5 7
1 3 6 7
1 4 5 6
1 4 5 7
1 4 6 7
1 5 6 7
2 3 4 5
2 3 4 6
2 3 4 7
2 3 5 6
2 3 5 7
2 3 6 7
2 4 5 6
2 4 5 7
2 4 6 7
2 5 6 7
3 4 5 6
3 4 5 7
3 4 6 7
3 5 6 7
4 5 6 7
Меняете свой цикл на конструкцию из моего поста и не парьтесь.
0
3 / 3 / 8
Регистрация: 14.10.2012
Сообщений: 288
23.02.2016, 20:35  [ТС] 10
не работает. уже вставлял
0
318 / 208 / 162
Регистрация: 08.12.2015
Сообщений: 861
23.02.2016, 20:54 11
Если я что то в чем то понимаю, ты вы сделали вот так?:
C#
1
2
3
4
 for (int i = 0; i < pnt.Count-3; i++)
                        for (int j = i+1; j < pnt.Count-2; j++)
                            for (int k = k+2; k < pnt.Count-1; k++)
                                for (int t = t+3; t < pnt.Count; t++)
и это не работает?
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
23.02.2016, 20:54

Помощь в написании контрольных, курсовых и дипломных работ здесь.

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

Установить факт пересечения четырехугольников
Нужно было сделать прогу, которая будет проверять пересечение двух четырёхугольников. Рылся в гугле...

Доказать, что периметры четырехугольников равны
Помогите решить задачу. В выпуклом пятиугольнике ABCDE вершина Е соединена равными диагоналями с...

Создать класс четырехугольников, квадратов и прямоугольников (иерархия)
Создать класс четырехугольников, квадратов и прямоугольников. Создать из них иерархию. Определить...


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

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

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