找到矢量構造的交叉點

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是找到行略低於簡單的函數/當前橫座標以上（簡單，因爲你的線是垂直的）。