0

我的问题可以从两个不同的方面提出：一个是从数据结构的角度，另一个是从图像处理的角度。让我们从数据结构的角度开始：假设现在我有一个由几个小项目组成的组件，如下面的类所示：

class Component
{
public:
  struct Point
  { 
     float x_;
     float y_;
  };
  Point center;
  Point bottom;
  Point top;
}

在上面的例子中，Component 类是由 center、bottom 和 top（小项）等成员变量组成的。

现在我有一堆组件（组件的数量在 1000 到 10000 个之间），并且堆栈中的每个组件都被分配了不同的值，这意味着堆栈中没有重复的组件。然后，如果组件中的一个小项，例如图示类中的 'center' 是已知的，我们就可以在堆栈中找到唯一的组件。之后，我们可以检索组件中的其他属性。那么我的问题是，如何构建一个正确的容器数据结构来使搜索更容易？现在我正在考虑在STL（伪代码）中使用向量和查找算法：

vector<Component> comArray;
comArray.push_back( component1);
.....
comArray.push_back(componentn);
find(comArray.begin(), comArray.end(), center);

我想知道是否有更有效的容器来解决这个问题。

我也可以从图像处理的角度解释我的问题。在图像处理中，连接分量分析是物体识别的一个非常重要的步骤。现在对于我的应用程序，我可以获得图像中的所有连接组件，并且我还发现有趣的对象应该满足以下要求：它们的连接组件中心应该在特定范围内。因此，给定这个约束，我可以消除许多连接的组件，然后处理候选的组件。上述过程的关键步骤是在给定中心坐标约束的情况下如何搜索候选连通分量。任何想法将不胜感激。

4

4 回答 4

2

如果您需要能够相当快地获得它们，这里有一个对您来说有点奇怪的解决方案。

请注意，一般来说，这是一个糟糕的解决方案，但它可能适合您。

你可以做一个普通的vector< component >。或者这甚至可以是一个简单的数组。然后制作三张地图：

map< Point, Component *>center
map< Point, Component *>bottom
map< Point, Component *>top

用和作为键的所有可用值填充它们center，并提供指向相应组件的指针作为值（您也可以只使用向量中的索引，所以它会是）。bottomtopmap< Point, int >

之后，您只需使用center[Key],bottom[Key]或top[Key], 并获取您的值（如果您存储指针）或数组中的值的索引（如果您存储索引）。

我不会经常使用这种方法，但是如果值不会改变（因此您可以一次填充索引映射）并且数据量相当大（因此搜索未排序的向量很慢），它可能会起作用，并且您将需要经常搜索。

于 2012-07-27T09:40:26.097 回答
1

您可能需要空间索引数据结构。

于 2012-07-27T09:37:17.710 回答
0

我认为您想使用地图或hash_map根据“中心”值有效地查找组件。

std::map<Component::Point, Component> lookuptable;
lookuptable[component1.center] = component1;

....

auto iterator = lookuptable.find(someCenterValue)
if (iterator != lookuptable.end())
{
    componentN = iterator->second;
}

至于在给定协调范围内查找集合中的元素。有几种方法可以做到这一点。一种简单的方法是只拥有两个排序的组件列表数组，一个在 X 轴上排序，另一个在 Y 轴上排序。然后要找到匹配的元素，您只需在任一轴上进行二进制搜索，以找到最接近目标的元素。然后向上和向下扩展扫描阵列，直到超出范围。您还可以查看使用kd-tree并找到所有最近的邻居。

于 2012-07-27T09:34:42.310 回答
0

If you want to access them in const time and don't want to modify it. I think std::set is good choice for you code.

set<Component> comArray;
comArray.push_back( component1);
.....
comArray.push_back(componentn);
set<Component>::iterator iter = comArray.find(center)

of course, you should write operator== for class Component and nesting struct Point.

于 2012-07-27T09:54:00.447 回答