Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.77/13: Рейтинг темы: голосов - 13, средняя оценка - 4.77
2 / 2 / 0
Регистрация: 23.09.2008
Сообщений: 54
1

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

05.11.2014, 23:07. Показов 2531. Ответов 10
Метки нет (Все метки)

Функция, рассчитывающая контур пересечения двух треугольников
Всем доброго дня, у меня возникла проблема с написанием этой функции, т.к. я не совсем понимаю что от меня требуется. Прошу вас знающий людей помочь разобраться с этой функцией и если есть эта реализация, то было бы здорово.
__________________
Помощь в написании контрольных, курсовых и дипломных работ здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
05.11.2014, 23:07
Ответы с готовыми решениями:

Найти площадь от пересечения двух треугольников
Заданы два равных равнобедренных треугольника со сторонами 1, 4, 4. Они наложены друг на друга (см....

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

Функция проверки двух треугольников на поглощение на плоскости
Доброго всем вечера! Очень нужна помощь! Необходимо написать функцию проверки двух треугольников на...

Нарисовать окружности и выделить их пересечения и контур
помогите пожалуйста , как через VS 2019 нарисовать окружности и выделить их пересечения и контур ,...

10
Эксперт С++
3211 / 1738 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
27.11.2014, 09:47 2
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
/////////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <complex>
#include <iostream>
#include <iterator>
#include <limits>
#include <string>
#include <utility>
#include <vector>
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::string                     T_str;
typedef double                          T_coord;
typedef std::complex    < T_coord   >   T_point_val;
/////////////////////////////////////////////////////////////////////////////////////////
class   T_point
{
    //-----------------------------------------------------------------------------------
    T_point_val     point_val_;
    //-----------------------------------------------------------------------------------
    friend  std::istream    &   operator>>
        (
            std::istream    &   istr,
            T_point         &   point
        )
    {
        istr    >>  point.point_val_;
        return  istr;
    }
    //-----------------------------------------------------------------------------------
    friend  std::ostream    &   operator<<
        (
            std::ostream            &   ostr,
            T_point         const   &   point
        )
    {
        ostr    <<  point.point_val_;
        return  ostr;
    }
    //-----------------------------------------------------------------------------------
public:
    //-----------------------------------------------------------------------------------
    T_point( T_point_val    const   &   point_val   =   0 )
        :
        point_val_( point_val )
    {}
    //-----------------------------------------------------------------------------------
    T_point( T_coord    const   &   coord )
        :
        point_val_( coord )
    {}
    //-----------------------------------------------------------------------------------
    T_coord     x()                                                                 const
    {
        return  point_val_.real();
    }
    //-----------------------------------------------------------------------------------
    T_coord     y()                                                                 const
    {
        return  point_val_.imag();
    }
    //-----------------------------------------------------------------------------------
    T_point     operator+   ( T_point   const   &   p )                             const
    {
        return      point_val_
                +   p.point_val_;
    }
    //-----------------------------------------------------------------------------------
    T_point     operator-   ( T_point   const   &   p )                             const
    {
        return      *this   +   -p;
    }
    //-----------------------------------------------------------------------------------
    T_point     operator-   ()                                                      const
    {
        return  -point_val_;
    }
    //-----------------------------------------------------------------------------------
    T_point     operator*=  ( T_point   const   &   p )
    {
        point_val_  *=  p.point_val_;
        return  *this;
    }
    //-----------------------------------------------------------------------------------
    T_point     operator/=  ( T_point   const   &   p )
    {
        point_val_  /=  p.point_val_;
        return  *this;
    }
    //-----------------------------------------------------------------------------------
    bool    operator==  ( T_point   const   &   p )                                 const
    {
        static  const   auto    factor      =   1000;
        static  const   auto    eps         =   std::numeric_limits< T_coord >::epsilon();
 
        auto                    max_abs     =   std::max    (
                                                                abs( point_val_     ),
                                                                abs( p.point_val_   )
                                                            );
 
        auto                    delta       =       ( 1 + max_abs )
                                                *   eps
                                                *   factor;
 
        return  abs( point_val_ - p.point_val_ )    <   delta;
    }
    //-----------------------------------------------------------------------------------
    bool    operator!=  ( T_point   const   &   p )                                 const
    {
        return  !(*this     ==  p );
    }
    //-----------------------------------------------------------------------------------
    bool    operator<   ( T_point   const   &   p )                                 const
    {
        return      std::make_pair
                        (
                            x(),
                            y()
                        )
 
                <   std::make_pair
                        (
                            p.x(),
                            p.y()
                        );
    }
    //-----------------------------------------------------------------------------------
};
/////////////////////////////////////////////////////////////////////////////////////////
T_point     operator*
    (
        T_point     const   &   L,
        T_point     const   &   R
    )
{
    auto    res     =   L;
    return  res     *=  R;
}
/////////////////////////////////////////////////////////////////////////////////////////
T_point     operator/
    (
        T_point     const   &   L,
        T_point     const   &   R
    )
{
    auto    res     =   L;
    return  res     /=  R;
}
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::vector     < T_point               >   T_points;
typedef std::pair       < T_point,  T_point     >   T_side;
/////////////////////////////////////////////////////////////////////////////////////////
T_point     vect
    (
        T_point     const   &   A,
        T_point     const   &   B
    )
{
    return  B   -   A;
}
/////////////////////////////////////////////////////////////////////////////////////////
T_point     vect( T_side  const   &   side )
{
    return      side.second
            -   side.first;
}
/////////////////////////////////////////////////////////////////////////////////////////
T_coord     det
    (
        T_point     const   &   M,
        T_point     const   &   N
    )
{
    return      M.x()    *   N.y()
            -   M.y()    *   N.x();
}
/////////////////////////////////////////////////////////////////////////////////////////
T_coord     det
    (
        T_side  const   &   side_1,
        T_side  const   &   side_2
    )
{
    return  det (
                    vect( side_1 ),
                    vect( side_2 )
                );
}
/////////////////////////////////////////////////////////////////////////////////////////
class   T_triangle
{
    //-----------------------------------------------------------------------------------
    T_point     A_;
    T_point     B_;
    T_point     C_;
    //-----------------------------------------------------------------------------------
public:
    //-----------------------------------------------------------------------------------
    T_side  get_begin_side()                                                        const
    {
        return  T_side( A_, B_ );
    }
    //-----------------------------------------------------------------------------------
    T_points    get_all_vertices()                                                  const
    {
        T_points    res_vertices;
 
        res_vertices.push_back(A_);
        res_vertices.push_back(B_);
        res_vertices.push_back(C_);
 
        return  res_vertices;
    }
    //-----------------------------------------------------------------------------------
    bool    is_vert( T_point    const   &   point )                                 const
    {
        return      point   ==  A_
                ||  point   ==  B_
                ||  point   ==  C_;
    }
    //-----------------------------------------------------------------------------------
    T_side  get_next_side( T_side   const   &   side )                              const
    {
        return  get_side_goes_from_vert( side.second );
    }
    //-----------------------------------------------------------------------------------
    bool    point_is_inside( T_point    const   &   w )                             const
    {
        auto    v   =   begin_vert();
 
        do
        {
            if  (
                        det (
                                vect    (w, v),
 
                                vect    (
                                            w,
                                            get_next_vert(v)
                                        )
                            )
 
                    <=  0
                )
            {
                return  false;
            }
 
            v   =   get_next_vert(v);
        }
        while   (
                    v   !=  begin_vert()
                );
 
        return  true;
    }
    //-----------------------------------------------------------------------------------
2
Эксперт С++
3211 / 1738 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
27.11.2014, 09:50 3
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
    T_point     begin_vert()                                                        const
    {
        return  A_;
    }
    //-----------------------------------------------------------------------------------
    T_side  get_side_goes_from_vert( T_point  const   &   v )                       const
    {
        return  T_side  (
                            v,
                            get_next_vert(v)
                        );
    }
    //-----------------------------------------------------------------------------------
    T_point     get_next_vert( T_point  const   &   v )                             const
    {
        if( v   ==  A_ )
        {
            return  B_;
        }
        else if( v  ==  B_ )
        {
            return  C_;
        }
        else
        {
            return  A_;
        }//else
    }
    //-----------------------------------------------------------------------------------
    void    input_vertices_with_triangle_name( T_str    const   &   triangle_name )
    {
        std::cout   <<  "\t"
                    <<  triangle_name
                    <<  std::endl
                    <<  "\t\tA\t= ";
 
        std::cin    >>  A_;
 
        do
        {
            std::cout   <<  "\t\tB\t= ";
            std::cin    >>  B_;
        }
        while   (
                    B_  ==  A_
                );
 
        do
        {
            std::cout   <<  "\t\tC\t= ";
            std::cin    >>  C_;
        }
        while   (
                        det (
                                vect( A_, B_ ),
                                vect( A_, C_ )
                            )
 
                    ==  0
                );
 
        std::cout   <<  std::endl;
        arrange_vertices_counterclockwise();
    }
    //-----------------------------------------------------------------------------------
private:
    //-----------------------------------------------------------------------------------
    void    arrange_vertices_counterclockwise()
    {
        if  (
                    det (
                            vect( A_,   B_ ),
                            vect( A_,   C_ )
                        )
                <   0
            )
        {
            std::swap( B_,  C_ );
        }
    }
    //-----------------------------------------------------------------------------------
};
/////////////////////////////////////////////////////////////////////////////////////////
bool    successfully_for_sides_set_intersection_point
    (
        T_side      const   &   side_AB,
        T_side      const   &   side_CD,
        T_point             &   intersec_point
    )
{
    bool    bool_res    =   false;
 
    //Находим точку R пересечения прямых, задаваемых векторами AB и CD.
    //R = A + AB * x
    //R = C + CD * y
    //A + AB * x = C + CD * y
    //AB * x - CD * y = C - A
    //
    //AB * x - CD * y = AC
 
    auto    vect_AB     =   vect( side_AB   );
    auto    vect_CD     =   vect( side_CD   );
 
    auto    vect_AC     =   vect    (
                                        side_AB.first,
                                        side_CD.first
                                    );
 
    auto    main_det    =   det (
                                    vect_AB,
                                    -vect_CD
                                );
 
    bool_res    =   main_det    !=  0;
 
    if( bool_res )
    {
        auto    det_X       =   det (
                                        vect_AC,
                                        -vect_CD
                                    );
 
        auto    X           =   det_X / main_det;
 
        auto    det_Y       =   det (
                                        vect_AB,
                                        vect_AC
                                    );
 
        auto    Y           =   det_Y / main_det;
 
        bool    intersection_point_belongs_to_both_sides    =       0   <=  X
                                                                &&  X   <=  1
                                                                &&  0   <=  Y
                                                                &&  Y   <=  1;
 
        bool_res    =   intersection_point_belongs_to_both_sides;
 
        if( bool_res )
        {
            intersec_point  =       side_AB.first
                                +   X   *   vect_AB;
        }//if
    }//else
 
    return  bool_res;
}
/////////////////////////////////////////////////////////////////////////////////////////
class   T_intersection_contour
{
    //-----------------------------------------------------------------------------------
    typedef std::vector < T_triangle    >   T_triangles;
    typedef bool                            T_first_second_ind;
    //-----------------------------------------------------------------------------------
    static  const   T_first_second_ind  first   =   false;
    static  const   T_first_second_ind  second  =   !first;
    //-----------------------------------------------------------------------------------
    T_triangles         triangles_;
    T_points            vertices_;
    T_point             cur_vert_;
    T_first_second_ind  cur_triangle_ind_;
    T_point             cur_triangle_directive_vert_;
    //-----------------------------------------------------------------------------------
public:
    //-----------------------------------------------------------------------------------
    T_intersection_contour
        (
            T_triangle  const   &   triangle_1,
            T_triangle  const   &   triangle_2
        )
    {
        triangles_.push_back( triangle_1 );
        triangles_.push_back( triangle_2 );
    }
    //-----------------------------------------------------------------------------------
    void    fill_vertices()
    {
        if  (
                triangles_coincide()
            )
        {
            vertices_   =   for_triangle_with_ind_get_all_vertices( first );
        }
        else if (
                    successfully_set_first_cur_vert_data()
                )
        {
            do
            {
                vertices_.push_back     ( cur_vert_ );
                inc_cur_vert            ();
            }
            while   (
                        cur_vert_   !=  vertices_.front()
                    );
        }//if
    }
    //-----------------------------------------------------------------------------------
    void    print_vertices()                                                        const
    {
        if  (
                vertices_.empty()
            )
        {
            std::cout   <<  "Треугольники не пересекаются."
                        <<  std::endl;
        }
        else
        {
            std::cout   <<  "Контур пересечения треугольников состоит из точек:"
                        <<  std::endl;
 
            std::copy
                (
                    vertices_.begin                     (),
                    vertices_.end                       (),
                    std::ostream_iterator< T_point >    ( std::cout,    "\t" )
                );
        }
    }
    //-----------------------------------------------------------------------------------
private:
    //-----------------------------------------------------------------------------------
    T_points    for_triangle_with_ind_get_all_vertices( T_first_second_ind  triangle_ind )  const
    {
        return  get_const_triangle_ref_with_ind( triangle_ind ).get_all_vertices();
    }
    //-----------------------------------------------------------------------------------
    bool    triangles_coincide()                                                    const
    {
        auto    vertices_first      =   for_triangle_with_ind_get_all_vertices( first   );
        auto    vertices_second     =   for_triangle_with_ind_get_all_vertices( second  );
 
        std::sort( vertices_first   .begin(),  vertices_first   .end()  );
        std::sort( vertices_second  .begin(),  vertices_second  .end()  );
 
        return  vertices_first  ==  vertices_second;
    }
    //-----------------------------------------------------------------------------------
    void    inc_cur_vert()
    {
        auto    cur_side    =   T_side  (
                                            cur_vert_,
                                            cur_triangle_directive_vert_
                                        );
 
        if  (
                !successfully_cur_side_intersects_other_triangle_and_set_cur_vert_data( cur_side )
            )
        {
            cur_vert_   =   cur_triangle_directive_vert_;
 
            for_triangle_with_ind_inc_vert
                (
                    cur_triangle_ind_,
                    cur_triangle_directive_vert_
                );
        }//if
    }
    //-----------------------------------------------------------------------------------
2
Эксперт С++
3211 / 1738 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
27.11.2014, 09:53 4
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
    void    for_triangle_with_ind_inc_vert
        (
            T_first_second_ind      triangle_ind,
            T_point             &   vert
        )
    {
        vert    =   get_const_triangle_ref_with_ind( triangle_ind ).get_next_vert( vert );
    }
    //-----------------------------------------------------------------------------------
    bool    successfully_cur_side_intersects_other_triangle_and_set_cur_vert_data( T_side   const   &   side )
    {
        bool    bool_res                =   false;
        auto    outside_triangle_ind    =   !cur_triangle_ind_;
        auto    outside_begin_side      =   for_triangle_with_ind_get_begin_side( outside_triangle_ind );
        auto    outside_cur_side        =   outside_begin_side;
 
        do
        {
            bool_res    =   successfully_for_cur_side_and_side_set_cur_intersec_vert_data
                                (
                                    side,
                                    outside_cur_side
                                );
 
            if( bool_res )
            {
                return  bool_res;
            }
 
            for_triangle_with_ind_inc_side
                (
                    outside_triangle_ind,
                    outside_cur_side
                );
        }
        while   (
                        outside_cur_side
                    !=  outside_begin_side
                );
 
        return  bool_res;
    }
    //-----------------------------------------------------------------------------------
    T_side  for_triangle_with_ind_get_begin_side( T_first_second_ind    triangle_ind )  const
    {
        return  get_const_triangle_ref_with_ind( triangle_ind ).get_begin_side();
    }
    //-----------------------------------------------------------------------------------
    void    for_triangle_with_ind_inc_side
        (
            T_first_second_ind      triangle_ind,
            T_side              &   side
        )                                                                           const
    {
        side    =   get_const_triangle_ref_with_ind( triangle_ind ).get_next_side( side );
    }
    //-----------------------------------------------------------------------------------
    T_point     for_triangle_with_ind_get_next_vert
        (
            T_first_second_ind              triangle_ind,
            T_point             const   &   vert
        )                                                                           const
    {
        return  get_const_triangle_ref_with_ind( triangle_ind ).get_next_vert( vert );
    }
    //-----------------------------------------------------------------------------------
    bool    successfully_for_cur_side_and_side_set_cur_intersec_vert_data
        (
            T_side  const   &   cur_side_AB,
            T_side  const   &   side_CD
        )
    {
        auto        det_AB_CD   =   det (
                                            cur_side_AB,
                                            side_CD
                                        );
 
        T_point     intersec_point;
 
        bool        bool_res    =       det_AB_CD   >   0
 
                                    &&  successfully_for_sides_set_intersection_point
                                            (
                                                cur_side_AB,
                                                side_CD,
                                                intersec_point
                                            )
 
                                    &&  intersec_point  !=  side_CD.second;
 
        if( bool_res )
        {
            for_cur_side_and_side_and_intersec_point_set_cur_intersec_vert_data
                (
                    cur_side_AB,
                    side_CD,
                    intersec_point
                );
        }//if
 
        return  bool_res;
    }
    //-----------------------------------------------------------------------------------
    void    for_cur_side_and_side_and_intersec_point_set_cur_intersec_vert_data
        (
            T_side      const   &   cur_side_AB,
            T_side      const   &   side_CD,
            T_point     const   &   intersec_point
        )
    {
        auto    cur_triangle_ind_side_or_next_side
            =   for_triangle_with_ind_side_and_intersec_point_get_side_or_next_side
                    (
                        cur_triangle_ind_,
                        cur_side_AB,
                        intersec_point
                    );
 
        auto    not_cur_triangle_ind_side_or_next_side
            =   for_triangle_with_ind_side_and_intersec_point_get_side_or_next_side
                    (
                        !cur_triangle_ind_,
                        side_CD,
                        intersec_point
                    );
 
        auto    det_cur_and_not_cur     =   det (
                                                    cur_triangle_ind_side_or_next_side,
                                                    not_cur_triangle_ind_side_or_next_side
                                                );
 
        cur_vert_   =   intersec_point;
 
        cur_triangle_directive_vert_    =   det_cur_and_not_cur     >   0
                                                ?   not_cur_triangle_ind_side_or_next_side  .second
                                                :   cur_triangle_ind_side_or_next_side      .second;
 
        if( det_cur_and_not_cur     >   0 )
        {
            cur_triangle_ind_           =   !cur_triangle_ind_;
        }
    }
    //-----------------------------------------------------------------------------------
    T_side  for_triangle_with_ind_side_and_intersec_point_get_side_or_next_side
        (
            T_first_second_ind              triangle_ind,
            T_side              const   &   side,
            T_point             const   &   intersec_point
        )                                                                           const
    {
        return  for_triangle_with_ind_is_vert
                    (
                        triangle_ind,
                        intersec_point
                    )
 
                    ?   for_triangle_with_ind_get_side_goes_from_vert
                            (
                                triangle_ind,
                                intersec_point
                            )
 
                    :   side;
    }
    //-----------------------------------------------------------------------------------
    bool    for_triangle_with_ind_is_vert
        (
            T_first_second_ind              triangle_ind,
            T_point             const   &   intersec_point
        )                                                                           const
    {
        return  get_const_triangle_ref_with_ind( triangle_ind ).is_vert( intersec_point );
    }
    //-----------------------------------------------------------------------------------
    T_triangle  const   &  get_const_triangle_ref_with_ind( T_first_second_ind   triangle_ind )     const
    {
        return  triangles_[ triangle_ind ];
    }
    //-----------------------------------------------------------------------------------
    T_side  for_triangle_with_ind_get_side_goes_from_vert
        (
            T_first_second_ind              triangle_ind,
            T_point             const   &   vert
        )                                                                           const
    {
        return  get_const_triangle_ref_with_ind( triangle_ind ).get_side_goes_from_vert( vert );
    }
    //-----------------------------------------------------------------------------------
    void    cur_vert_go_to_next_vert_in_triangle_with_ind( T_first_second_ind      triangle_ind )
    {
        for_triangle_with_ind_inc_vert
            (
                triangle_ind,
                cur_vert_
            );
    }
    //-----------------------------------------------------------------------------------
    T_point     for_triangle_with_ind_get_begin_vert( T_first_second_ind    triangle_ind )  const
    {
        return  get_const_triangle_ref_with_ind( triangle_ind ).begin_vert();
    }
    //-----------------------------------------------------------------------------------
    bool    successfully_set_first_cur_vert_data()
    {
        return      successfully_set_first_cur_vert_data_as_sides_intersection_not_side_end                             ()
                ||  successfully_set_first_cur_vert_data_as_located_inside_triangle                                     ()
                ||  successfully_set_first_cur_vert_data_as_begin_vert_of_side_middle_of_which_lies_inside_triangle     ();
    }
    //-----------------------------------------------------------------------------------
    bool    successfully_set_first_cur_vert_data_as_begin_vert_of_side_middle_of_which_lies_inside_triangle()
    {
        return
            successfully_set_first_cur_vert_data_as_begin_vert_of_side_middle_of_which_lies_inside_triangle_with_ind( first  )
        ||  successfully_set_first_cur_vert_data_as_begin_vert_of_side_middle_of_which_lies_inside_triangle_with_ind( second );
    }
    //-----------------------------------------------------------------------------------
2
Эксперт С++
3211 / 1738 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
27.11.2014, 09:54 5
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
    bool    successfully_set_first_cur_vert_data_as_begin_vert_of_side_middle_of_which_lies_inside_triangle_with_ind
        ( T_first_second_ind    outside_triangle_ind )
    {
        bool    bool_res                =   false;
        auto    inside_triangle_ind     =   !outside_triangle_ind;
 
        auto    inside_begin_side       =   for_triangle_with_ind_get_begin_side( inside_triangle_ind );
        auto    inside_cur_side         =   inside_begin_side;
 
        do
        {
            bool_res    =   middle_of_side_is_inside_triangle_with_ind
                                (
                                    inside_cur_side,
                                    outside_triangle_ind
                                );
 
            if( bool_res )
            {
                cur_vert_                       =   inside_cur_side.first;
                cur_triangle_directive_vert_    =   inside_cur_side.second;
                cur_triangle_ind_               =   inside_triangle_ind;
                return  bool_res;
            }
 
            for_triangle_with_ind_inc_side
                (
                    inside_triangle_ind,
                    inside_cur_side
                );
        }
        while   (
                        inside_cur_side
                    !=  inside_begin_side
                );
 
        return  bool_res;
    }
    //-----------------------------------------------------------------------------------
    bool    middle_of_side_is_inside_triangle_with_ind
        (
            T_side              const   &   side,
            T_first_second_ind              outside_triangle_ind
        )                                                                           const
    {
        auto    middle_point    =   (
                                            side.first
                                        +   side.second
                                    )
                                    / 2.0;
 
        return  get_const_triangle_ref_with_ind( outside_triangle_ind ).point_is_inside( middle_point );
    }
    //-----------------------------------------------------------------------------------
    bool    successfully_set_first_cur_vert_data_as_sides_intersection_not_side_end()
    {
        bool    bool_res                    =   false;
        auto    triangle_first_start_side   =   for_triangle_with_ind_get_begin_side( first );
        auto    triangle_first_cur_side     =   triangle_first_start_side;
 
        do
        {
            auto    triangle_second_start_side  =   for_triangle_with_ind_get_begin_side( second );
            auto    triangle_second_cur_side    =   triangle_second_start_side;
 
            do
            {
                T_point     intersec_point;
 
                bool_res    =   successfully_for_sides_set_intersection_point_not_side_end
                                    (
                                        triangle_first_cur_side,
                                        triangle_second_cur_side,
                                        intersec_point
                                    );
 
                if( bool_res )
                {
                    cur_vert_                       =   intersec_point;
 
                    auto    det_first_second        =   det (
                                                                triangle_first_cur_side,
                                                                triangle_second_cur_side
                                                            );
 
                    if( det_first_second    >   0 )
                    {
                        cur_triangle_ind_               =   second;
                        cur_triangle_directive_vert_    =   triangle_second_cur_side.second;
                    }
                    else
                    {
                        cur_triangle_ind_               =   first;
                        cur_triangle_directive_vert_    =   triangle_first_cur_side.second;
                    }//else
 
                    return  bool_res;
                }//if
 
                for_triangle_with_ind_inc_side
                    (
                        second,
                        triangle_second_cur_side
                    );
            }
            while   (
                        triangle_second_cur_side   !=  triangle_second_start_side
                    );
 
            for_triangle_with_ind_inc_side
                (
                    first,
                    triangle_first_cur_side
                );
        }
        while   (
                    triangle_first_cur_side   !=  triangle_first_start_side
                );
 
        return  bool_res;
    }
    //-----------------------------------------------------------------------------------
    static  bool    successfully_for_sides_set_intersection_point_not_side_end
        (
            T_side  const   &   side_AB,
            T_side  const   &   side_CD,
            T_point         &   intersec_point
        )
    {
        return      successfully_for_sides_set_intersection_point
                        (
                            side_AB,
                            side_CD,
                            intersec_point
                        )
 
                &&  intersec_point  !=  side_AB.first
                &&  intersec_point  !=  side_AB.second
                &&  intersec_point  !=  side_CD.first
                &&  intersec_point  !=  side_CD.second;
    }
    //-----------------------------------------------------------------------------------
    bool    successfully_set_first_cur_vert_data_as_located_inside_triangle()
    {
        return      successfully_set_first_cur_vert_data_as_located_inside_triangle_with_ind( first      )
                &&  successfully_set_first_cur_vert_data_as_located_inside_triangle_with_ind( second     );
    }
    //-----------------------------------------------------------------------------------
    bool    successfully_set_first_cur_vert_data_as_located_inside_triangle_with_ind
        ( T_first_second_ind    outside_triangle_ind )
    {
        bool    bool_res                =   false;
        auto    inside_triangle_ind     =   !outside_triangle_ind;
        cur_vert_                       =   for_triangle_with_ind_get_begin_vert( inside_triangle_ind );
 
        do
        {
            bool_res        =   cur_vert_is_inside_triangle_with_ind( outside_triangle_ind );
 
            if( bool_res )
            {
                cur_triangle_ind_               =   inside_triangle_ind;
 
                cur_triangle_directive_vert_    =   for_triangle_with_ind_get_next_vert
                                                        (
                                                            cur_triangle_ind_,
                                                            cur_vert_
                                                        );
 
                return  bool_res;
            }//if
 
            cur_vert_go_to_next_vert_in_triangle_with_ind( inside_triangle_ind );
        }
        while   (
                    cur_vert_   !=  for_triangle_with_ind_get_begin_vert( inside_triangle_ind )
                );
 
        return  bool_res;
    }
    //-----------------------------------------------------------------------------------
    bool    cur_vert_is_inside_triangle_with_ind( T_first_second_ind    triangle_ind )  const
    {
        return  get_const_triangle_ref_with_ind( triangle_ind ).point_is_inside( cur_vert_ );
    }
    //-----------------------------------------------------------------------------------
};
/////////////////////////////////////////////////////////////////////////////////////////
int     main()
{
    std::locale::global(std::locale(""));
 
    for(;;)
    {
        std::cout   <<  std::endl
                    <<  std::endl
                    <<  std::endl
                    <<  std::endl
                    <<  std::endl
                    <<  std::endl
                    <<  std::endl
                    <<  std::endl
                    <<  "Введите координаты вершин двух треугольников в формате (x, y):"
                    <<  std::endl;
 
        T_triangle  triangle_1;
        T_triangle  triangle_2;
 
        triangle_1.input_vertices_with_triangle_name( "треугольник 1:" );
        triangle_2.input_vertices_with_triangle_name( "треугольник 2:" );
 
        T_intersection_contour  intersection_contour
                                    (
                                        triangle_1,
                                        triangle_2
                                    );
 
        intersection_contour.fill_vertices      ();
        intersection_contour.print_vertices     ();
    }//for
}
2
_Ivana
28.11.2014, 01:51
  #6

Не по теме:

Вот это сильный ответ, это я понимаю! :) Плюсую многозначно :)

0
С чаем беда...
Эксперт CЭксперт С++
9445 / 4938 / 1351
Регистрация: 18.10.2014
Сообщений: 11,504
28.11.2014, 04:30 7
Цитата Сообщение от SnakeLight Посмотреть сообщение
контур пересечения двух треугольников
Для пересечения любых выпуклых многоугольников прекрасно работает алгоритм последовательного отсечения

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
#include <cassert>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
 
typedef int coord_t;
typedef long long coord2_t;
 
struct pnt_t
{
  coord_t x, y;
 
  friend pnt_t operator -(const pnt_t &lhs, const pnt_t &rhs)
  {
    pnt_t delta = { lhs.x - rhs.x, lhs.y - rhs.y };
    return delta;
  }
 
  friend bool operator <(const pnt_t &lhs, const pnt_t &rhs)
  {
    return lhs.y < rhs.y || (lhs.y == rhs.y && lhs.x < rhs.x);
  }
 
  friend bool operator ==(const pnt_t &lhs, const pnt_t &rhs)
  {
    return lhs.x == rhs.x && lhs.y == rhs.y;
  }
 
  friend bool operator !=(const pnt_t &lhs, const pnt_t &rhs)
  {
    return !(lhs == rhs);
  }
};
 
typedef vector<pnt_t> poly_t;
 
inline coord2_t determinant(const pnt_t &v1, const pnt_t &v2)
{
  return (coord2_t) v1.x * v2.y - (coord2_t) v1.y * v2.x;
}
 
bool is_ccw(const poly_t &poly)
{
  assert(poly.size() >= 3);
  poly_t::const_iterator it_ll = min_element(poly.begin(), poly.end());
  poly_t::const_iterator it_prev = it_ll != poly.begin() ? it_ll - 1 : poly.end() - 1;
  poly_t::const_iterator it_next = it_ll != poly.end() - 1 ? it_ll + 1 : poly.begin();
  return determinant(*it_next - *it_ll, *it_prev - *it_ll) > 0;
}
 
bool intersect(const pnt_t &a1, const pnt_t &b1, const pnt_t &a2, const pnt_t &b2, pnt_t &p)
{
  assert(a1 != b1 && a2 != b2);
 
  pnt_t delta1 = b1 - a1, delta2 = b2 - a2;
  coord2_t det = determinant(delta1, delta2);
  if (det == 0)
    return false;
 
  coord2_t 
    det1 = determinant(a1, b1), 
    det2 = determinant(a2, b2);
  coord2_t 
    num_x = det2 * delta1.x - det1 * delta2.x,
    num_y = det2 * delta1.y - det1 * delta2.y;
 
  p.x = (coord_t) (num_x / det);
  p.y = (coord_t) (num_y / det);
  return true;
}
 
inline void push_point(poly_t &poly, const pnt_t& p)
{
  if (poly.empty() || poly.back() != p)
    poly.push_back(p);
}
 
poly_t intersect_polys(const poly_t &poly1, const poly_t &poly2)
{
  assert(poly1.size() >= 3 && poly2.size() >= 3);
  assert(is_ccw(poly1) && is_ccw(poly2));
 
  poly_t cut = poly1;
 
  for (poly_t::const_iterator it_line_a = poly2.end() - 1, it_line_b = poly2.begin(); 
       it_line_b != poly2.end(); 
       it_line_a = it_line_b++)
  {
    coord2_t A = -(it_line_b->y - it_line_a->y);
    coord2_t B = it_line_b->x - it_line_a->x;
    coord2_t C = -(A * it_line_b->x + B * it_line_b->y);
 
    poly_t cut_result;
 
    for (poly_t::const_iterator it_side_a = cut.end() - 1, it_side_b = cut.begin(); 
         it_side_b != cut.end();
         it_side_a = it_side_b++)
    {
      coord2_t sign_a = A * it_side_a->x + B * it_side_a->y + C;
      coord2_t sign_b = A * it_side_b->x + B * it_side_b->y + C;
 
      if (sign_a >= 0)
        push_point(cut_result, *it_side_a);
 
      if (sign_a != 0 && sign_b != 0 && (sign_a > 0) != (sign_b > 0))
      {
        pnt_t p;
        bool is_intersect = intersect(*it_side_a, *it_side_b, *it_line_a, *it_line_b, p);
        assert(is_intersect);
        push_point(cut_result, p);
      }
    }
 
    cut = cut_result;
    if (cut.size() < 3)
      break;
  }
 
  if (!cut.empty() && cut.back() == cut.front())
    cut.pop_back();
 
  if (cut.size() < 3)
    cut.clear();
 
  return cut;
} 
 
void normalize_poly(poly_t &poly)
{
  poly.resize(unique(poly.begin(), poly.end()) - poly.begin());
  if (!poly.empty() && poly.back() == poly.front())
    poly.pop_back();
 
  if (!poly.empty() && !is_ccw(poly))
    reverse(poly.begin(), poly.end());
}
 
int main()
{
  const pnt_t T1[] = { { 0, 0 }, { 40, 20 }, { 20, 40 } };
  poly_t t1(T1, T1 + sizeof T1 / sizeof *T1);
  normalize_poly(t1);
 
  const pnt_t T2[] = { { 20, 0 }, { 0, 20 }, { 40, 40 } };
  poly_t t2(T2, T2 + sizeof T2 / sizeof *T2);
  normalize_poly(t2);
 
  poly_t intersection = intersect_polys(t1, t2);
 
  if (!intersection.empty())
  {
    cout << "{ { " << intersection[0].x << ", " << intersection[0].y << " }";
    for (poly_t::size_type i = 1; i < intersection.size(); ++i)
      cout << ", { " << intersection[i].x << ", " << intersection[i].y << " }";
    cout << " }" << endl;
  }
  else
    cout << "Пересечение пусто" << endl;
}
1
Эксперт С++
3211 / 1738 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
30.11.2014, 09:39 8
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
алгоритм последовательного отсечения
Если честно, я специально не стал заглядывать в существующие алгоритмы, хотелось самому покумекать. И наверно додумался бы и до отсечения, но надоело.
А что это у вас за целые координаты, это несерьезно. И что это вы написали вместо сортировки вершин против часовой стрелки? Для числа вершин больше трех это не работает.
Мой вариант:
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
/////////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <complex>
#include <functional>
#include <iostream>
#include <iterator>
#include <limits>
#include <numeric>
#include <string>
#include <utility>
#include <vector>
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::string                                 T_str;
typedef double                                      T_coord;
typedef std::complex    < T_coord               >   T_point;
typedef std::vector     < T_point               >   T_points;
typedef std::pair       < T_point,  T_point     >   T_side;
/////////////////////////////////////////////////////////////////////////////////////////
bool    operator==
    (
        T_point     const   &   L,
        T_point     const   &   R
    )
{
    static  const   auto    factor      =   1000;
    static  const   auto    eps         =   std::numeric_limits< T_coord >::epsilon();
 
    auto                    max_abs     =   std::max    (
                                                            abs(L),
                                                            abs(R)
                                                        );
 
    auto                    delta       =       ( 1 + max_abs )
                                            *   eps
                                            *   factor;
 
    return  abs( L - R )    <   delta;
}
/////////////////////////////////////////////////////////////////////////////////////////
T_point     vect
    (
        T_point     const   &   A,
        T_point     const   &   B
    )
{
    return  B   -   A;
}
/////////////////////////////////////////////////////////////////////////////////////////
T_point     vect( T_side  const   &   side )
{
    return      side.second
            -   side.first;
}
/////////////////////////////////////////////////////////////////////////////////////////
T_coord     det
    (
        T_point     const   &   M,
        T_point     const   &   N
    )
{
    return      M.real()    *   N.imag()
            -   M.imag()    *   N.real();
}
/////////////////////////////////////////////////////////////////////////////////////////
class   T_polygon
{
    //-----------------------------------------------------------------------------------
    T_points    vertices_;
    //-----------------------------------------------------------------------------------
public:
    //-----------------------------------------------------------------------------------
    void    inc_vert( T_point   &   vert )
    {
        vert    =   get_next_vert( vert );
    }
    //-----------------------------------------------------------------------------------
    void    if_is_vert_push_vert
        (
            T_point   const   &   v,
            T_point   const   &   w
        )
    {
        if  (
                    !vertices_.empty    ()
                &&  is_vert             (v)
            )
        {
            push_if_is_not_vert(w);
        }
    }
    //-----------------------------------------------------------------------------------
    void    push_if_is_not_vert( T_point   const   &   vert )
    {
        if  (
                    vertices_.empty     ()
                ||  !is_vert            (vert)
            )
        {
            vertices_.push_back(vert);
        }
    }
    //-----------------------------------------------------------------------------------
    void    print_vertices()                                                        const
    {
        std::copy
            (
                vertices_.begin                     (),
                vertices_.end                       (),
                std::ostream_iterator< T_point >    ( std::cout,    "\t" )
            );
    }
    //-----------------------------------------------------------------------------------
    bool    empty()                                                                 const
    {
        return  vertices_.empty();
    }
    //-----------------------------------------------------------------------------------
    T_side  get_begin_side()                                                        const
    {
        return  T_side  (
                            vertices_       .front(),
                            *++vertices_    .begin()
                        );
    }
    //-----------------------------------------------------------------------------------
    void    inc_side( T_side    &   side )                                          const
    {
        side    =   T_side  (
                                side.second,
                                get_next_vert( side.second )
                            );
    }
    //-----------------------------------------------------------------------------------
    bool    is_vert( T_point    const   &   point )                                 const
    {
        return      std::find   (
                                    vertices_.begin     (),
                                    vertices_.end       (),
                                    point
                                )
 
                !=  vertices_.end();
    }
    //-----------------------------------------------------------------------------------
    T_point     begin_vert()                                                        const
    {
        return  vertices_.front();
    }
    //-----------------------------------------------------------------------------------
    T_point     get_next_vert( T_point  const   &   v )                             const
    {
        auto    it      =   std::find
                                (
                                    vertices_.begin  (),
                                    vertices_.end    (),
                                    v
                                );
 
        auto    ind     =   std::distance
                                (
                                    vertices_.begin(),
                                    it
                                );
 
        ++ind   %=  vertices_.size();
        return  vertices_[ ind ];
    }
    //-----------------------------------------------------------------------------------
    void    input_vertices_with_polygon_name( T_str    const   &   polygon_name )
    {
        static  const   int     MIN_VERT_COUNT  =   3;
 
        int     vert_count  =   0;
        do
        {
            std::cout   <<  "Введите количество вершин в многоугольнике "
                        <<  polygon_name
                        <<  ": ";
 
            std::cin    >>  vert_count;
        }
        while( vert_count   <   MIN_VERT_COUNT );
 
        std::cout   <<  std::endl
                    <<  "Введите "
                    <<  vert_count
                    <<  " вершин в многоугольник "
                    <<  polygon_name
                    <<  ":"
                    <<  std::endl;
 
        for( int  i = 0; i < vert_count; ++i )
        {
            T_point     cur_vert;
 
            do
            {
                std::cout   <<  '\t'
                            <<  "вершина #"
                            <<  i + 1
                            <<  "\t: ";
 
                std::cin    >>  cur_vert;
            }
            while   (
                            !vertices_.empty    ()
                        &&  is_vert             ( cur_vert )
                    );
 
            std::cout   <<  std::endl;
            vertices_.push_back( cur_vert );
        }//for
 
        std::cout   <<  std::endl;
        arrange_vertices_counterclockwise();
    }
    //-----------------------------------------------------------------------------------
private:
    //-----------------------------------------------------------------------------------
    void    arrange_vertices_counterclockwise()
    {
        auto    center_point    =   std::accumulate
                                        (
                                            vertices_.begin     (),
                                            vertices_.end       (),
                                            T_point             ()
                                        );
 
        center_point    /=  vertices_.size();
 
        std::sort
            (
                vertices_.begin     (),
                vertices_.end       (),
 
                [=]                 (
                                        T_point     &   L,
                                        T_point     &   R
                                    )
                {
                    return      std::arg( L     -   center_point )
                            <   std::arg( R     -   center_point );
                }
            );
    }
    //-----------------------------------------------------------------------------------
};
/////////////////////////////////////////////////////////////////////////////////////////
1
Эксперт С++
3211 / 1738 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
30.11.2014, 09:40 9
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
T_point     get_intersec_point_for_line_of_side_and_side
    (
        T_side  const   &   side_AB_for_line,
        T_side  const   &   side_CD
    )
{
    bool    bool_res    =   false;
 
    //Находим точку R пересечения прямых, задаваемых векторами AB и CD.
    //R = A + AB * x
    //R = C + CD * y
    //A + AB * x = C + CD * y
    //AB * x - CD * y = C - A
    //
    //AB * x - CD * y = AC
 
    auto    vect_AB     =   vect( side_AB_for_line  );
    auto    vect_CD     =   vect( side_CD           );
 
    auto    vect_AC     =   vect    (
                                        side_AB_for_line    .first,
                                        side_CD             .first
                                    );
 
    auto    main_det    =   det (
                                    vect_AB,
                                    -vect_CD
                                );
 
    auto    det_X       =   det (
                                    vect_AC,
                                    -vect_CD
                                );
 
    auto    X           =   det_X / main_det;
 
    auto    det_Y       =   det (
                                    vect_AB,
                                    vect_AC
                                );
 
    auto    Y           =   det_Y / main_det;
 
    return      side_AB_for_line.first
            +   X   *   vect_AB;
}
/////////////////////////////////////////////////////////////////////////////////////////
class   T_intersection_contour
{
    //-----------------------------------------------------------------------------------
    T_polygon           polygon_in_;
    T_polygon           polygon_out_;
    T_polygon           polygon_res_;
    //-----------------------------------------------------------------------------------
public:
    //-----------------------------------------------------------------------------------
    T_intersection_contour
        (
            T_polygon  const   &   polygon_1,
            T_polygon  const   &   polygon_2
        )
        :
        polygon_in_     ( polygon_1 ),
        polygon_out_    ( polygon_2 )
    {}
    //-----------------------------------------------------------------------------------
    bool    empty()
    {
        return  polygon_res_.empty();
    }
    //-----------------------------------------------------------------------------------
    void    swap_polygons()
    {
        std::swap   (
                        polygon_in_,
                        polygon_out_
                    );
    }
    //-----------------------------------------------------------------------------------
    void    fill_vertices()
    {
        polygon_res_            =   polygon_in_;
        auto    begin_out_side  =   polygon_out_.get_begin_side();
        auto    cur_out_side    =   begin_out_side;
 
        do
        {
            to_clip_polygon_with_side
                (
                    polygon_res_,
                    cur_out_side
                );
 
            polygon_out_.inc_side( cur_out_side );
        }
        while   (
                        cur_out_side
                    !=  begin_out_side
                );
    }
    //-----------------------------------------------------------------------------------
    void    print_vertices()                                                        const
    {
        if  (
                polygon_res_.empty()
            )
        {
            std::cout   <<  "Многоугольники не пересекаются."
                        <<  std::endl;
        }
        else
        {
            std::cout   <<  "Контур пересечения многоугольников состоит из точек:"
                        <<  std::endl;
 
            polygon_res_.print_vertices();
        }
    }
    //-----------------------------------------------------------------------------------
private:
    //-----------------------------------------------------------------------------------
    void    to_clip_polygon_with_side
        (
            T_polygon           &   polygon,
            T_side      const   &   side
        )
    {
        if  (
                polygon.empty()
            )
        {
            return;
        }
 
        T_polygon   res_polygon;
        auto        begin_vert          =   polygon.begin_vert();
 
        auto        det_to_begin_vert   =   det (
                                                    vect    ( side ),
 
                                                    vect    (
                                                                side.first,
                                                                begin_vert
                                                            )
                                                );
 
        if( det_to_begin_vert   >   0 )
        {
            res_polygon.push_if_is_not_vert( begin_vert );
        }
 
        auto    cur_vert    =   begin_vert;
 
        do
        {
            auto    next_vert   =   polygon.get_next_vert( cur_vert );
 
            auto    cur_side    =   T_side  (
                                                cur_vert,
                                                next_vert
                                            );
 
            auto    det_cur     =   det (
                                            vect    ( side ),
 
                                            vect    (
                                                        side.first,
                                                        cur_vert
                                                    )
                                        );
 
            auto    det_next    =   det (
                                            vect    ( side ),
 
                                            vect    (
                                                        side.first,
                                                        next_vert
                                                    )
                                        );
 
            if( det_cur     >   0 )
            {
                if( det_next    >=  0 )
                {
                    //Изнутри внутрь или на прямую.
                    res_polygon.push_if_is_not_vert( next_vert );
                }
                else if( det_next    <  0 )
                {
                    //Изнутри наружу.
                    res_polygon.push_if_is_not_vert
                        (
                            get_intersec_point_for_line_of_side_and_side
                                (
                                    side,
                                    cur_side
                                )
                        );
                }//else
            }
            else if( det_cur     <   0 )
            {
                if( det_next    >  0 )
                {
                    //Извне внутрь.
                    res_polygon.push_if_is_not_vert
                        (
                            get_intersec_point_for_line_of_side_and_side
                                (
                                    side,
                                    cur_side
                                )
                        );
 
                    res_polygon.push_if_is_not_vert( next_vert );
                }
                //Извне на прямую и наружу - ничего не добавляем.
            }
            else//С прямой.
            {
                //С прямой внутрь.
                if( det_next    >  0 )
                {
                    res_polygon.push_if_is_not_vert( cur_vert   );
                    res_polygon.push_if_is_not_vert( next_vert  );
                }
                else if( det_next   ==  0 )
                {
                    //С прямой  на прямую.
                    res_polygon.if_is_vert_push_vert
                        (
                            cur_vert,
                            next_vert
                        );
                }
            }//else
            //С прямой наружу - ничего не добавляем.
 
            polygon.inc_vert( cur_vert );
        }
        while   (
                    cur_vert    !=  begin_vert
                );
 
        polygon     =   res_polygon;
    }
    //-----------------------------------------------------------------------------------
};
/////////////////////////////////////////////////////////////////////////////////////////
int     main()
{
    std::locale::global(std::locale(""));
 
    for(;;)
    {
        std::cout   <<  std::endl
                    <<  std::endl
                    <<  std::endl
                    <<  std::endl
                    <<  std::endl
                    <<  std::endl
                    <<  std::endl
                    <<  std::endl
                    <<  "Введите координаты вершин двух выпуклых многоугольников в формате (x, y):"
                    <<  std::endl;
 
        T_polygon  polygon_1;
        T_polygon  polygon_2;
 
        polygon_1.input_vertices_with_polygon_name( "1" );
        polygon_2.input_vertices_with_polygon_name( "2" );
 
        T_intersection_contour  intersection_contour
                                    (
                                        polygon_1,
                                        polygon_2
                                    );
 
        intersection_contour.fill_vertices();
 
        if  (
                intersection_contour.empty()
            )
        {
            intersection_contour.swap_polygons  ();
            intersection_contour.fill_vertices  ();
        }
 
        intersection_contour.print_vertices     ();
    }//for
}
1
С чаем беда...
Эксперт CЭксперт С++
9445 / 4938 / 1351
Регистрация: 18.10.2014
Сообщений: 11,504
30.11.2014, 10:31 10
Цитата Сообщение от Mr.X Посмотреть сообщение
А что это у вас за целые координаты, это несерьезно
Ни в коем случае. Вся практическая вычислительная геометрия - строго целые числа. При этом понтяно, конечно, что целые числа могут являться ни чем иным, как представлением с фиксированной точкой. Т.е. дело тут не столько в целости, сколько в равномерности покрытия всего координатного пространства.

За использование плавающих типов - сразу линейкой по рукам. Именно плавающие типы - это несерьезно. Плавающие типы в такой ситуации сразу выдают аффтара, который не знал, как справиться с арифметическим переполнением и наивно решил просто воспользоваться плавающими типами, потому что они "не переполняются". Искусство алгоритмической вычислительной геометрии - это именно искусство решения геометрических задач на целых числах.

Цитата Сообщение от Mr.X Посмотреть сообщение
И что это вы написали вместо сортировки вершин против часовой стрелки? Для числа вершин больше трех это не работает.
"Сортировка"? Нет, никакой "стортировки" там нет. Это не "сортировка" против часовой, это распознавание одного из двух вариантов - "по часовой" или "против часовой" - (работающее для любого простого многоугольника) и приведение многоугольника именно к варианту "против часовой".
1
2 / 2 / 0
Регистрация: 23.09.2008
Сообщений: 54
02.12.2014, 17:58  [ТС] 11
Помогите пожалуйста, какую функцию можно протестировать из этого кода, я уже все перепробовал, но ничего не выходит :-( . С помощью (модульного тестирования) Assert:Equal();
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
02.12.2014, 17:58

Вычислить площади двух треугольников, и определить, какой из треугольников имеет большую площадь
Два треугольника заданные координатами своих вершин a, b, c. Вычислить площади треугольников,...

Линия пересечения треугольников
Здравствуйте! Есть 2 треугольника в пространстве заданные координатами вершин. 1) Не силён в...

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

Производительность труда q описывается выражением q(t)=dQ/dt=-t+2t+40, где Q – функция, рассчитывающая количество продукции, t – время в часах 1≤t≤8.
Производительность труда q описывается выражением q(t)=dQ/dt=-t+2t+40, где Q – функция,...

Найти наибольшее возможное число треугольников, вершины которых являются точками пересечения этих прямых и не совпадаю
На плоскости даны три точки А, В и С. Через точки А, В и С проведены пучки соответственно из m, n,...

*на зачете*Даны длины двух сторон и угла между ними для двух треугольников.Определить больший по площади треугольник.Выч.пл.треуг.оформ. Ввиде ФУНКЦИИ
*на зачете*Даны длины двух сторон и угла между ними для двух треугольников.Определить больший по...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru