Началось с того, что мне показалось простым делом — «векторно» (не «растрово») объединить многоугольник с треугольником. Вроде, получилось — программу написал — но вышло не совсем просто. Теперь я уже знаю, что я далеко не первый, кто возился с этой задачей, что таких людей очень много. А это значит, что наболело у многих, кто это реализовывал — есть, что обсудить, есть о чем поговорить — особенно, если у меня получилось не очень (вдруг ошибся, хотя я сейчас уверен, что всё работает, как часики) — можно ткнуть в меня вилкой. Задача вообще-то веселая. Приглашаю под кат.
Алгоритм «векторное объединение теней»
Полезные ссылки
Скрытый текст
Пересечение многоугольников:
https://dxdy.ru/post1111898.html (2016)
https://dxdy.ru/topic7343.html (2007)
Булевы операции над многоугольниками
Ф. Препарата, М. Шеймос «Вычислительная геометрия» (1989)
https://lib.ysu.am/disciplines_bk/75186a5fdb0833d59fd09e2aecfd0f3d.pdf
Постановка задачи
Дана тень, ограниченная замкнутой ломаной линией, в виде набора отрезков. Отрезки границы ориентированы – обеспечивая положительный обход тени (тень слева) – начало и конец отрезка задается координатами на плоскости. Однако, отрезки не обязаны быть упорядочены в геометрическом порядке – не обязаны следовать один за другим – другими словами, порядок отрезков в списке – произвольный.
Список отрезков границы №1:
Номер отрезка |
абсцисса начала |
ордината начала |
абсцисса конца |
ордината конца |
1 |
X0_1 |
Y0_1 |
X1_1 |
Y1_1 |
2 |
X0_2 |
Y0_2 |
X1_2 |
Y1_2 |
… |
… |
… |
… |
… |
N |
X0_N |
Y0_N |
X1_N |
Y1_N |
Дана еще одна тень – с одним условием – это треугольник. Список отрезков границы №2:
Номер отрезка |
абсцисса начала |
ордината начала |
абсцисса конца |
ордината конца |
1 |
X0_1 |
Y0_1 |
X1_1 |
Y1_1 |
2 |
X0_2 |
Y0_2 |
X1_2 |
Y1_2 |
3 |
X0_3 |
Y0_3 |
X1_3 |
Y1_3 |
Задача: следует объединить тени, т.е. сформировать Список отрезков границы №3.
Идея алгоритма
Условие для формирования новой границы: в границу объединенных теней (в Список отрезков границы №3) должны попасть только «светлые» участки старых отрезков границ:
Замечание (в сторону булевых операций над многоугольниками): если выбирать только «темные» участки отрезков, по мы получим пересечение теней:
Проблемы «светлых» участков
— Для выявления участков предлагается использовать анализ окрестности точки пересечения отрезков: будем определять «закраску» секторов справа и слева от точки – нам придется накапливать историю пересечения для каждого отрезка из обоих списков и анализировать эту историю после того, как мы пробежали по всем отрезкам и проверили их пересечение.
— для единообразия анализа – будем разбивать отрезок на два – если он «уверенно» пересекает исследуемый отрезок:
— Надо определиться с удалением смежных участков:
— Удаление или оставление всего отрезка: если отрезок ни разу не пересекся, то надо анализировать края отрезка – находятся они внутри или снаружи тени – для этого используем лемму Жордано (в вольном пересказе): «точка принадлежит многоугольнику, если луч, построенный из исследуемой точки, пересекается с границей многоугольника нечетное количество раз» (луч произвольный). При этом нужно учесть «проблему касания»:
— Плавающая точка (погрешность вычисления) – будем вводить эпсилон – расстояние притяжения между близкими точками с последующим слипанием (для определенности мы выбираем слипание в точку, которая прямо содержится в Списке №1 в качестве края отрезка или же точка рассчитана из отрезка Списка №1)
Пересечение двух отрезков: – задаем параметрические прямые, решаем СЛАУ.
-вычисляем:
— если, то
анализируем положение точки решения в плоскости всех возможных пар:
— если, то возможны два случая – или отрезки лежат на двух параллельных прямых (не могут пересечься), или отрезки лежат на одной прямой (тогда и):
Здесь достаточно вычислить четыре значения (выбрав любую ненулевую строку в СЛАУ – допустим, в виде:):
и проанализировать (выбрать их этих четырех не более двух точек).
После чего следует разобраться с оставлением части отрезка, например так:
Детали реализации см. в коде (за код можно прям убивать, вдруг я поумнею):
Скрытый текст
#include <algorithm> #include <math.h> #include <iostream> #include <stdio.h> #include <stdlib.h> #include <cstring> #include <vector> #include <array> #include <fenv.h> #include <time.h> #include <cmath> #include <cstdio> #include <fstream> double interval_point_point(double x, double y, double u, double v){ double r = sqrt(pow((u-x),2) + pow((v-y),2)); return r; } double interval_line_point(double x0, double y0, double x1, double y1, double u, double v){ double r; double ax; double ay; double bx; double by; double mod_a; ax = x1 - x0; ay = y1 - y0; mod_a = sqrt(pow(ax,2) + pow(ay,2)); bx = u - x0; by = v - y0; r = abs(ax*by - ay*bx)/mod_a; return r; } std::vector<std::vector<double>> segments_intersection_point (std::vector<std::vector<double>>seg1, std::vector<std::vector<double>>seg2, double r_point){ double x0 = seg1[0][0]; double y0 = seg1[0][1]; double x1 = seg1[1][0]; double y1 = seg1[1][1]; double u0 = seg2[0][0]; double v0 = seg2[0][1]; double u1 = seg2[1][0]; double v1 = seg2[1][1]; std::vector<double> iio; std::vector<std::vector<double>> points_attributes; // mask: [t_][tau_][cos_][sin_][x_][y_] points_attributes.clear(); double t_; double tau_; double cos_ ; double sin_ ; double x_ ; double y_ ; double ax = x1 - x0; double ay = y1 - y0; double bx = u1 - u0; double by = v1 - v0; double ax_ = x0; double ay_ = y0; double bx_ = u0; double by_ = v0; double cx = bx_ - ax_; double cy = by_ - ay_; double a; double b; double c; double det_0 = - ax*by + ay*bx; double det_t = - cx*by + cy*bx; double det_tau = ax*cy - ay*cx; double r_a = sqrt( ax*ax+ay*ay ); double r_b = sqrt( bx*bx+by*by ); if (abs(det_0/r_a)<r_point){ if(abs(det_t/r_b)<r_point && abs(det_tau/r_a)<r_point ){ a = ax; b = bx; c = cx; if(a == 0.0){ a = ay; b = by; c = cy; } cos_ = 1.0; if (b/a < 0.0){cos_ = -1.0;}; sin_ = 0.0; t_ = 0.0; tau_ = -c/b; x_ = bx*tau_ + bx_; y_ = by*tau_ + by_; if ( interval_point_point(x0,y0,u0,v0)<r_point ){ tau_ = 0.0; x_ = u0; y_ = v0; }; if ( interval_point_point(x0,y0,u1,v1)<r_point ){ tau_ = 1.0; x_ = u1; y_ = v1; }; iio.push_back(t_); // [t_] iio.push_back(tau_); // [tau_] iio.push_back(cos_); // [cos_] iio.push_back(sin_); // [sin_] iio.push_back(x_); // [x_] iio.push_back(y_); // [y_] points_attributes.push_back(iio); iio.clear(); t_ = 1.0; tau_ = (a-c)/b; x_ = bx*tau_ + bx_; y_ = by*tau_ + by_; if ( interval_point_point(x1,y1,u0,v0)<r_point ){ tau_ = 0.0; x_ = u0; y_ = v0; }; if ( interval_point_point(x1,y1,u1,v1)<r_point ){ tau_ = 1.0; x_ = u1; y_ = v1; }; iio.push_back(t_); // [t_] iio.push_back(tau_); // [tau_] iio.push_back(cos_); // [cos_] iio.push_back(sin_); // [sin_] iio.push_back(x_); // [x_] iio.push_back(y_); // [y_] points_attributes.push_back(iio); iio.clear(); tau_ = 0.0; t_ = c/a; if ( interval_point_point(x0,y0,u0,v0)<r_point ){ t_ = 0.0; }; if ( interval_point_point(x1,y1,u0,v0)<r_point ){t_ = 1.0; }; x_ = u0; y_ = v0; iio.push_back(t_); // [t_] iio.push_back(tau_); // [tau_] iio.push_back(cos_); // [cos_] iio.push_back(sin_); // [sin_] iio.push_back(x_); // [x_] iio.push_back(y_); // [y_] points_attributes.push_back(iio); iio.clear(); tau_ = 1.0; t_ = (c+b)/a; if ( interval_point_point(x0,y0,u1,v1)<r_point ){t_ = 0.0; }; if ( interval_point_point(x1,y1,u1,v1)<r_point ){t_ = 1.0; }; x_ = u1; y_ = v1; iio.push_back(t_); // [t_] iio.push_back(tau_); // [tau_] iio.push_back(cos_); // [cos_] iio.push_back(sin_); // [sin_] iio.push_back(x_); // [x_] iio.push_back(y_); // [y_] points_attributes.push_back(iio); iio.clear(); } }else{ t_ = det_t/det_0; if (interval_line_point(u0,v0,u1,v1, x0,y0)<r_point){t_ = 0.0;}; if (interval_line_point(u0,v0,u1,v1, x1,y1)<r_point){t_ = 1.0;}; tau_ = det_tau/det_0; if (interval_line_point(x0,y0,x1,y1, u0,v0)<r_point){tau_ = 0.0;}; if (interval_line_point(x0,y0,x1,y1, u1,v1)<r_point){tau_ = 1.0;}; cos_ = ax*bx + ay*by; sin_ = - det_0; x_ = bx*tau_ + bx_; y_ = by*tau_ + by_; iio.push_back(t_); // [t_] iio.push_back(tau_); // [tau_] iio.push_back(cos_); // [cos_] iio.push_back(sin_); // [sin_] iio.push_back(x_); // [x_] iio.push_back(y_); // [y_] points_attributes.push_back(iio); iio.clear(); }; return points_attributes; } void two_histories(std::vector<std::vector<double>> input_array, std::vector<std::vector<double>>& output_add_array_1, std::vector<std::vector<double>>& output_add_array_2, std::array<int, 2>& Jordano_flag_t, std::array<int, 2>& Jordano_flag_tau ){ std::vector<double> iii; double t_; double tau_; double cos_ ; double sin_ ; double x_ ; double y_ ; if(input_array.size()==1){ t_ = input_array[0][0]; tau_ = input_array[0][1]; cos_ = input_array[0][2]; sin_ = input_array[0][3]; x_ = input_array[0][4]; y_ = input_array[0][5]; if( t_<0.0 ){ if(tau_==0.0){ if(sin_>0.0) {Jordano_flag_t[0] = Jordano_flag_t[0] + 1;} }; if(tau_>0.0 && tau_<1.0){ Jordano_flag_t[0] = Jordano_flag_t[0] + 1; }; if(tau_==1.0){ if(-sin_>0.0) {Jordano_flag_t[0] = Jordano_flag_t[0] + 1;} }; }; if( t_==0.0 ){ if(tau_<0.0){ if(-sin_>0.0) {Jordano_flag_tau[0] = Jordano_flag_tau[0] + 1;} }; if(tau_==0.0){ iii.push_back(t_); // t_ iii.push_back(0.0); // tau_ iii.push_back(cos_); // cos_ iii.push_back(sin_); // sin_ iii.push_back(x_); // x_ iii.push_back(y_); // y_ output_add_array_1.push_back(iii); iii.clear(); iii.push_back(tau_); // tau_ iii.push_back(0.0); // t_ iii.push_back(cos_); // cos_ iii.push_back(-sin_); // sin_ iii.push_back(x_); // x_ iii.push_back(y_); // y_ output_add_array_2.push_back(iii); iii.clear(); }; if(tau_>0.0 && tau_<1.0){ iii.push_back(t_); // t_ iii.push_back(0.0); // tau_ iii.push_back(cos_); // cos_ iii.push_back(sin_); // sin_ iii.push_back(x_); // x_ iii.push_back(y_); // y_ output_add_array_1.push_back(iii); iii.clear(); iii.push_back(t_); // t_ iii.push_back(1.0); // tau_ iii.push_back(-cos_); // cos_ iii.push_back(-sin_); // sin_ iii.push_back(x_); // x_ iii.push_back(y_); // y_ output_add_array_1.push_back(iii); iii.clear(); iii.push_back(tau_); // tau_ iii.push_back(0.0); // t_ iii.push_back(cos_); // cos_ iii.push_back(-sin_); // sin_ iii.push_back(x_); // x_ iii.push_back(y_); // y_ output_add_array_2.push_back(iii); iii.clear(); }; if(tau_==1.0){ iii.push_back(t_); // t_ iii.push_back(1.0); // tau_ iii.push_back(-cos_); // cos_ iii.push_back(-sin_); // sin_ iii.push_back(x_); // x_ iii.push_back(y_); // y_ output_add_array_1.push_back(iii); iii.clear(); iii.push_back(tau_); // tau_ iii.push_back(0.0); // t_ iii.push_back(cos_); // cos_ iii.push_back(-sin_); // sin_ iii.push_back(x_); // x_ iii.push_back(y_); // y_ output_add_array_2.push_back(iii); iii.clear(); }; if(tau_>1.0){ if(-sin_>0.0) {Jordano_flag_tau[1] = Jordano_flag_tau[1] + 1;} }; }; if( t_>0.0 && t_<1.0 ){ if(tau_<0.0){ Jordano_flag_tau[0] = Jordano_flag_tau[0] + 1; }; if(tau_==0.0){ iii.push_back(t_); // t_ iii.push_back(0.0); // tau_ iii.push_back(cos_); // cos_ iii.push_back(sin_); // sin_ iii.push_back(x_); // x_ iii.push_back(y_); // y_ output_add_array_1.push_back(iii); iii.clear(); iii.push_back(tau_); // tau_ iii.push_back(0.0); // t_ iii.push_back(cos_); // cos_ iii.push_back(-sin_); // sin_ iii.push_back(x_); // x_ iii.push_back(y_); // y_ output_add_array_2.push_back(iii); iii.clear(); iii.push_back(tau_); // tau_ iii.push_back(1.0); // t_ iii.push_back(-cos_); // cos_ iii.push_back(sin_); // sin_ iii.push_back(x_); // x_ iii.push_back(y_); // y_ output_add_array_2.push_back(iii); iii.clear(); }; if(tau_>0.0 && tau_<1.0){ iii.push_back(t_); // t_ iii.push_back(0.0); // tau_ iii.push_back(cos_); // cos_ iii.push_back(sin_); // sin_ iii.push_back(x_); // x_ iii.push_back(y_); // y_ output_add_array_1.push_back(iii); iii.clear(); iii.push_back(t_); // t_ iii.push_back(1.0); // tau_ iii.push_back(-cos_); // cos_ iii.push_back(-sin_); // sin_ iii.push_back(x_); // x_ iii.push_back(y_); // y_ output_add_array_1.push_back(iii); iii.clear(); iii.push_back(tau_); // tau_ iii.push_back(0.0); // t_ iii.push_back(cos_); // cos_ iii.push_back(-sin_); // sin_ iii.push_back(x_); // x_ iii.push_back(y_); // y_ output_add_array_2.push_back(iii); iii.clear(); iii.push_back(tau_); // tau_ iii.push_back(1.0); // t_ iii.push_back(-cos_); // cos_ iii.push_back(sin_); // sin_ iii.push_back(x_); // x_ iii.push_back(y_); // y_ output_add_array_2.push_back(iii); iii.clear(); }; if(tau_==1.0){ iii.push_back(t_); // t_ iii.push_back(1.0); // tau_ iii.push_back(-cos_); // cos_ iii.push_back(-sin_); // sin_ iii.push_back(x_); // x_ iii.push_back(y_); // y_ output_add_array_1.push_back(iii); iii.clear(); iii.push_back(tau_); // tau_ iii.push_back(0.0); // t_ iii.push_back(cos_); // cos_ iii.push_back(-sin_); // sin_ iii.push_back(x_); // x_ iii.push_back(y_); // y_ output_add_array_2.push_back(iii); iii.clear(); iii.push_back(tau_); // tau_ iii.push_back(1.0); // t_ iii.push_back(-cos_); // cos_ iii.push_back(sin_); // sin_ iii.push_back(x_); // x_ iii.push_back(y_); // y_ output_add_array_2.push_back(iii); iii.clear(); }; if(tau_>1.0){ Jordano_flag_tau[1] = Jordano_flag_tau[1] + 1; }; }; if( t_==1.0 ){ if(tau_<0.0){ if(sin_>0.0) {Jordano_flag_tau[0] = Jordano_flag_tau[0] + 1;} }; if(tau_==0.0){ iii.push_back(t_); // t_ iii.push_back(0.0); // tau_ iii.push_back(cos_); // cos_ iii.push_back(sin_); // sin_ iii.push_back(x_); // x_ iii.push_back(y_); // y_ output_add_array_1.push_back(iii); iii.clear(); iii.push_back(tau_); // tau_ iii.push_back(1.0); // t_ iii.push_back(-cos_); // cos_ iii.push_back(sin_); // sin_ iii.push_back(x_); // x_ iii.push_back(y_); // y_ output_add_array_2.push_back(iii); iii.clear(); }; if(tau_>0.0 && tau_<1.0){ iii.push_back(t_); // t_ iii.push_back(0.0); // tau_ iii.push_back(cos_); // cos_ iii.push_back(sin_); // sin_ iii.push_back(x_); // x_ iii.push_back(y_); // y_ output_add_array_1.push_back(iii); iii.clear(); iii.push_back(t_); // t_ iii.push_back(1.0); // tau_ iii.push_back(-cos_); // cos_ iii.push_back(-sin_); // sin_ iii.push_back(x_); // x_ iii.push_back(y_); // y_ output_add_array_1.push_back(iii); iii.clear(); iii.push_back(tau_); // tau_ iii.push_back(1.0); // t_ iii.push_back(-cos_); // cos_ iii.push_back(sin_); // sin_ iii.push_back(x_); // x_ iii.push_back(y_); // y_ output_add_array_2.push_back(iii); iii.clear(); }; if(tau_==1.0){ iii.push_back(t_); // t_ iii.push_back(1.0); // tau_ iii.push_back(-cos_); // cos_ iii.push_back(-sin_); // sin_ iii.push_back(x_); // x_ iii.push_back(y_); // y_ output_add_array_1.push_back(iii); iii.clear(); iii.push_back(tau_); // tau_ iii.push_back(1.0); // t_ iii.push_back(-cos_); // cos_ iii.push_back(sin_); // sin_ iii.push_back(x_); // x_ iii.push_back(y_); // y_ output_add_array_2.push_back(iii); iii.clear(); }; if(tau_>1.0){ if(sin_>0.0) {Jordano_flag_tau[1] = Jordano_flag_tau[1] + 1;} }; }; if( t_>1.0 ){ if(tau_==0.0){ if(sin_>0.0) {Jordano_flag_t[1] = Jordano_flag_t[1] + 1;} }; if(tau_>0.0 && tau_<1.0){ Jordano_flag_t[1] = Jordano_flag_t[1] + 1; }; if(tau_==1.0){ if(-sin_>0.0) {Jordano_flag_t[1] = Jordano_flag_t[1] + 1;} }; }; } else { if(input_array.size()== 4){ double t0 = input_array[0][0]; //0 double tau0 = input_array[0][1]; double t1 = input_array[1][0]; //1 double tau1 = input_array[1][1]; double t2 = input_array[2][0]; double tau2 = input_array[2][1]; //0 double t3 = input_array[3][0]; double tau3 = input_array[3][1]; //1 int num_aad = 0; if (tau0>=0.0 && tau0 <=1.0){ //t = 0 num_aad = num_aad + 1; if ( tau0 == 0.0 ){ iii.push_back(0.0); // t_ iii.push_back(0.0); // tau_ iii.push_back(input_array[0][2]); // cos_ iii.push_back(0.0); // sin_ iii.push_back(input_array[0][4]); // x_ iii.push_back(input_array[0][5]); // y_ output_add_array_1.push_back(iii); iii.clear(); iii.push_back(0.0); // tau_ iii.push_back(0.0); // t_ iii.push_back(input_array[0][2]); // cos_ iii.push_back(0.0); // sin_ iii.push_back(input_array[0][4]); // x_ iii.push_back(input_array[0][5]); // y_ output_add_array_2.push_back(iii); iii.clear(); }; if ( tau0>0.0 && tau0 <1.0 ){ iii.push_back(0.0); // t_ iii.push_back(0.0); // tau_ iii.push_back(input_array[0][2]); // cos_ iii.push_back(0.0); // sin_ iii.push_back(input_array[0][4]); // x_ iii.push_back(input_array[0][5]); // y_ output_add_array_1.push_back(iii); iii.clear(); iii.push_back(0.0); // t_ iii.push_back(1.0); // tau_ iii.push_back(-input_array[0][2]); // cos_ iii.push_back(0.0); // sin_ iii.push_back(input_array[0][4]); // x_ iii.push_back(input_array[0][5]); // y_ output_add_array_1.push_back(iii); iii.clear(); iii.push_back(input_array[0][1]); // tau_ iii.push_back(0.0); // t_ iii.push_back(input_array[0][2]); // cos_ iii.push_back(0.0); // sin_ iii.push_back(input_array[0][4]); // x_ iii.push_back(input_array[0][5]); // y_ output_add_array_2.push_back(iii); iii.clear(); }; if ( tau0 == 1.0 ){ iii.push_back(0.0); // t_ iii.push_back(1.0); // tau_ iii.push_back(-input_array[0][2]); // cos_ iii.push_back(0.0); // sin_ iii.push_back(input_array[0][4]); // x_ iii.push_back(input_array[0][5]); // y_ output_add_array_1.push_back(iii); iii.clear(); iii.push_back(1.0); // tau_ iii.push_back(0.0); // t_ iii.push_back(input_array[0][2]); // cos_ iii.push_back(0.0); // sin_ iii.push_back(input_array[0][4]); // x_ iii.push_back(input_array[0][5]); // y_ output_add_array_2.push_back(iii); iii.clear(); }; }; if (tau1>=0.0 && tau1 <=1.0){ num_aad = num_aad + 1; if(tau1 == 0.0){ iii.push_back(1.0); // t_ iii.push_back(0.0); // tau_ iii.push_back(input_array[1][2]); // cos_ iii.push_back(0.0); // sin_ iii.push_back(input_array[1][4]); // x_ iii.push_back(input_array[1][5]); // y_ output_add_array_1.push_back(iii); iii.clear(); iii.push_back(0.0); // tau_ iii.push_back(1.0); // t_ iii.push_back(-input_array[1][2]); // cos_ iii.push_back(0.0); // sin_ iii.push_back(input_array[1][4]); // x_ iii.push_back(input_array[1][5]); // y_ output_add_array_2.push_back(iii); iii.clear(); }; if(tau1>0.0 && tau1<1.0){ iii.push_back(1.0); // t_ iii.push_back(0.0); // tau_ iii.push_back(input_array[1][2]); // cos_ iii.push_back(0.0); // sin_ iii.push_back(input_array[1][4]); // x_ iii.push_back(input_array[1][5]); // y_ output_add_array_1.push_back(iii); iii.clear(); iii.push_back(1.0); // t_ iii.push_back(1.0); // tau_ iii.push_back(-input_array[1][2]); // cos_ iii.push_back(0.0); // sin_ iii.push_back(input_array[1][4]); // x_ iii.push_back(input_array[1][5]); // y_ output_add_array_1.push_back(iii); iii.clear(); iii.push_back(input_array[1][1]); // tau_ iii.push_back(1.0); // t_ iii.push_back(-input_array[1][2]); // cos_ iii.push_back(0.0); // sin_ iii.push_back(input_array[1][4]); // x_ iii.push_back(input_array[1][5]); // y_ output_add_array_2.push_back(iii); iii.clear();}; if(tau1 == 1.0){ iii.push_back(1.0); // t_ iii.push_back(1.0); // tau_ iii.push_back(-input_array[1][2]); // cos_ iii.push_back(0.0); // sin_ iii.push_back(input_array[1][4]); // x_ iii.push_back(input_array[1][5]); // y_ output_add_array_1.push_back(iii); iii.clear(); iii.push_back(1.0); // tau_ iii.push_back(1.0); // t_ iii.push_back(-input_array[1][2]); // cos_ iii.push_back(0.0); // sin_ iii.push_back(input_array[1][4]); // x_ iii.push_back(input_array[1][5]); // y_ output_add_array_2.push_back(iii); iii.clear();}; }; if (t2 >=0.0 && t2 <=1.0 && num_aad<2){ if(t2 != t0 || tau2 != tau0){ if(t2 != t1 || tau2 != tau1){ num_aad = num_aad + 1; if(t2 == 0.0){ iii.push_back(0.0); // t_ iii.push_back(0.0); // tau_ = 0 iii.push_back(input_array[2][2]); // cos_ iii.push_back(0.0); // sin_ iii.push_back(input_array[2][4]); // x_ iii.push_back(input_array[2][5]); // y_ output_add_array_1.push_back(iii); iii.clear(); iii.push_back(0.0); // tau_ = 0 iii.push_back(0.0); // t_ iii.push_back(input_array[2][2]); // cos_ iii.push_back(0.0); // sin_ iii.push_back(input_array[2][4]); // x_ iii.push_back(input_array[2][5]); // y_ output_add_array_2.push_back(iii); iii.clear(); }; if(t2>0.0 && t2<1.0){ iii.push_back(input_array[2][0]); // t_ iii.push_back(0.0); // tau_ = 0 iii.push_back(input_array[2][2]); // cos_ iii.push_back(0.0); // sin_ iii.push_back(input_array[2][4]); // x_ iii.push_back(input_array[2][5]); // y_ output_add_array_1.push_back(iii); iii.clear(); iii.push_back(0.0); // tau_ = 0 iii.push_back(0.0); // t_ iii.push_back(input_array[2][2]); // cos_ iii.push_back(0.0); // sin_ iii.push_back(input_array[2][4]); // x_ iii.push_back(input_array[2][5]); // y_ output_add_array_2.push_back(iii); iii.clear(); iii.push_back(0.0); // tau_ = 0 iii.push_back(1.0); // t_ iii.push_back(-input_array[2][2]); // cos_ iii.push_back(0.0); // sin_ iii.push_back(input_array[2][4]); // x_ iii.push_back(input_array[2][5]); // y_ output_add_array_2.push_back(iii); iii.clear(); }; if(t2 == 1.0){ iii.push_back(input_array[2][0]); // t_ iii.push_back(0.0); // tau_ = 0 iii.push_back(input_array[2][2]); // cos_ iii.push_back(0.0); // sin_ iii.push_back(input_array[2][4]); // x_ iii.push_back(input_array[2][5]); // y_ output_add_array_1.push_back(iii); iii.clear(); iii.push_back(0.0); // tau_ = 0 iii.push_back(1.0); // t_ iii.push_back(-input_array[2][2]); // cos_ iii.push_back(0.0); // sin_ iii.push_back(input_array[2][4]); // x_ iii.push_back(input_array[2][5]); // y_ output_add_array_2.push_back(iii); iii.clear(); }; }; }; }; if (t3>=0.0 && t3 <=1.0 && num_aad<2){ if(t3 != t0 || tau3 != tau0){ if(t3 != t1 || tau3 != tau1){ if(t3 == 0.0){ iii.push_back(0.0); // t_ iii.push_back(1.0); // tau_ iii.push_back(-input_array[3][2]); // cos_ iii.push_back(0.0); // sin_ iii.push_back(input_array[3][4]); // x_ iii.push_back(input_array[3][5]); // y_ output_add_array_1.push_back(iii); iii.clear(); iii.push_back(1.0); // tau_ iii.push_back(0.0); // t_ iii.push_back(input_array[3][2]); // cos_ iii.push_back(0.0); // sin_ iii.push_back(input_array[3][4]); // x_ iii.push_back(input_array[3][5]); // y_ output_add_array_2.push_back(iii); iii.clear(); }; if(t3>0.0 && t3<1.0){ iii.push_back(input_array[3][0]); // t_ iii.push_back(1.0); // tau_ iii.push_back(-input_array[3][2]); // cos_ iii.push_back(0.0); // sin_ iii.push_back(input_array[3][4]); // x_ iii.push_back(input_array[3][5]); // y_ output_add_array_1.push_back(iii); iii.clear(); iii.push_back(1.0); // tau_ iii.push_back(0.0); // t_ iii.push_back(input_array[3][2]); // cos_ iii.push_back(0.0); // sin_ iii.push_back(input_array[3][4]); // x_ iii.push_back(input_array[3][5]); // y_ output_add_array_2.push_back(iii); iii.clear(); iii.push_back(1.0); // tau_ iii.push_back(1.0); // t_ iii.push_back(-input_array[3][2]); // cos_ iii.push_back(0.0); // sin_ iii.push_back(input_array[3][4]); // x_ iii.push_back(input_array[3][5]); // y_ output_add_array_2.push_back(iii); iii.clear(); }; if(t3 == 1.0){ iii.push_back(1.0); // t_ iii.push_back(1.0); // tau_ iii.push_back(-input_array[3][2]); // cos_ iii.push_back(0.0); // sin_ iii.push_back(input_array[3][4]); // x_ iii.push_back(input_array[3][5]); // y_ output_add_array_1.push_back(iii); iii.clear(); iii.push_back(1.0); // tau_ iii.push_back(1.0); // t_ iii.push_back(-input_array[3][2]); // cos_ iii.push_back(0.0); // sin_ iii.push_back(input_array[3][4]); // x_ iii.push_back(input_array[3][5]); // y_ output_add_array_2.push_back(iii); iii.clear(); }; }; }; }; } }; }; std::vector<std::vector<double>> give_spirit_tau(std::vector<std::vector<double>> segment, std::vector<std::vector<double>> his, std::array<int, 2> Jordano, double tau_point){ std::vector<std::vector<double>> spirit; std::vector<std::vector<double>> analize_tmp; std::vector<double> io; double x0 = segment[0][0]; double y0 = segment[0][1]; double x1 = segment[1][0]; double y1 = segment[1][1]; int left_N = Jordano[0]%2; int right_N = Jordano[1]%2; double x_tmp; double y_tmp; double parameter_tmp; int i_min; int i_max; double cos_a; double sin_a; double max_a; double min_a; double tmp; double left_light ; double right_light; std::sort(begin(his), end(his)); parameter_tmp = his[0][0]; if (parameter_tmp > 0.0){ io.push_back(left_N); io.push_back(x0); io.push_back(y0); io.push_back(left_N); spirit.push_back(io); io.clear(); }; for ( int m = 0; m<his.size(); m++ ) { if ( abs(parameter_tmp - his[m][0])<tau_point ){ io.push_back(his[m][1]); // t = [0;1] io.push_back(his[m][2]); // cos io.push_back(his[m][3]); // sin io.push_back(his[m][4]); // x io.push_back(his[m][5]); // y analize_tmp.push_back(io); io.clear(); } else { parameter_tmp = his[m][0]; m = m-1; i_min = 0; i_max = 0; cos_a = analize_tmp[0][1]; sin_a = analize_tmp[0][2]; max_a = cos_a/sqrt(pow(cos_a,2)+pow(sin_a,2)) ; min_a = max_a; for (int d=1; d<analize_tmp.size();d++){ cos_a = analize_tmp[d][1]; sin_a = analize_tmp[d][2]; tmp = cos_a/sqrt(pow(cos_a,2)+pow(sin_a,2)); if ( tmp > max_a ){ max_a = tmp; i_max = d; }; if ( tmp < min_a ){ min_a = tmp; i_min = d; }; }; x_tmp = analize_tmp[0][3]; y_tmp = analize_tmp[0][4]; left_light = 1.0; if ( (analize_tmp[i_min][0]==1.0 && analize_tmp[i_min][2]>0) || (analize_tmp[i_min][0]==0.0 && analize_tmp[i_min][2]<0) ) {left_light = 0.0;}; if ( analize_tmp[i_min][0] == 1.0 && analize_tmp[i_min][2] == 0.0 ) {left_light = 0.0;}; right_light = 1.0; if ( (analize_tmp[i_max][0]==0.0 && analize_tmp[i_max][2]>0) || (analize_tmp[i_max][0]==1.0 && analize_tmp[i_max][2]<0) ) {right_light = 0.0;}; if ( analize_tmp[i_max][0] == 0.0 && analize_tmp[i_max][2] == 0.0 ) {right_light = 0.0;}; io.push_back(left_light); io.push_back(x_tmp); io.push_back(y_tmp); io.push_back(right_light); spirit.push_back(io); io.clear(); analize_tmp.clear(); }; }; i_min = 0; i_max = 0; cos_a = analize_tmp[0][1]; sin_a = analize_tmp[0][2]; max_a = cos_a/sqrt(pow(cos_a,2)+pow(sin_a,2)) ; min_a = max_a; for (int d=1; d<analize_tmp.size();d++){ cos_a = analize_tmp[d][1]; sin_a = analize_tmp[d][2]; tmp = cos_a/sqrt(pow(cos_a,2)+pow(sin_a,2)); if ( tmp > max_a ){ max_a = tmp; i_max = d; }; if ( tmp < min_a ){ min_a = tmp; i_min = d; }; }; x_tmp = analize_tmp[0][3]; y_tmp = analize_tmp[0][4]; left_light = 1.0; if ( (analize_tmp[i_min][0]==1.0 && analize_tmp[i_min][2]>0.0) || (analize_tmp[i_min][0]==0.0 && analize_tmp[i_min][2]<0.0) ) {left_light = 0.0;}; if ( analize_tmp[i_min][0] == 1.0 && analize_tmp[i_min][2] == 0.0 ) {left_light = 0.0;}; right_light = 1.0; if ( (analize_tmp[i_max][0]==0.0 && analize_tmp[i_max][2]>0) || (analize_tmp[i_max][0]==1.0 && analize_tmp[i_max][2]<0) ) {right_light = 0.0;}; if ( analize_tmp[i_max][0] == 0.0 && analize_tmp[i_max][2] == 0.0 ) {right_light = 0.0;}; io.push_back(left_light); io.push_back(x_tmp); io.push_back(y_tmp); io.push_back(right_light); spirit.push_back(io); io.clear(); analize_tmp.clear(); parameter_tmp = his[his.size()-1][0]; if (parameter_tmp < 1.0){ io.push_back(right_N); io.push_back(x1); io.push_back(y1); io.push_back(right_N); spirit.push_back(io); io.clear(); }; return spirit; }; std::vector<std::vector<double>> give_spirit_t(std::vector<std::vector<double>> segment, std::vector<std::vector<double>> his, std::array<int, 2> Jordano, double tau_point){ std::vector<std::vector<double>> spirit; std::vector<std::vector<double>> analize_tmp; std::vector<double> io; double x0 = segment[0][0]; double y0 = segment[0][1]; double x1 = segment[1][0]; double y1 = segment[1][1]; int left_N = Jordano[0]%2; int right_N = Jordano[1]%2; double x_tmp; double y_tmp; double parameter_tmp; int i_min; int i_max; double cos_a; double sin_a; double max_a; double min_a; double tmp; double left_light ; double right_light; std::sort(begin(his), end(his)); parameter_tmp = his[0][0]; if (parameter_tmp > 0.0){ io.push_back(left_N); io.push_back(x0); io.push_back(y0); io.push_back(left_N); spirit.push_back(io); io.clear(); }; for ( int m = 0; m<his.size(); m++ ) { if ( abs(parameter_tmp - his[m][0])<tau_point ){ io.push_back(his[m][1]); // t = [0;1] io.push_back(his[m][2]); // cos io.push_back(his[m][3]); // sin io.push_back(his[m][4]); // x io.push_back(his[m][5]); // y analize_tmp.push_back(io); io.clear(); } else { parameter_tmp = his[m][0]; m = m-1; i_min = 0; i_max = 0; cos_a = analize_tmp[0][1]; sin_a = analize_tmp[0][2]; max_a = cos_a/sqrt(pow(cos_a,2)+pow(sin_a,2)) ; min_a = max_a; for (int d=1; d<analize_tmp.size();d++){ cos_a = analize_tmp[d][1]; sin_a = analize_tmp[d][2]; tmp = cos_a/sqrt(pow(cos_a,2)+pow(sin_a,2)); if ( tmp > max_a ){ max_a = tmp; i_max = d; }; if ( tmp < min_a ){ min_a = tmp; i_min = d; }; }; x_tmp = analize_tmp[0][3]; y_tmp = analize_tmp[0][4]; left_light = 1.0; if ( (analize_tmp[i_min][0]==1.0 && analize_tmp[i_min][2]>0) || (analize_tmp[i_min][0]==0.0 && analize_tmp[i_min][2]<0) ) {left_light = 0.0;}; right_light = 1.0; if ( (analize_tmp[i_max][0]==0.0 && analize_tmp[i_max][2]>0) || (analize_tmp[i_max][0]==1.0 && analize_tmp[i_max][2]<0) ) {right_light = 0.0;}; io.push_back(left_light); io.push_back(x_tmp); io.push_back(y_tmp); io.push_back(right_light); spirit.push_back(io); io.clear(); analize_tmp.clear(); }; }; i_min = 0; i_max = 0; cos_a = analize_tmp[0][1]; sin_a = analize_tmp[0][2]; max_a = cos_a/sqrt(pow(cos_a,2)+pow(sin_a,2)) ; min_a = max_a; for (int d=1; d<analize_tmp.size();d++){ cos_a = analize_tmp[d][1]; sin_a = analize_tmp[d][2]; tmp = cos_a/sqrt(pow(cos_a,2)+pow(sin_a,2)); if ( tmp > max_a ){ max_a = tmp; i_max = d; }; if ( tmp < min_a ){ min_a = tmp; i_min = d; }; }; x_tmp = analize_tmp[0][3]; y_tmp = analize_tmp[0][4]; left_light = 1.0; if ( (analize_tmp[i_min][0]==1.0 && analize_tmp[i_min][2]>0) || (analize_tmp[i_min][0]==0.0 && analize_tmp[i_min][2]<0) ) {left_light = 0.0;}; right_light = 1.0; if ((analize_tmp[i_max][0]==0.0 && analize_tmp[i_max][2]>0) || (analize_tmp[i_max][0]==1.0 && analize_tmp[i_max][2]<0)) {right_light = 0.0;}; io.push_back(left_light); io.push_back(x_tmp); io.push_back(y_tmp); io.push_back(right_light); spirit.push_back(io); io.clear(); analize_tmp.clear(); parameter_tmp = his[his.size()-1][0]; if (parameter_tmp < 1.0){ io.push_back(right_N); io.push_back(x1); io.push_back(y1); io.push_back(right_N); spirit.push_back(io); io.clear(); }; return spirit; }; std::vector<std::vector<double>> add_triangle (std::vector<std::vector<double>> shad, std::vector<double> triangle_shad, double r_point){ std::vector<std::vector<double>> merge_shadow; merge_shadow.clear(); std::vector<std::vector<double>> spirit; std::vector<double> shad_el; double x0 = triangle_shad[0]; double y0 = triangle_shad[1]; double x1 = triangle_shad[2]; double y1 = triangle_shad[3]; double x2 = triangle_shad[4]; double y2 = triangle_shad[5]; double x0_; double y0_; double x1_; double y1_; if(shad.size() == 0 ){ shad_el.push_back(x0); shad_el.push_back(y0); shad_el.push_back(x1); shad_el.push_back(y1); merge_shadow.push_back(shad_el); shad_el.clear(); shad_el.push_back(x1); shad_el.push_back(y1); shad_el.push_back(x2); shad_el.push_back(y2); merge_shadow.push_back(shad_el); shad_el.clear(); shad_el.push_back(x2); shad_el.push_back(y2); shad_el.push_back(x0); shad_el.push_back(y0); merge_shadow.push_back(shad_el); shad_el.clear(); } else { double t1_point = r_point/(sqrt(pow((x1-x0),2) + pow((y1 - y0),2))); double t2_point = r_point/(sqrt(pow((x2-x1),2) + pow((y2 - y1),2))); double t3_point = r_point/(sqrt(pow((x0-x2),2) + pow((y0 - y2),2))); double u0; double v0; double u1; double v1; std::vector<double> point1_t; std::vector<double> point2_t; std::vector<double> point3_t; std::vector<std::vector<double>> segment1_t; std::vector<std::vector<double>> segment2_t; std::vector<std::vector<double>> segment3_t; std::vector<double> point1_tau; std::vector<double> point2_tau; std::vector<std::vector<double>> segment4_tau; std::vector<std::vector<double>> vector_tmp; std::vector<std::vector<double>> his_1t; std::vector<std::vector<double>> his_2t; std::vector<std::vector<double>> his_3t; std::vector<std::vector<double>> his_tau; std::vector<double> io; std::array<int, 2> Jordano_t1; std::array<int, 2> Jordano_t2; std::array<int, 2> Jordano_t3; std::array<int, 2> Jordano_tau; Jordano_t1[0] = 0; Jordano_t1[1] = 0; Jordano_t2[0] = 0; Jordano_t2[1] = 0; Jordano_t3[0] = 0; Jordano_t3[1] = 0; Jordano_tau[0] = 0; Jordano_tau[1] = 0; point1_t.clear(); point1_t.push_back(x0); point1_t.push_back(y0); point2_t.clear(); point2_t.push_back(x1); point2_t.push_back(y1); point3_t.clear(); point3_t.push_back(x2); point3_t.push_back(y2); segment1_t.clear(); segment1_t.push_back(point1_t); segment1_t.push_back(point2_t); segment2_t.clear(); segment2_t.push_back(point2_t); segment2_t.push_back(point3_t); segment3_t.clear(); segment3_t.push_back(point3_t); segment3_t.push_back(point1_t); his_1t.clear(); his_2t.clear(); his_3t.clear(); Jordano_t1[0] = 0; Jordano_t1[1] = 0; Jordano_t2[0] = 0; Jordano_t2[1] = 0; Jordano_t3[0] = 0; Jordano_t3[1] = 0; if(interval_point_point(segment1_t[0][0],segment1_t[0][1],segment1_t[1][0],segment1_t[1][1])>r_point && interval_point_point(segment2_t[0][0],segment2_t[0][1],segment2_t[1][0],segment2_t[1][1])>r_point && interval_point_point(segment3_t[0][0],segment3_t[0][1],segment3_t[1][0],segment3_t[1][1])>r_point) { for (int k = 0; k< shad.size(); k++){ u0 = shad[k][0]; v0 = shad[k][1]; u1 = shad[k][2]; v1 = shad[k][3]; double tau_point = r_point/(sqrt(pow((u1-u0),2) + pow((v1 - v0),2))); point1_tau.clear(); point1_tau.push_back(u0); point1_tau.push_back(v0); point2_tau.clear(); point2_tau.push_back(u1); point2_tau.push_back(v1); segment4_tau.clear(); segment4_tau.push_back(point1_tau); segment4_tau.push_back(point2_tau); his_tau.clear(); Jordano_tau[0] = 0; Jordano_tau[1] = 0; vector_tmp.clear(); vector_tmp = segments_intersection_point(segment1_t,segment4_tau,r_point); two_histories(vector_tmp,his_1t,his_tau,Jordano_t1,Jordano_tau); vector_tmp.clear(); vector_tmp = segments_intersection_point(segment2_t,segment4_tau,r_point); two_histories(vector_tmp,his_2t,his_tau,Jordano_t2,Jordano_tau); vector_tmp.clear(); vector_tmp = segments_intersection_point(segment3_t,segment4_tau,r_point); two_histories(vector_tmp,his_3t,his_tau,Jordano_t3,Jordano_tau); if (his_tau.size()==0){ if (Jordano_tau[0]%2 == 0){ shad_el.push_back(u0); shad_el.push_back(v0); shad_el.push_back(u1); shad_el.push_back(v1); merge_shadow.push_back(shad_el); shad_el.clear(); }; } else { spirit.clear(); spirit = give_spirit_tau(segment4_tau,his_tau,Jordano_tau,tau_point); for(int q = 1; q<spirit.size(); q++){ if( spirit[q-1][3]==0.0 && spirit[q][0]==0.0 ){ x0_ = spirit[q-1][1]; y0_ = spirit[q-1][2]; x1_ = spirit[q][1]; y1_ = spirit[q][2]; shad_el.push_back(x0_); shad_el.push_back(y0_); shad_el.push_back(x1_); shad_el.push_back(y1_); merge_shadow.push_back(shad_el); shad_el.clear(); }; }; }; }; if (his_1t.size()==0){ if (Jordano_t1[0]%2 == 0){ shad_el.push_back(x0); shad_el.push_back(y0); shad_el.push_back(x1); shad_el.push_back(y1); merge_shadow.push_back(shad_el); shad_el.clear(); }; } else { spirit.clear(); spirit = give_spirit_t(segment1_t,his_1t,Jordano_t1,t1_point); for(int q = 1; q<spirit.size(); q++){ if( spirit[q-1][3]==0.0 && spirit[q][0]==0.0 ){ x0_ = spirit[q-1][1]; y0_ = spirit[q-1][2]; x1_ = spirit[q][1]; y1_ = spirit[q][2]; shad_el.push_back(x0_); shad_el.push_back(y0_); shad_el.push_back(x1_); shad_el.push_back(y1_); merge_shadow.push_back(shad_el); shad_el.clear(); }; }; }; if (his_2t.size()==0){ if (Jordano_t2[0]%2 == 0){ shad_el.push_back(x1); shad_el.push_back(y1); shad_el.push_back(x2); shad_el.push_back(y2); merge_shadow.push_back(shad_el); shad_el.clear(); }; } else { spirit.clear(); spirit = give_spirit_t(segment2_t,his_2t,Jordano_t2,t2_point); for(int q = 1; q<spirit.size(); q++){ if( spirit[q-1][3]==0.0 && spirit[q][0]==0.0 ){ x0_ = spirit[q-1][1]; y0_ = spirit[q-1][2]; x1_ = spirit[q][1]; y1_ = spirit[q][2]; shad_el.push_back(x0_); shad_el.push_back(y0_); shad_el.push_back(x1_); shad_el.push_back(y1_); merge_shadow.push_back(shad_el); shad_el.clear(); }; }; }; if (his_3t.size()==0){ if (Jordano_t3[0]%2 == 0){ shad_el.push_back(x2); shad_el.push_back(y2); shad_el.push_back(x0); shad_el.push_back(y0); merge_shadow.push_back(shad_el); shad_el.clear(); }; } else { spirit.clear(); spirit = give_spirit_t(segment3_t,his_3t,Jordano_t3,t3_point); for(int q = 1; q<spirit.size(); q++){ if( spirit[q-1][3]==0.0 && spirit[q][0]==0.0 ){ x0_ = spirit[q-1][1]; y0_ = spirit[q-1][2]; x1_ = spirit[q][1]; y1_ = spirit[q][2]; shad_el.push_back(x0_); shad_el.push_back(y0_); shad_el.push_back(x1_); shad_el.push_back(y1_); merge_shadow.push_back(shad_el); shad_el.clear(); }; }; }; }; }; return merge_shadow; }; int main() { double L_triangle_min; double r_point; L_triangle_min = 1.0; r_point = L_triangle_min/1e+5; std::vector<double> triangle_shadow; triangle_shadow.clear(); triangle_shadow.push_back(1.0); //x1 (0.0) triangle_shadow.push_back(0.0); //y1 (0.0) triangle_shadow.push_back(1.0); //x2 (1.0) triangle_shadow.push_back(1.0); //y2 (0.0) triangle_shadow.push_back(0.0); //x3 (0.0) triangle_shadow.push_back(1.0); //y3 (1.0) std::vector<std::vector<double>> shadow; shadow.clear(); std::vector<double> shadow_element; shadow_element.push_back(0.0); //u0 (0.0 ); shadow_element.push_back(0.0); //v0 (-0.5); shadow_element.push_back(1.0); //u1 (0.5); shadow_element.push_back(0.0); //v1 (0.0); shadow.push_back(shadow_element); shadow_element.clear(); shadow_element.push_back(1.0); //u0 (0.5); shadow_element.push_back(0.0); //v0 (0.0); shadow_element.push_back(0.0); //u1 (-0.5); shadow_element.push_back(1.0); //v1 (0.0 ); shadow.push_back(shadow_element); shadow_element.clear(); shadow_element.push_back(0.0); //u0 (-0.5); shadow_element.push_back(1.0); //v0 (0.0 ); shadow_element.push_back(0.0); //u1 (0.0 ); shadow_element.push_back(0.0); //v1 (-0.5); shadow.push_back(shadow_element); shadow_element.clear(); // shadow.clear(); std::vector<std::vector<double>> rez_of_merge; rez_of_merge = add_triangle(shadow,triangle_shadow,r_point); if (rez_of_merge.size()>0){ std::cout<< "rez_of_merge" <<std::endl; for (int i=0; i< rez_of_merge.size(); i++) {std::cout<< rez_of_merge[i][0] << "; " << rez_of_merge[i][1] << "; " << rez_of_merge[i][2] << "; " << rez_of_merge[i][3] <<std::endl;} } else {std::cout<< "rez_of_merge = 0" <<std::endl;} return 0; }
ссылка на оригинал статьи https://habr.com/ru/articles/848782/
Добавить комментарий