更改矩形大小时重新计算射线 tracing/casting 成本

Question

我有一个 "rays" 的数组，我需要根据下面的矩形框来衡量成本。外层红色框总是比深绿色框大 1m，浅绿色框总是比深绿色框小 10cm。如果射线

穿过深绿色框我会分配成本 c
ands 在深绿色框上我会分配成本 d
落在我要指定的红色区域成本 e
不与深绿色方框相交且不落在红色方框内，成本f
和d < f < c < e

我目前有以下数据结构和函数来计算成本。我需要计算给定矩形的成本（由 4 个 xy 坐标表示），但同时找到 approximate/local 最优 length/width深绿色矩形（即通过固定矩形的最近角来缩小或增大尺寸）使得成本最小。

一个具体的例子是下面的截图。较小的矩形对应于图中的深绿色框。绿线是成本为 d 的光线，黄线是成本为 f 的光线，蓝绿色线是成本为 c 的光线。如果我固定内部矩形的左上角并减小宽度，我可以将绿松石射线的成本从 c 降低到 f。

我的问题是，我不知道应该如何更改我的代码或更改我的数据结构，以便我可以通过仅重新计算受影响的光线（即无需再次遍历所有光线）来找到最佳维度。

struct VRay{
    float range, x, y;
    enum RayType{ PASSTHROUGH, FREE, SURFACE, OCCLUDED, UNIFORM};
    RayType r;
};
struct VScan{
    VRay rays[401];
    int closestIdx;
    int firstIdx;
    int lastIdx;
} vscan;

成本计算函数：

for (int i = 0; i < 401; i++){
       VRay& r = vscan.rays[i];

       Vector2f cray(r.y, -r.x);
       bool ppBound = false;
       bool ppSurf = false;
       Vector2f vertex =  outBox.row(0);
       Vector2f vertexSurf = surface.row(0);

       float init = cray.dot(vertex);
       float initSurf = cray.dot(vertexSurf);
       //this part finds whether ray intersects rectangle or not 
       for (int j = 1; j < 4; j++){
            Vector2f v2 = outBox.row(j);
            Vector2f vSurf =  surface.row(j);

            float i2 = cray.dot(v2);
            float iSurf = cray.dot(vSurf);

            if (i2 * init < 0){
                ppBound =  true;
            }

            if (iSurf * initSurf < 0){
                ppSurf = true;
            }
       }

       //ray does not intersect all rectangles
       if (!ppBound){
          z += log(1/100.);
          continue;
       }

        //ray is inside red box
        if (inPolygon(outBox, r)){
            //ray inside dark green box 
            if (inPolygon(surface, r)){
                //ray inside light green box
                if (inPolygon(inBox,r))
                    c  = passTCost;
                else
                    c = surfaceCost;
            }
            else{
                c = freeCost; //free space
            }
        }
        else if (ppSurf){
            c = passTCost; //before all boxes
        }
        else { //ray does not intersect dark green box
            z += log(1/100.);
            continue;
        }

        z += -(c * c)/(2 * deviation * deviation);
    }

Answer 1

光线永远不会落在浅绿色框中，我说得对吗？即光线到达浅绿色区域时停止？是否有任何规则可以确定光线是落在红色区域、深绿色区域还是同时穿过它们？

如果这些规则与车的大小无关，而只取决于射线"end point"的相对位置，例如如果射到汽车表面中间的光线总是落在汽车周围的自由 space 上，则光线数量与成本 d、c 或e 与汽车的大小无关。成本为 f（标记为黄色）的光线数量只是其余光线，即没有成本 d、c 或 e 的光线。

这意味着在第一步中，计算最佳（最小）成本总和，给定 d/c/e 的恒定成本比率并且知道其余射线的成本为 f.

示例：您有 5% 的光线成本为 c（绿松石线），10% 的光线成本为 e（红线），40% 的光线成本为 d（绿线），45% 的光线成本为 f（黄线）。因此，对于成本为 c 的每条光线，您有两条成本为 e 的光线和八条成本为 d 的光线。所有剩余的光线都花费了 f.

-> 设 x 为成本为 c 的射线数，则总成本为：1*c*x + 2*e*x + 8*d*x + (totalNumberOfRays - (1+2+8)*x) * f

现在找到这个函数的最小值（这很容易，因为它是一个线性函数，但可能你对你的车的尺寸有一些限制），并使用结果 x 来计算尺寸你的车：如果你一开始就有，例如10条射线，成本c，结果x为5，你必须找到只产生5条成本c的汽车尺寸，即汽车宽度和长度应分别为乘以 0.5.

现在，我唯一希望的是，我的假设是正确的:-)

（我想到的其他选项，以防我的假设错误，以某种方式将光线分组在一起，并且只对每组进行计算）

Answer 2

如果我理解正确，您想要改变深绿色矩形的大小，使其与浅绿色矩形保持共同的中心，两者的边缘保持平行。深绿色矩形在任何时候都不会离开红色矩形，并且永远不会小于浅绿色矩形。红色和浅绿色矩形保持不变。如果您改变深绿色矩形（DGR 从现在开始......），您只想重新计算那些可能会改变其成本的光线。

所以我的主张如下：让另一个 std::vector<VRay*> 在开始时为空，以及第二个 sum 变量。在第一个运行中，像您一样计算成本。此外，对于每条光线，确定在改变 DGR 时它是否会完全改变。

如果可以，将指向它的指针添加到上面的向量，否则，将其当前成本添加到第二个总和。从现在开始，你只需要重新计算指针向量中的那些光线，并将其他光线的预先计算的总和添加到这个新的总和上。

如果光线可能改变成本，如何决定？好吧，那些没有穿过红色矩形的人当然不会。那些以浅绿色矩形结束的也不会，以及那些同时穿过浅绿色和红色矩形的。所以相关的光线是那些在红色矩形内结束，但不在浅绿色矩形内，另外那些完全穿过红色矩形但不与浅绿色矩形相交的光线。

如果您考虑最大 DGR（如果它不一定与红色那个平行），则可以收集进一步的优化：那些不与这个最大矩形相交或终止在它前面的线也不会改变。

更改矩形大小时重新计算射线 tracing/casting 成本

recalculate ray tracing/casting costs when changing size of rectangle

c++

algorithm

geometry

raycasting