c++ 计算矩形与[0，1)^d相交产生的每个方框，其中后者被认为是环绕

vu8f3i0k 于 2023-03-14 发布在其他

关注(0)|答案(2)|浏览(88)

考虑盒子[0，1）^d环绕;例如在每个维度上为1 + .05 = .05。
给定[0，1）^d内的一个点x和一个正常数epsilon（0到.5之间），我想得到[0，1）^d内所有“盒子”的向量，这些盒子是通过用最小角x - (epsilon, ..., epsilon)和最大角x + (epsilon, ..., epsilon)包裹盒子而产生的。
我认为一张照片帮助很大;这里是d = 2的情况：

这里我们有9个例子，黑色的小矩形是由x和epsilon组成的;红色的是从环绕中产生的框。
我可以编写如下代码（我使用的是boost中的box模型，但这并不重要）：

template<typename T>
void foo(point<T, 2> const& x, T const& epsilon)
{
    assert(0 < epsilon && epsilon < T(1) / 2);

    std::array<boost::geometry::model::box<point<double, 2>>, 4> boxes;
    std::size_t box_count{};

    if (x[0] - epsilon < 0)
    {
        if (x[1] - epsilon < 0)
        {
            boxes[0].min_corner() = make_point(T{}, T{});
            boxes[0].max_corner() = x + make_point(epsilon, epsilon);

            boxes[1].min_corner() = make_point(1 + x[0] - epsilon, T{});
            boxes[1].max_corner() = make_point(T(1), x[1] + epsilon);

            boxes[2].min_corner() = x + make_point(1 - epsilon, 1 - epsilon);
            boxes[2].max_corner() = make_point(T(1), T(1));

            boxes[3].min_corner() = make_point(T{}, 1 + x[1] - epsilon);
            boxes[3].max_corner() = make_point(x[0] + epsilon, T(1));

            box_count = 4;
        }
        else if (x[1] + epsilon >= 1)
        {
            boxes[0].min_corner() = make_point(T{}, x[1] - epsilon);
            boxes[0].max_corner() = make_point(x[0] + epsilon, T(1));

            boxes[1].min_corner() = make_point(T{}, T{});
            boxes[1].max_corner() = make_point(x[0] + epsilon, x[1] + epsilon - 1);

            boxes[2].min_corner() = make_point(1 + x[0] - epsilon, T{});
            boxes[2].max_corner() = make_point(T(1), x[1] + epsilon - 1);

            boxes[3].min_corner() = make_point(1 + x[0] - epsilon, x[1] - epsilon);
            boxes[3].max_corner() = make_point(T(1), T(1));

            box_count = 4;
        }
        else
        {
            boxes[0].min_corner() = make_point(T{}, x[1] - epsilon);
            boxes[0].max_corner() = make_point(x[0] + epsilon, x[1] + epsilon);

            boxes[1].min_corner() = make_point(1 + x[0] - epsilon, x[1] - epsilon);
            boxes[1].max_corner() = make_point(T(1), x[1] + epsilon);

            rbox_count = 2;
        }
    }
    else if (x[0] + epsilon >= 1)
    {
        if (x[1] - epsilon < 0)
        {
            boxes[0].min_corner() = make_point(x[0] - epsilon, T{});
            boxes[0].max_corner() = make_point(T(1), x[1] + epsilon);

            boxes[1].min_corner() = make_point(x[0] - epsilon, 1 + x[0] - epsilon);
            boxes[1].max_corner() = make_point(T(1), T(1));

            boxes[2].min_corner() = make_point(T{}, 1 + x[1] - epsilon);
            boxes[2].max_corner() = make_point(x[0] + epsilon - 1, T(1));

            boxes[3].min_corner() = make_point(T{}, T{});
            boxes[3].max_corner() = make_point(x[0] + epsilon - 1, x[1] + epsilon);

            box_count = 4;
        }
        else if (x[1] + epsilon >= 1)
        {
            boxes[0].min_corner() = x - make_point(epsilon, epsilon);
            boxes[0].max_corner() = make_point(T(1), T(1));

            boxes[1].min_corner() = make_point(T{}, x[1] - epsilon);
            boxes[1].max_corner() = make_point(x[0] + epsilon - 1, T(1));

            boxes[2].min_corner() = make_point(T{}, T{});
            boxes[2].max_corner() = make_point(x[0] + epsilon - 1, x[1] + epsilon - 1);

            boxes[3].min_corner() = make_point(x[0] - epsilon, T{});
            boxes[3].max_corner() = make_point(T(1), x[1] + epsilon - 1);

            box_count = 4;
        }
        else
        {
            boxes[0].min_corner() = x - make_point(epsilon, epsilon);
            boxes[0].max_corner() = make_point(T(1), x[1] + epsilon);

            boxes[1].min_corner() = make_point(T{}, x[1] - epsilon);
            boxes[1].max_corner() = make_point(x[0] + epsilon - 1, x[1] + epsilon);

            box_count = 2;
        }
    }
    else
    {
        if (x[1] - epsilon < 0)
        {
            boxes[0].min_corner() = make_point(x[0] - epsilon, T{});
            boxes[0].max_corner() = x + make_point(epsilon, epsilon);

            boxes[1].min_corner() = make_point(x[0] - epsilon, 1 + x[1] - epsilon);
            boxes[1].max_corner() = make_point(x[0] + epsilon, T(1));

            box_count = 2;
        }
        else if (x[1] + epsilon >= 1)
        {
            boxes[0].min_corner() = x - make_point(epsilon, epsilon);
            boxes[0].max_corner() = make_point(x[0] + epsilon, T(1));

            boxes[1].min_corner() = make_point(x[0] - epsilon, T{});
            boxes[1].max_corner() = make_point(x[0] + epsilon, 1 - x[1] + epsilon);

            box_count = 2;
        }
        else
        {
            boxes[0].min_corner() = x - make_point(epsilon, epsilon);
            boxes[0].max_corner() = x + make_point(epsilon, epsilon);

            box_count = 1;
        }
    }
}

如你所见，这是相当复杂的。我已经分别考虑了每种情况。我的问题是：我们怎样才能简化它，使它适用于任意维数d？

c++

来源：https://stackoverflow.com/questions/75689770/compute-each-box-arising-from-intersecting-a-rectangle-with-0-1d-where-the

2条答案

按热度按时间

bsxbgnwa1#

我认为每个维度会分别以1或2的因子改变盒子的数量，因此，归纳起来，你可能会得到下面的结果（我尝试复制了9个二维测试用例，并添加了一个具有最大分割的三维测试用例）。

#include <iostream>
#include <vector>
using namespace std;

struct Box
{
   vector<pair<double,double>> bounds;
};

ostream & operator << ( ostream &out, const Box &box )
{
   out << "Box:  ";
   for ( int i = 0; i < box.bounds.size(); i++ ) out << box.bounds[i].first << " < x" << i + 1 << " < " << box.bounds[i].second << "      ";
   return out;
}

//======================================================================

vector<Box> makeBoxes( const vector<double> &x, double eps )      // x is multidimensional centre, eps is half-width
{
   vector<Box> boxes(1);

   // Do the wraparound for each dimension in turn
   for ( int d = 0; d < x.size(); d++ )
   {
      vector<Box> newboxes;
      double lower = x[d] - eps, higher = x[d] + eps;
      for ( Box b : boxes )
      {
         auto b1 = b, b2 = b;
         if ( lower < 0 )
         {
            b1.bounds.push_back( { 1.0 + lower, 1.0    } );   newboxes.push_back( b1 );
            b2.bounds.push_back( { 0.0        , higher } );   newboxes.push_back( b2 );
         }
         else if ( higher > 1.0 )
         {
            b1.bounds.push_back( { lower, 1.0          } );   newboxes.push_back( b1 );
            b2.bounds.push_back( { 0.0  , higher - 1.0 } );   newboxes.push_back( b2 );
         }
         else
         {
            b1.bounds.push_back( { lower, higher } );   newboxes.push_back( b1 );
         }
      }
      boxes = newboxes;
   }

   return boxes;
}

//======================================================================

int main()
{
   vector<vector<double>> testcases2d = {
      { 0.1, 0.1 },
      { 0.1, 0.9 },
      { 0.1, 0.5 },
      { 0.9, 0.1 },
      { 0.9, 0.9 },
      { 0.9, 0.5 },
      { 0.5, 0.1 },
      { 0.5, 0.9 },
      { 0.5, 0.5 }
                                        };
   double eps = 0.2;

   for ( int i = 0; i < testcases2d.size(); i++ )
   {
      cout << "2D Testcase " << i + 1 << '\n';
      vector<Box> box2d = makeBoxes( testcases2d[i], eps );
      for ( Box b : box2d ) cout << b << '\n';
      cout << "\n\n";
   }

   vector<double> testcase3d = { 0.9, 0.9, 0.9 };
   cout << "3D Testcase (corner): \n";
   vector<Box> box3d = makeBoxes( testcase3d, eps );
   for ( Box b : box3d ) cout << b << '\n';
}

2D Testcase 1
Box:  0.9 < x1 < 1      0.9 < x2 < 1      
Box:  0.9 < x1 < 1      0 < x2 < 0.3      
Box:  0 < x1 < 0.3      0.9 < x2 < 1      
Box:  0 < x1 < 0.3      0 < x2 < 0.3      

2D Testcase 2
Box:  0.9 < x1 < 1      0.7 < x2 < 1      
Box:  0.9 < x1 < 1      0 < x2 < 0.1      
Box:  0 < x1 < 0.3      0.7 < x2 < 1      
Box:  0 < x1 < 0.3      0 < x2 < 0.1      

2D Testcase 3
Box:  0.9 < x1 < 1      0.3 < x2 < 0.7      
Box:  0 < x1 < 0.3      0.3 < x2 < 0.7      

2D Testcase 4
Box:  0.7 < x1 < 1      0.9 < x2 < 1      
Box:  0.7 < x1 < 1      0 < x2 < 0.3      
Box:  0 < x1 < 0.1      0.9 < x2 < 1      
Box:  0 < x1 < 0.1      0 < x2 < 0.3      

2D Testcase 5
Box:  0.7 < x1 < 1      0.7 < x2 < 1      
Box:  0.7 < x1 < 1      0 < x2 < 0.1      
Box:  0 < x1 < 0.1      0.7 < x2 < 1      
Box:  0 < x1 < 0.1      0 < x2 < 0.1      

2D Testcase 6
Box:  0.7 < x1 < 1      0.3 < x2 < 0.7      
Box:  0 < x1 < 0.1      0.3 < x2 < 0.7      

2D Testcase 7
Box:  0.3 < x1 < 0.7      0.9 < x2 < 1      
Box:  0.3 < x1 < 0.7      0 < x2 < 0.3      

2D Testcase 8
Box:  0.3 < x1 < 0.7      0.7 < x2 < 1      
Box:  0.3 < x1 < 0.7      0 < x2 < 0.1      

2D Testcase 9
Box:  0.3 < x1 < 0.7      0.3 < x2 < 0.7      

3D Testcase (corner): 
Box:  0.7 < x1 < 1      0.7 < x2 < 1      0.7 < x3 < 1      
Box:  0.7 < x1 < 1      0.7 < x2 < 1      0 < x3 < 0.1      
Box:  0.7 < x1 < 1      0 < x2 < 0.1      0.7 < x3 < 1      
Box:  0.7 < x1 < 1      0 < x2 < 0.1      0 < x3 < 0.1      
Box:  0 < x1 < 0.1      0.7 < x2 < 1      0.7 < x3 < 1      
Box:  0 < x1 < 0.1      0.7 < x2 < 1      0 < x3 < 0.1      
Box:  0 < x1 < 0.1      0 < x2 < 0.1      0.7 < x3 < 1      
Box:  0 < x1 < 0.1      0 < x2 < 0.1      0 < x3 < 0.1

赞(0）回复(0）举报 2023-03-14

toiithl62#

你根本不需要考虑案例，如果你真的想很容易地概括，你需要正确地理解问题域。
在d维上，一个“盒子”基本上是由2 * d个坐标或原点和d个向量定义的区域的内部。

在1D中有一个点和到该点距离。
在2D中，你有一个点，一个垂直距离和一个水平距离。
在3D中你有一个点和三个矢量在向上，向前和向左的方向。

两个框的交点本身是一个框，其坐标由每条线与每个框的交点给出。
即对于每个维度

沿着该维度抓取两个长方体的2个向量及其起始坐标。
仅计算4个点的4轴坐标值（例如，仅计算x值）
在这4个点中找出最小值和最大值。
放弃那两个。你剩下的坐标位于交叉点内。

它最多应该有10行代码。
在更多伪代码中：

intersections = set()
for i in dimensions
   let c_1 = box1.point[i]
   let c_2 = box1.point[i] + box1.lengths[i]

   let d_1 = box2.point[i]
   let d_2 = box2.point[i] + box2.lengths[i]

   let min, max = find_min_max(c_1, c_2, d_1, d_2)
   let remaining = remove min max from [c_1, c_2, d_1, d_2]

    add remaining to set

这将给予你交点。然后你需要把这些点转换回一个点长度表示。但我留给你，因为它是直截了当的。注意，我假设框是轴对齐。

赞(0）回复(0）举报 2023-03-14

我来回答

c++ 计算矩形与[0，1)^d相交产生的每个方框，其中后者被认为是环绕

2条答案

相关问题

热门标签

最新问答