c++ 优化函数来计算直线上一点的投影？

5hcedyr0 于 2023-01-10 发布在其他

关注(0)|答案(4)|浏览(234)

请考虑以下问题：

我的问题是：如何优化以下独立功能：

// Computation of the coordinates of P
inline std::array<double, 3> P(const std::array<double, 3>& A, 
                               const std::array<double, 3>& B,
                               const std::array<double, 3>& M)
{
    // The most inefficient version in the world (to be verified)
    std::array<double, 3> AB = {B[0]-A[0], B[1]-A[1], B[2]-A[2]};
    std::array<double, 3> AM = {M[0]-A[0], M[1]-A[1], M[2]-A[2]};
    double norm = std::sqrt(AB[0]*AB[0]+AB[1]*AB[1]+AB[2]*AB[2]);
    double dot = AB[0]*AM[0]+AB[1]*AM[1]+AB[2]*AM[2];
    double d1 = dot/norm;
    std::array<double, 3> AP = {AB[0]/d1, AB[1]/d1, AB[2]/d1};
    std::array<double, 3> P = {AP[0]-A[0], AP[1]-A[1], AP[2]-A[2]};
    return P;
}

// Computation of the distance d0
inline double d0(const std::array<double, 3>& A, 
                 const std::array<double, 3>& B,
                 const std::array<double, 3>& M)
{
    // The most inefficient version in the world (to be verified)
    std::array<double, 3> AB = {B[0]-A[0], B[1]-A[1], B[2]-A[2]};
    std::array<double, 3> AM = {M[0]-A[0], M[1]-A[1], M[2]-A[2]};
    double norm = std::sqrt(AB[0]*AB[0]+AB[1]*AB[1]+AB[2]*AB[2]);
    double dot = AB[0]*AM[0]+AB[1]*AM[1]+AB[2]*AM[2];
    double d1 = dot/norm;
    std::array<double, 3> AP = {AB[0]/d1, AB[1]/d1, AB[2]/d1};
    std::array<double, 3> P = {AP[0]-A[0], AP[1]-A[1], AP[2]-A[2]};
    std::array<double, 3> MP = {P[0]-M[0], P[1]-M[1], P[2]-M[2]};
    double d0 = std::sqrt(MP[0]*MP[0]+MP[1]*MP[1]+MP[2]*MP[2]);
    return d0;
}

// Computation of the distance d1
inline double d1(const std::array<double, 3>& A, 
                 const std::array<double, 3>& B,
                 const std::array<double, 3>& M)
{
    // The most inefficient version in the world (to be verified)
    std::array<double, 3> AB = {B[0]-A[0], B[1]-A[1], B[2]-A[2]};
    std::array<double, 3> AM = {M[0]-A[0], M[1]-A[1], M[2]-A[2]};
    double norm = std::sqrt(AB[0]*AB[0]+AB[1]*AB[1]+AB[2]*AB[2]);
    double dot = AB[0]*AM[0]+AB[1]*AM[1]+AB[2]*AM[2];
    double d1 = dot/norm;
}

// Computation of the distance d2
inline double d2(const std::array<double, 3>& A, 
                 const std::array<double, 3>& B,
                 const std::array<double, 3>& M)
{
    // The most inefficient version in the world (to be verified)
    std::array<double, 3> AB = {B[0]-A[0], B[1]-A[1], B[2]-A[2]};
    std::array<double, 3> AM = {M[0]-A[0], M[1]-A[1], M[2]-A[2]};
    double norm = std::sqrt(AB[0]*AB[0]+AB[1]*AB[1]+AB[2]*AB[2]);
    double dot = AB[0]*AM[0]+AB[1]*AM[1]+AB[2]*AM[2];
    double d1 = dot/norm;
    double d2 = norm-d1;
    return d2;
}

这样每个函数都会被尽可能地优化？（我会执行这些函数亿万次）。

c++

来源：https://stackoverflow.com/questions/22087193/optimized-functions-to-compute-projection-of-a-point-on-a-line

4条答案

按热度按时间

pb3skfrl1#

从算法的Angular 来看，您可以计算向量到另一个向量的投影，而不使用SQRT调用
这里伪码http://www.euclideanspace.com/maths/geometry/elements/line/projections/

// projection of vector v1 onto v2
inline vector3 projection( const vector3& v1, const vector3& v2 ) {
    float v2_ls = v2.len_squared();
        return v2 * ( dot( v2, v1 )/v2_ls );

}

其中dot（）是两个向量的点积，len_squared是向量与self的点积。
注：如果可能，尝试在主循环之前预先计算v2_ls的倒数。

赞(0）回复(0）举报 2023-01-10

q9rjltbz2#

一次计算所有请求数量可能更好。
设P = A + t . AB为给出P位置的矢量方程，表示MP和AB正交：MP . AB = 0 = (MA + t . AB) . AB，其产生t= - (MA . AB) / AB^2和P。
t是比率AP / AB，因此d1 = t . |AB|。类似地，d2 = (1 - t) . |AB|. d0是从毕达哥拉斯d0^2 = MA^2 - d1^2获得的，或者通过|MP|的直接计算获得。
会计：计算MA（增加3个），AB（增加3个），AB^2（2次添加，3 μ l），MA.AB（2次添加，3 μ l），t（1格），P（3个加法器，3微升），|AB|（1平方），d1（1微升），d2（1个加法器，1微升），MA^2（2个加法器，3微升），d0（1个加法器，1微升，1平方）。
总共17个加法器，15个乘法器，1个除法器，2个平方。

赞(0）回复(0）举报 2023-01-10

exdqitrt3#

如果您希望代码可移植，因此不使用处理器特定的功能，我建议您：
1)正如我在上面的评论中提到的，创建一个3D矢量类，它只会使编写代码变得容易得多（优化开发时间）
2)创建一个交集类，使用惰性求值来获取P、d0和d1，如下所示：

class Intersection
{
public: 
  Intersection (A, B, M) { store A, B, M; constants_calculated = false }
  Point GetP () { CalculateConstants; Return P; }
  double GetD0 () { CalculateConstants; Return D0; }
  double GetD1 () { CalculateConstants; Return D1; }
private:
  CalculateConstants ()
  {
    if (!constants_calculate)
    {
      calculate and store common expressions required for P, d0 and d1
      constants_calculate = true
    }
  }

3)不要调用10亿次，什么都不做会无限快，为什么要调用这么频繁，有没有方法可以用更少的调用来求出P、d0和d1？
如果您可以使用处理器特定的特性，那么您可以考虑使用SIMD，但这可能需要将精度从双精度降至浮点。

赞(0）回复(0）举报 2023-01-10

q3qa4bjr4#

以下是点到线投影计算的C++实现

#include <iostream>
#include <cmath>
using namespace std;
int main() {
// the point
double x0 = 1.0, y0 = 1.0;
// the line equation
double A = 1.0, B = 1.0, C = 0.0;
// calc point to line distance
double dist = fabs(A * x0 + B * y0 + C) / sqrt(A * A + B * B);
// calc project point coord
double x1 = x0 - dist * A / sqrt(A * A + B * B);
double y1 = y0 - dist * B / sqrt(A * A + B * B);
// result
cout << "project point：(" << x1 << ", " << y1 << ")" << endl;
return 0;
}

赞(0）回复(0）举报 2023-01-10

我来回答

c++ 优化函数来计算直线上一点的投影？

4条答案

相关问题

热门标签

最新问答