65.9K
CodeProject 正在变化。 阅读更多。
Home

高级多维区域模板类

valdok
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.91/5 (6投票s)

2009年4月11日

CPOL

7分钟阅读

viewsIcon

27141

downloadIcon

437

适用于任何坐标类型的多维区域的模板类。

引言

几年前，我必须编写一种视频钩子驱动程序。在那里面，我（除了其他事情）需要处理区域操作，例如查找交集、减法、合并区域等。

Win32 API 支持此类区域。操作区域的函数是CreateRectRgn、CreateEllipticRgn、EqualRgn、GetRgnBox、OffsetRgn、CombineRgn等。在我看来，这个 API 非常糟糕且不方便。它的实现是隐藏的，您必须处理句柄（HRGN）才能使用它。例如，当您需要查找两个区域的交集时，您必须创建一个新的空区域句柄，然后将其“填充”为交集。也就是说，

// Find intersection of hRgn1 and hRgn2
HRGN hIntersect = CreateRectRgn(0, 0, 0, 0); // create an empty region
CombineRgn(hIntersect, hRgn1, hRgn2, RGN_AND);

此外，如果您想遍历（区域组成的）矩形，API 会创建其数据的**副本**，而这并非总是需要的。

所以，我不想使用它。然而，即使我想使用，我也实际上无法使用，因为它在内核模式下根本不受支持。因此，我决定自己实现区域。

然后，我创建了一个非常简单的区域实现。但最近，我不得不再次处理区域，这一次，我决定使其更加灵活和高效。

多维模板区域

此区域实现的特点：

  1. 维度数量是模板参数。
  2. 每个维度的坐标类型也是模板参数。
  3. 区域以 N 维**立方体**表示。
  4. 对于整数坐标的二维区域，它是一个规则的平面区域，而**立方体**等同于RECT。
  5. 在每个轴上，坐标都组织在二叉搜索树中，因此所有操作（联合、交集等）都可以快速完成。
  6. 可以很好地处理复杂区域。

首先，让我们看看如何使用代码。区域类的定义如下：

template <typename T, class RgnInternal>
class Rgn_T;

Rgn_T 类有两个模板参数：第一个坐标的类型和基础区域类。这个基础类应如下指定：

  • 如果没有更多维度，则为RgnNull。
  • 如果需要更多维度，则使用带有其模板参数的Rgn_T。

以下是一些实例化示例：

// One-dimensional region with 'double' coordinate
typedef Rgn_T<double, RgnNull> MyRgn;

// Two-dimensional region. 1st coordinate is 'float', second is 'int'
typedef Rgn_T<float, Rgn_T<int, RgnNull> > MyRgn;

如果所有维度都使用相同类型的坐标，则有一个简化的定义：

template <typename T, int Dim>
class Rgn_Dim_T;

// 3-dimensional region, all the coordinates are 'long'
typedef Rgn_Dim_T<long, 3> MyRgn;

这些是区域类中定义的类型：

template <typename T, class RgnInternal>
class Rgn_T {
    // ...
public:

    // N-dimensional point
    struct Point
        :public RgnInternal::Point
    {
        T m_Value;
        // ...
    };

    // N-dimensional rectangular area.
    // Consists of two 'corner; points bounding the area.
    struct Cube {
        Point lo, hi; // low-hi
        // ...
    };

    // Class used to iterate through the region
    class Iterator
        :public Cube
        // ...
    {
    public:
        // ...
        bool Init(const Rgn_T& rgn);
        bool MoveNext();
    };
};

关键类型是Point。顾名思义，它是在 N 维空间中的一个点。可以使用这种方式访问特定坐标的值：

MyRgn::Point p;
p.get_Level<0>() = 0.0f; // 1st coordinate
p.get_Level<1>() = 44; // 2nd coorinate
p.get_Level<2>() = 12.76; // 3rd coorinate

并且，Cube 代表一个 N 维矩形区域。它由两个Point组成，描述了指定区域的“角”点。以下是区域支持的操作：

void Clear():
bool IsEmpty() const;
void AddCube(const Cube&);
bool GetBounds(Cube& c) const; // get the bounding box of the region
// If empty - returns false and zeroes 'c'
void Offset(const Point&); // Offset (move) the region by the given increment

bool IsEqual(const Rgn_T&) const;
void Swap(Rgn_T& rgn);

bool CubeInsidePart(const Cube& c) const; // Is a part of 'c' inside the region
bool CubeInsideFull(const Cube&c) const; // Is 'c' totally inside the region
bool PtInside(const Point&) const; // Is this point inside the region

void Subtract(const Rgn_T&);
void SubtractEx(const Rgn_T& rgn, Rgn_T& rgnIntersect);
// Same as above, the removed part
// is added to 'rgnIntersect'
void Copy(const Rgn_T&);
void Intersect(const Rgn_T&);
void Combine(const Rgn_T&);

总的来说，这个类提供了您对此类期望的功能——各种“光栅”操作、遍历Cube、布尔测试（例如PtInside）。

注意：它的接口用Point和Cube描述。没有直接提及坐标。

为简单起见，我们来看几个例子：

typedef Rgn_Dim_T<int, 1> MyRgn; // 1-dimensional, integer

MyRgn rgn1, rgn2;

MyRgn::Cube c;
c.lo.get_Level<0>() = 1;
c.hi.get_Level<0>() = 100;
rgn1.AddCube(c); // [1 .. 100]

c.lo.get_Level<0>() = 32;
c.hi.get_Level<0>() = 711;
rgn2.AddCube(c); // [32 .. 711]

rgn1.Intersect(rgn2); // intersect rgn1 by rgn2.

rgn1.GetBounds(c); // get the bounding (should be [32 .. 100]

这是一个更复杂的例子。在这里，区域是二维的。**注意**：在这里，我们在某个时候实际上是遍历其中一个区域，而不仅仅是获取其边界框。

typedef Rgn_Dim_T<int, 2> MyRgn; // 2-dimensional, integer

MyRgn rgn1, rgn2;

MyRgn::Cube c;
c.lo.get_Level<0>() = 1;
c.lo.get_Level<1>() = 10;
c.hi.get_Level<0>() = 100;
c.hi.get_Level<1>() = 15;
rgn1.AddCube(c);

c.lo.get_Level<0>() = 32;
c.lo.get_Level<1>() = 12;
c.hi.get_Level<0>() = 711;
c.hi.get_Level<1>() = 300;
rgn2.AddCube(c);

rgn1.Combine(rgn2);

MyRgn::Iterator it;
for (it.Init(rgn1); it; it.MoveNext())
{
    const MyRgn::Cube& curCube = it;
    // do something...
}

在这里，我们需要消除一个歧义。实际上，有几种方法可以将区域划分为Cube。我们的区域类通过**坐标顺序**进行此划分。第一个坐标被划分为*段*；然后，在每个段内，第二个坐标被划分为*子段*，依此类推。

例如，这里我们提供一个二维区域。根据 X、Y 坐标的解释方式，划分将不同：

实际区域 level<0>=X, level<1>=Y level<0>=Y, level<1>=X

如果此类区域用于绘图，则首选第二种选项。也就是说，level<0>应代表 Y 坐标，level<1>应代表 X。通过这种方式，我们得到更长的水平线，这对于绘图是可取的（绘图算法通常处理扫描线，其中线上的相邻像素在内存中是连续的）。

与 GDI 区域的比较

首先，此比较不公平，因为我们的区域是**多**维的，具有**任何**坐标类型，因此其用途 far 广泛。然而，我们可以实例化一个具有long坐标的二维区域，这（在某种意义上）等同于 GDI 区域。这就是我们可以将我们的区域与 GDI 区域进行比较的地方。

实际上，GDI 区域的实现方式与我们的区域类似，其中 Y 是第一个坐标，X 是第二个坐标。也就是说，整个区域被划分为 Y 坐标的段，并且在每个这样的段内，有 X 坐标的子段。特别是，我们的区域产生与 GDI 区域完全相同的划分（我甚至在单元测试中使用了这个事实）。

然而，在我们的区域和 GDI 区域的内存存储方式上存在巨大差异。我们的区域段是存储在二叉树结构中的动态分配节点。而 GDI 将其段存储在数组中，并且整个 GDI 区域数据是这些连续数组的**一个实心内存块**。因此，GDI 区域占用的内存显著更少。此外，在我看来，它们可以更快地构建（通过ExtCreateRegion），因为一个大的分配比许多小的分配更快。

但是这种方法也有其缺点。以这种方式存储的区域**不能修改**！也就是说，如果您想对区域执行操作（例如，向其中添加一个矩形），您就无法做到！相反，您只能构建一个**新**区域，该区域将是该区域与指定矩形的并集。这也（部分）解释了为什么 GDI 区域的 API 看起来如此奇怪。相比之下，我们的区域提供了高效的修改。

GDI 区域的另一个缺点是它们的实现是隐藏的。要“查看”区域内部，您必须调用GetRegionData，它会创建一个区域的**副本**。实际上，我不知道为什么实现是隐藏的。GDI 区域是在用户模式下实现的！

让我们总结一下：

GDI 区域的优点：

  • 更好的内存利用率（尤其是对于巨大的区域）
  • 可以更快地构建
  • 通用的绘图功能：大多数 GDI 绘图函数都使用相对于当前选定区域的工作

我们的区域的优点：

  • 灵活：可用于任意数量的维度和坐标类型
  • 友好且易于使用的 API（与极其丑陋的 GDI API 相比）
  • 允许就地修改区域；因此，复杂区域的调整速度要快得多
  • 显式迭代不需要复制区域（在我看来这真的很愚蠢）
  • 也可以用于绘图，尽管不是通用的（在迭代期间，必须为分区中的每个区域重复调用绘图函数）
  • 更多的功能：可以测试指定的矩形是否完全或部分包含在区域内；GDI 只有RectInRegion，这是一个部分变体
  • 对于小型区域往往更快（开销更少）；特别是，创建空区域对象很简单

结论

我希望有些人会发现这个区域类很有用。也许对于实现某些数学算法，N 维性和处理浮点坐标的能力很有用。

我将其用于内核模式下的绘图。在那里，GDI API 是无法访问的，但即使它是可访问的，我也更喜欢这种实现。尽管 GDI 区域**确实**有一些优势——对于我的特定情况，我们的区域更适合。

实际上，在我实现了（并使用了一段时间）这些区域，并在撰写本文之前，我花了时间学习 GDI 区域是如何实现的。然后，我非常惊讶地发现了这一点。然后，我才明白了为什么 GDI 区域的 API 会是那个样子。它只是反映了 GDI 中区域的实现方式。

我们的实现更好吗？嗯，这取决于区域的预期用途。在我了解到 GDI 如何实现其区域之后，我考虑为我的区域也制作一个额外的实现，这将更适合某些特定情况。

尽管如此，实现的差异只会对大量使用巨大区域的情况影响性能。从灵活性和可用性的角度来看，我们的实现看起来要好得多。

顺便说一句，如果您想了解区域实现的**代码层面**，您应该阅读这篇关于容器类的文章。它再次展示了它们的灵活性。

一如既往，欢迎批评和新想法。

© . All rights reserved.