Найти точки пересечения векторной конструкции

Question

Так что в моем программном обеспечении у меня есть два вектора. Первый вектор matrix хранит информацию о форме данной 3D-модели. Поэтому я получил вектор массивов для хранения координат точек x, y, z.

std::vector<std::array<double, 3>> matrix; 

Этот вектор уже отсортирован, так что я получаю контур модели. Во втором векторе boundingbox Я сохраняю информацию об ограничивающей рамке.

std::vector<std::array<double, 3>> boundingbox; 

В этом векторе первые четыре элемента описывают ограничительную рамку вокруг контура. Чтобы заполнить контур, я разместил на нем сетку. В этом случае сетка определяется программным обеспечением на основе переменной. Переменная infill задается пользователем во время выполнения. Итак, в настоящее время моя программа создает следующий образ.

Теперь следующий шаг должен был бы найти точки пересечения между сеткой и контуром. Мой подход к этому был бы типичным математическим подходом. Я бы использовал два for -loops. Первый цикл будет использоваться для итерации по сетке, чтобы каждая строка сетки вызывалась один раз.

Второй цикл будет использоваться вектором для прохождения матрицы. Я разработал псевдокод, в котором я описываю свою процедуру.

int fillingStart; //first element of boundingbox to contain information about the grid 
int n; //number of lines in the Grid. 
for(size_t i=fillingStart; i<(n-1); i+2) 
{ 
    double A_x=boundingbox[j][0]; 
    double A_y=boundingbox[j][1]; 
    double B_x=boundingbox[j+1][0]; 
    double B_y=boundingbox[j+1][0]; 

    double AB_x=B_x-A_x; 
    double AB_y=B_y-A_y; 

    double intersectionpoint_y = DBL_MAX; 
    double intersectionpoint_x = DBL_MAX; 
    double intersectionpoint2_y = DBL_MAX; 
    double intersectionpoint2_x = DBL_MAX; 

    for(size_t j=0; j<(matrix.size()-1); j++) 
    { 
    double C_x = matrix[j][0]; 
    double C_y = matrix[j][1]; 
    double D_x = matrix[j+1][0]; 
    double D_y = matrix[j+1][1]; 

    double CD_x = D_x-C_x; 
    double CD_y = D_y-C_y; 

    double s = (((C_x-A_x)*(-CD_y))-((-CD_x)*(C_y-A_y)))/((AB_x*(-CD_y))-((-CD_x)*AB_y));//Cramer's rule 
    double t = ((AB_x*(C_y-A_y))-((C_x-A_x)*AB_y))/((AB_x * (-CD_y))-((-CD_x)*AB_y));//Cramer's rule 

    double point_x = A_x+s*AB_x; 
    double point_y = A_y*s*AB_y; 

    if(point_x < intersectionpoint_x && point_y < intersectionpoint_y) 
    { 
     intersectionpoint_x = point_x; 
     intersectionpoint_y = point_y; 
    } 
    else if(point_x < intersectionpoint2_x && point_y < intersectionpoint2_y) 
    { 
     intersectionpoint2_x = point_x; 
     intersectionpoint2_y = point_y; 
    } 
    } 

    intersects.push_back(std::array<double, 3>()); 
    double q = boundingbox.size()-1; 
    intersects[q][0] = intersectionpoint_x; 
    intersects[q][1] = intersectionpoint_y; 

    intersects.push_back(std::array<double, 3>()); 
    double q = boundingbox.size()-1; 
    intersects[q][0] = intersectionpoint2_x; 
    intersects[q][1] = intersectionpoint2_y; 
} 

С этими двумя петлями я хотел бы найти точки пересечения для каждой линии сетки и каждого вектора (между двумя точками) контура. Затем мне нужно было бы найти две точки пересечения, наиболее близкие к линии сетки, и сохранить эти точки. Частный случай был бы, если в контуре есть что-то вроде дыры. В этом случае я бы нашел четыре очка.

EDIT: Почему я хочу использовать точки пересечения показано на следующих рисунках Здесь мы имеем контур прямоугольника. Как вы можете видеть, есть всего несколько моментов, чтобы описать фигуру. Следующее изображение показывает заполнение модели Из-за нескольких точек контура я должен рассчитать точки пересечения контура и сетки.

EDIT2: Теперь я получил код работает и обновляется код здесь, но проблема в том, что она всегда сохраняет ту же точку в intersectionpoint. Это из-за if-утверждения, но я не могу понять, как заставить его работать.

Answer 1

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

std::vector<std::array<double, 3>> intersects; 

auto it = matrix.begin(); 

while (it != matrix.end() - 1) { 
    auto &p1 = *it; 
    auto &p2 = *(++it); 
    double x; 
    // Check if there is a vertical line between p1 and p2 
    if (has_vertical_line(p1, p2, &x)) { 
     // The equation of the line joining p1 and p2 is: 
     //  (p2[1] - p1[1])/(p2[0] - p1[0]) * x + p1[0] 
     double y = (p2[1] - p1[1])/(p2[0] - p1[0]) * x + p1[0]; 
     intersects.push_back({x, y, 0.0}); 
    } 
} 

Где has_vertical_line что-то вроде:

bool has_vertical_line (std::array<double, 3> const& p1, 
         std::array<double, 3> const& p2, 
         double *px) { 
    double x1 = p1[0], x2 = p2[0]; 
    if (x2 <= x1) { 
     std::swap(x1, x2); 
    } 
    size_t lx2 = closest_from_below(x2), 
      lx1 = closest_from_above(x1); 
    if (lx1 == lx2) { 
     *px = lines[lx1]; // Assuming abscissa 
     return true; 
    } 
    return false; 
} 

Где closest_from_below и closest_from_above простые функции, которые находят линию чуть ниже/выше текущей абсциссы (тривиально, так как ваши линии по вертикали).