Началось с того, что мне показалось простым делом - "векторно" (не "растрово") объединить многоугольник с треугольником. Вроде, получилось - программу написал - но вышло не совсем просто. Теперь я уже знаю, что я далеко не первый, кто возился с этой задачей, что таких людей очень много. А это значит, что наболело у многих, кто это реализовывал - есть, что обсудить, есть о чем поговорить - особенно, если у меня получилось не очень (вдруг ошибся, хотя я сейчас уверен, что всё работает, как часики) - можно ткнуть в меня вилкой. Задача вообще-то веселая. Приглашаю под кат.
Алгоритм «векторное объединение теней»
Полезные ссылки
Скрытый текст
Пересечение многоугольников:
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;
}Комментарии (4)
tony-space
07.10.2024 13:47+1Рассматривали ли вы использовать существующие библиотеки для решения задачи? Для C++ есть header-only библиотека Boost.Geometry где вышеупомянутая задача решается посредством функции union_.
https://www.boost.org/doc/libs/1_85_0/libs/geometry/doc/html/geometry/reference/algorithms/union_/union__3.html
Сами полигоны там описываются из колец: одно внешнее (внешний контур) и много внутренних (дырки). Каждое кольцо -- это std::vector из точек (есть встроенный класс, но можно и свой задать).
northzen
07.10.2024 13:47Здравствуйте,
Проблема объединения полигонов старая. И широко известная. Ровно как и обработка точек без потери точности, когда требуется узнать, лежит ли что-то "внутри" или "вне".
Вот приличная библиотека, занимающаяся проблемами подобного рода, которая является де-факто стандартом среди открытых библиотек:
https://doc.cgal.org/latest/Boolean_set_operations_2/group__boolean__intersection.htmlВот как она справляется с произвольной точностью:
https://www.cgal.org/exact.htmlИспользуйте ее, она вам сэкономит кучу нервов и сил, пока вы сможете заниматься более сложной логикой или задачами, котоыре в ней не решены.
wataru
Касаемо кода: какой-нибудь класс Point с переопределенными операциями сложения и хотя бы умножения на скаляр сделал бы ваш код на порядки более читаемым. Еще хорошо бы векторное/скалярные произведения переопределить, например через * и ^.
y1 = seg1[1][1]- вообще плохо. Все это вычисление пересечения отрезков становится буквально парой векторых/скалярных произведений. И количество параметров функций делится на 2 и имена будут более понятными.his_tau,shad_el,iii- вообще непоятные имена переменных. Я пока так и не разобрался, что там происходит.А так, идея здравая - нанести все точки пересечения на отрезки, пометить их как вхождение внутрь или выход из другого многоугольника, потом выкинуть отрезки целиком внутри, и замкнуть все контура из оставшихся отрезков. Проблема с параллельными накладывающимеся отрезками и пересечениями по вершинам, но тут можно считать, что треугольник на epsilion больше, чем он есть на самом деле и так аккуратно рассмотреть несколько случаев.
MarkNest Автор
спасибо!