9
我在這裏讀了文章後實施的路徑簡化算法：拉默 - 道格拉斯 - 普克路徑簡化算法
http://losingfight.com/blog/2011/05/30/how-to-implement-a-vector-brush/
它的工作對我來說相當不錯生成優化的幾何級爲我的比賽。但是，我現在正在使用它來清理*路徑查找路徑，並且它有一個奇怪的邊緣情況，失敗了。
下面是它的工作截圖 - 優化從紅色圓圈到藍色圓圈的路徑。微弱的綠線是a *輸出，較淡的白線是最佳路徑。
這裏是它失敗的截圖：
這裏是我的代碼。我將文章中的ObjC代碼改編爲C++
注意：vec2fvec是std::vector< vec2<float> >，'real'只是一個typedef'd float。
void rdpSimplify(const vec2fvec &in, vec2fvec &out, real threshold)
{
if (in.size() <= 2)
{
out = in;
return;
}
//
// Find the vertex farthest from the line defined by the start and and of the path
//
real maxDist = 0;
size_t maxDistIndex = 0;
LineSegment line(in.front(), in.back());
for (vec2fvec::const_iterator it(in.begin()),end(in.end()); it != end; ++it)
{
real dist = line.distance(*it);
if (dist > maxDist)
{
maxDist = dist;
maxDistIndex = it - in.begin();
}
}
//
// If the farhtest vertex is greater than our threshold, we need to
// partition and optimize left and right separately
//
if (maxDist > threshold)
{
//
// Partition 'in' into left and right subvectors, and optimize them
//
vec2fvec left(maxDistIndex+1),
right(in.size() - maxDistIndex),
leftSimplified,
rightSimplified;
std::copy(in.begin(), in.begin() + maxDistIndex + 1, left.begin());
std::copy(in.begin() + maxDistIndex, in.end(), right.begin());
rdpSimplify(left, leftSimplified, threshold);
rdpSimplify(right, rightSimplified, threshold);
//
// Stitch optimized left and right into 'out'
//
out.resize(leftSimplified.size() + rightSimplified.size() - 1);
std::copy(leftSimplified.begin(), leftSimplified.end(), out.begin());
std::copy(rightSimplified.begin() + 1, rightSimplified.end(), out.begin() + leftSimplified.size());
}
else
{
out.push_back(line.a);
out.push_back(line.b);
}
}
我真的不知道怎麼回事。我的spidey意味着它在std :: copy調用中......在某些情況下，我必須複製垃圾。
編輯： 我已經重寫了算法，放棄任何使用迭代器和std :: copy，等等。它仍然以完全相同的方式失敗。
void rdpSimplify(const vec2fvec &in, vec2fvec &out, real threshold)
{
if (in.size() <= 2)
{
out = in;
return;
}
//
// Find the vertex farthest from the line defined by the start and and of the path
//
real maxDist = 0;
size_t maxDistIndex = 0;
LineSegment line(in.front(), in.back());
for (size_t i = 0, N = in.size(); i < N; i++)
{
real dist = line.distance(in[i]);
if (dist > maxDist)
{
maxDist = dist;
maxDistIndex = i;
}
}
//
// If the farthest vertex is greater than our threshold, we need to
// partition and optimize left and right separately
//
if (maxDist > threshold)
{
//
// Partition 'in' into left and right subvectors, and optimize them
//
vec2fvec left, right, leftSimplified, rightSimplified;
for (size_t i = 0; i < maxDistIndex + 1; i++) left.push_back(in[i]);
for (size_t i = maxDistIndex; i < in.size(); i++) right.push_back(in[i]);
rdpSimplify(left, leftSimplified, threshold);
rdpSimplify(right, rightSimplified, threshold);
//
// Stitch optimized left and right into 'out'
//
out.clear();
for (size_t i = 0, N = leftSimplified.size(); i < N; i++) out.push_back(leftSimplified[i]);
for (size_t i = 1, N = rightSimplified.size(); i < N; i++) out.push_back(rightSimplified[i]);
}
else
{
out.push_back(line.a);
out.push_back(line.b);
}
}