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

Множество точек определяет ломаную. Имеет ли она самопересечения? - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 30, средняя оценка - 4.73
Destiny
Сообщений: n/a
04.02.2009, 18:06     Множество точек определяет ломаную. Имеет ли она самопересечения? #1
Помогите, пожалуйста, кто-нибудь!

В задачах предполагается, что во входном файле записана последовательность пар чисел, которые можно рассматривать как координаты множества точек на плоскости.
Для представления геометрических объектов нужно использовать структуры.
Во всех задачах в начале входного файла стоит число = количеству ПАР чисел, идущих после этого числа, т.е. размерность вектора структур { double x,y; }, в который эти пары можно поместить.
1. Множество точек определяет ломаную. Имеет ли она самопересечения? Ответ: 1 - да, 0 - нет.
2. Множество точек определяет многоугольник. Для данной точки определить, где она расположена относительно этого многоугольника: внутри, снаружи, на границе. Ответ: 1 - внутри, -1 - снаружи, 0 - на границе.
Круг задается 3 последними числами:
координаты центра
радиус

Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.02.2009, 18:06     Множество точек определяет ломаную. Имеет ли она самопересечения?
Посмотрите здесь:

C++ множество точек
C++ Множество точек.Найти множество треугльники
C++ на плоскости задано множество точек. Найти все подмножества точек, лежащих на одной прямой.
C++ Задано множество точек в трехмерном пространстве. Найти минимум радиусов шаров с центрами в этих точках, содержащих ровно n точек этого множества
C++ На плоскости задано множество точек. Выбрать три различные точки так, чтобы проходящая через них окружность делила это множество на группы
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
maximus09
32 / 32 / 3
Регистрация: 29.12.2008
Сообщений: 75
05.02.2009, 18:52     Множество точек определяет ломаную. Имеет ли она самопересечения? #2
В общем, не хочу за тебя просто так писать программу. Скажу только алгоритм выполнения. Думаю, дальше ты справишься.

Задача 1.
Эта задача сводится к тому, что надо определить, пересекаются ли два заданных отрезка. Обозначим координаты концов первого отрезка за (x1a,y1a) и (x1b,y1b). Координаты концов второго - (x2a,y2a) и (x2b,y2b).

Вводим величины
k1 = (y1b-y1a)/(x1b-x1a),
k2 = (y2b-y2a)/(x2b-x2a).

Далее находим

x = (y2a-y1a+k1*x1a-k2*x2a)/(k1-k2)
y = k1*(x-x1a)+y1a

Далее находим значения
d1a = sqrt((x1a-x)^2+(y1a-y)^2)
d1b = sqrt((x1b-x)^2+(y1b-y)^2)
d1 = sqrt((x1b-x1a)^2+(y1b-y1a)^2)

d2a = sqrt((x2a-x)^2+(y2a-y)^2)
d2b = sqrt((x2b-x)^2+(y2b-y)^2)
d2 = sqrt((x2b-x2a)^2+(y2b-y2a)^2)

Отрезки пересекаются, если имеет место равенства:
d1a+d1b = d1
d2a+d2b = d2

(эти два равенства должны выполняться одновременно).

Перебрав все возможные пары звеньев ломанной, можно определить, пересекает ли эта ломанная саму себя.

Добавлено через 20 минут 18 секунд
Задача 2.
Первое, что нужно сделать - это найти площадь всего многоугольника целиком. Для этого разбиваешь его на несколько треугольников, проводя все возможные диагонали из одной вершины. Площадь всего многоугольника находится как сумма площадей всех полученных треугольников.

Площадь треугольника, координаты вершин которого есть (x1,y1), (x2,y2) и (x3,y3) можно найти как
St = abs((x1-x3)(y2-y3) - (y1-y3)(x2-x3))/2.

Обозначим за Sm площадь многоугольника.

Далее соединяем точку, положение которой относительно многоугольника нужно найти также со всеми вершинами многоугольника. Получим несколько треугольников. Находим суммарную площадь всех этих треугольников. Обозначим ее буквой S.

Если S>Sm, то точка лежит вне многоугольника.
Если S=Sm, то точка лежит на границе многоугольника.
Если S<Sm, то точка лежит внутри многоугольника.

Жаль, но все сказанное справедливо только для выпуклого многоугольника. Для невыпуклого вопрос пока остается открытым.

Добавлено через 22 часа 59 минут 36 секунд
Жаль, но все сказанное справедливо только для выпуклого многоугольника. Для невыпуклого вопрос пока остается открытым.
В принципе, и для невыпуклого многоугольника тоже подходит. Но надо правильно рассчитать площадь этого невыпуклого многоугольника.
maximus09
32 / 32 / 3
Регистрация: 29.12.2008
Сообщений: 75
09.02.2009, 18:49     Множество точек определяет ломаную. Имеет ли она самопересечения? #3
В принципе, и для невыпуклого многоугольника тоже подходит. Но надо правильно рассчитать площадь этого невыпуклого многоугольника.
Для рассчета площади невыпуклого многоугольника можно воспользоваться следующим алгоритмом.

1. Выбрать 1-ю вершину мгногоугольника (номер, естественно, условный).
2. Провести от нее все возможные диагонали. Т.е. разбить многоугольник на треугольники.
3. Вычислить сумму площадей всех получившихся треугольников.
4. Взять 2-ю вершину многоугольника и выполнить для нее действия пунктов 2 и 3.
5. Аналогично поступаем с 3, 4, 5 и т.д. вершинами.

За истинную площадь многоугольника принимаем наименьшую из полученных сумм площадей треугольников.
heaRtseAs
Сообщений: n/a
22.02.2009, 14:34     Множество точек определяет ломаную. Имеет ли она самопересечения? #4
мне не совсем понятно, почему алгоритм решения первой задачи верен.
Не могли бы вы объяснить это?

Добавлено через 26 минут 3 секунды
Вы находите, пересекаются ли прямые, которым принадлежат отрезки, а потом оцениваете, где находится точка пересечения? я правильно понимаю?
и еще один, возможно, совсем глупый вопрос, скажите, пожалуйста, в чем основное отличие кодирования структур от кодирования массивов?
нужно написать несколько программ, а как - не могу до конца разобраться.
Допустим, вот мы выделили память, считали из файла данные
C++
1
2
3
4
5
6
7
8
9
while (fscanf(f,"%f",&c)==1)
       n++;
    n=n/2;
    arr=(struct koord*)malloc(sizeof(struct koord)* n);
    for (i=0; i<n; i++)
    {
       fscanf(f,"%f",&arr[i].x);
       fscanf(f,"%f",&arr[i].y);
    }
А как дальше разбить на начала и концы отрезков?
zinurzhan
Сообщений: n/a
13.11.2011, 13:43     Множество точек определяет ломаную. Имеет ли она самопересечения? #5
можете пожалуйста написать программу 1, а то я в с не очень
Andrey B
0 / 0 / 0
Регистрация: 06.02.2015
Сообщений: 5
06.02.2015, 17:42     Множество точек определяет ломаную. Имеет ли она самопересечения? #6
Пожалуйста необходима помощь в исправлении этой же задачи !
Имеет ли ломанная точку самопересечения
1- да 0 -нет

Очень плохо работаю со структурами но алгоритм нахождения точки пересечения правильный
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
 
 
typedef struct 
 
{ int x; int y; } point; 
 
typedef struct 
{ 
point p1; point p2;
 
} line; 
 
int check_lines(line, line, point);
 
 
int check_lines(line *line1, line *line2, point *hitp) { 
 
int d = (line2->p2.y - line2->p1.y)*(line1->p2.x-line1->p1.x) - (line2->p2.x - line2->p1.x)*(line1->p2.y-line1->p1.y); 
int n_a = (line2->p2.x - line2->p1.x)*(line1->p1.y-line2->p1.y) - (line2->p2.y - line2->p1.y)*(line1->p1.x-line2->p1.x); 
int n_b = (line1->p2.x - line1->p1.x)*(line1->p1.y - line2->p1.y) - (line1->p2.y - line1->p1.y)*(line1->p1.x - line2->p1.x);  
if(d == 0) return 0; 
int ua = (n_a << 14)/d; int ub = (n_b << 14)/d; 
 
{ hitp->x = line1->p1.x + ((ua * (line1->p2.x - line1->p1.x))>>14); hitp->y = line1->p1.y + ((ua * (line1->p2.y - line1->p1.y))>>14); return 1; } 
return 0; 
 
}
 
 
int task(char *FileName)
{
line *all_lines;
point  *points;
 
FILE *f_in,*f_out;
int n,rez,i,j;
    
    f_in=fopen("in.txt","r");
    f_out=fopen("out.txt","w");
 
    fscanf(f_in,"%d",&n);
    if (n<=2) return -777; else 
 
    points=(point*)malloc(sizeof(point)*(n+2));
    all_lines=(line*)malloc(sizeof(line)*(n+2));
 
        for(i=0;i<n;i++)
        {
            fscanf(f_in,"%lf%lf",&all,&points[i].y);
        }
            
                
 
                    for(i=1;i<n;i++)
                    {
                        for(j=1;j<n-1;j++)
                        {
                            rez=check_lines(&all_lines[i],&all_lines[i+1],&points[i]);
                            
                            if(rez==1)
                            {
                                fprintf(f_out,"%d",rez);
                                return 0;
                            }
                        }
                    }
    
                    fprintf(f_out,"%d",rez);
                
                        
    fclose(f_in);
    fclose(f_out);
    free (all_lines);
    free (points);
    return 0;
}
Добавлено через 17 минут
Пожалуйста очень нужна Ваша Помощь !!
Байт
 Аватар для Байт
13988 / 8819 / 1230
Регистрация: 24.12.2010
Сообщений: 15,975
06.02.2015, 18:46     Множество точек определяет ломаную. Имеет ли она самопересечения? #7
В задаче 1 я бы основовался на уравнении отрезка. Вот оно в векторном виде: X = A*t - (1-t)*B 0<=t <=1
Т.е если система из таких уравнений и неравенств относительно 2-х неизвестных s, t имеет решение - они пересекаются, иначе - нет
Ax*t + Bx*(t-1) = Cx*s +Dx*(1-s)
Ay*t + By*(t-1) = Cy*s +Dy*(1-s)
0 <= t <= 1
0 <= s <= 1
Ax, Ay... -здесь координаты точек
Andrey B
0 / 0 / 0
Регистрация: 06.02.2015
Сообщений: 5
06.02.2015, 20:02     Множество точек определяет ломаную. Имеет ли она самопересечения? #8
Спасибо за ответ но переделывать времени уже не осталось
Предположим что условие check_lines правильно определяет пересечения
Можете тогда помочь с правильной постановкой цикла и выводом ответа
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.02.2015, 21:09     Множество точек определяет ломаную. Имеет ли она самопересечения?
Еще ссылки по теме:

C++ Дано множество точек на плоскости, заданных полярными координатами. Получить декартовы координаты этих точек
C++ Программа, которая определяет принадлежность точек к полукружию
Определить, имеет ли ломаная линия самопересечения C++

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

Или воспользуйтесь поиском по форуму:
Байт
 Аватар для Байт
13988 / 8819 / 1230
Регистрация: 24.12.2010
Сообщений: 15,975
06.02.2015, 21:09     Множество точек определяет ломаную. Имеет ли она самопересечения? #9
C++
1
2
3
4
5
6
7
8
for(i=1; i<n;i++) 
  for(j=0; j<i; j++) {
     if (check_line(line[i], line[j])) break;
  }
   if (j < i) break;
}
if (i<n) cout << "Пересекаются";
else cout<<"Нет пересечений";
(Псевдокот)
Yandex
Объявления
06.02.2015, 21:09     Множество точек определяет ломаную. Имеет ли она самопересечения?
Ответ Создать тему
Опции темы

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