Пересчитать затраты трассировки/литья луча при изменении размера прямоугольника

У меня есть массив "лучей", которые мне нужно для измерения затрат по отношению к прямоугольным блокам ниже. Внешняя красная рамка всегда на 1 м больше, чем темно-зеленая коробка, а светло-зеленая коробка на 10 см меньше, чем темно-зеленая коробка. Если луч

  • проходит через темно-зеленый ящик, я бы назначил стоимость c
  • и на темно-зеленой коробке я бы назначил стоимость d
  • Приземлится на красную область, которую я бы назначил стоимость e
  • не пересекает темно-зеленый ящик и не приземляется в красном поле, стоимость f
  • и d < f < c < e

введите описание изображения здесь

В настоящее время у меня есть следующие структуры данных и функции для расчета стоимости. Мне нужно рассчитать стоимость для данных прямоугольников (представленных координатами 4 xy), но в то же время найдите приблизительную/локальную оптимальную длину/ширину темно-зеленого прямоугольника (т.е. сжимайте или вырастите размер, удерживая ближайший угол прямоугольника фиксированным), чтобы стоимость была минимальной.

Конкретный пример - снимок экрана ниже. Меньший прямоугольник соответствует темно-зеленой коробке на рисунке. Зеленые линии - это лучи со стоимостью d, желтые линии стоят f, а бирюзовые линии - те, которые стоят c. Если я исправлю верхний левый угол внутреннего прямоугольника и уменьшу ширину, я могу уменьшить лучи turqoise от стоимости 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);
    }

Ответы

Ответ 1

Если я правильно понимаю вас, вы хотите изменить размер темно-зеленого прямоугольника таким образом, чтобы он сохранял общий центр с светло-зеленым прямоугольником, края которого оставались параллельными. Темно-зеленый прямоугольник никогда не останется красным в любой точке и никогда не будет меньше, чем светло-зеленый. Красный и светло-зеленый прямоугольник остаются постоянными. Вы только хотите пересчитать те лучи, которые могут изменить их стоимость, если вы измените темно-зеленый прямоугольник (теперь DGR...).

Итак, мое предложение таково: Пусть пустая строка std::vector<VRay*> пуста в начале и вторая переменная sum. В первом прогоне вычислите свои затраты так же, как и вы. Кроме того, для каждого луча можно решить, может ли он вообще измениться при изменении DGR.

Если это возможно, добавьте указатель к нему в вектор выше, иначе добавьте его текущую стоимость во вторую сумму. С этого момента вам нужно только пересчитать эти лучи в векторе указателя и добавить к этой новой сумме заранее рассчитанную сумму других.

Как решить, может ли луч изменить стоимость? Ну, конечно, те, кто не пересекает красный прямоугольник, не будут. Те, которые заканчиваются светло-зеленым прямоугольником, тоже не будут, а также пересекают светло-зеленый и красный прямоугольник. Таким образом, соответствующие лучи - это те, которые заканчиваются в красном прямоугольнике, но не внутри светло-зеленого, а также те, которые полностью пересекают красный, но не пересекают светло-зеленый.

Дальнейшая оптимизация может быть собрана, если вы считаете максимальную DGR (если она не обязательно параллельна красной): те линии, которые не пересекаются с этим максимальным прямоугольником или не заканчиваются перед ним, также не будут меняться.

Ответ 2

Я исправлю, что луч не может приземлиться в светло-зеленой коробке? то есть лучи прекращаются, когда они достигают светло-зеленой области? Существуют ли какие-либо правила, определяющие, попадает ли луч на красную область, на темно-зеленую зону или проходит через оба из них?

Если эти правила не зависят от размера автомобиля, а зависят только от относительного положения "конечной точки" луча, например, если лучи до середины передней части поверхности автомобиля всегда приземляются на свободное пространство вокруг автомобиля, то соотношение количества лучей со стоимостью 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.

Теперь я надеюсь, что мои предположения были правильными: -)

(Другие варианты, о которых я думал, на случай, если мои предположения ошибочны, группируют лучи вместе определенным образом и выполняют только вычисления на группу)