找到矢量构造的交叉点

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; 
} 

有了这两个循环，我会找到网格的每一行和轮廓的每个向量（两点之间）的交点。然后，我将不得不找到最接近网格线的两个交点并存储这些点。特殊情况是，如果在轮廓中有东西，就像一个洞。在这种情况下，我会找到四点。

编辑：我为什么要使用交叉点显示在下面的图 在这里，我们有一个矩形的轮廓。正如你所看到的，只有几点来描述这个数字。 下一张图显示了模型的填充 由于轮廓的几个点，我必须计算轮廓和网格的交点。

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是找到行略低于简单的函数/当前横坐标以上（简单，因为你的线是垂直的）。