c++ 如何放置n个对象(弧)周围的圆，而不重叠考虑他们的首选Angular ？

我需要在一个圆周上放置n个对象（弧）。每个对象都有其以弧度（度）表示的大小和一个以弧度表示的首选位置。已知对象大小之和〈PI*2，因此它们都可以放进去。顶部会有20-25个对象，通常数量较少，大小小于20度（每个对象可以有不同的大小）。
如果对象重叠，则需要将它们相互移动一点，直到它们不再重叠。
任何想法或方向挖掘是受欢迎的。
例如，如果我有五个2度的对象，首选位置在0度，我希望第三个对象在0度，前两个逆时针从0和4，5顺时针从0。我不确定这是否可能。（1，2，3，4，5）将它们相加成圆的顺序，它们可以与处于其它角位置的对象交错）。这种解决冲突的方式是首选的，但不是非常关键，我可以科普1在零度和4其他顺时针从它或逆时针或任何其他。主要目标是将所有对象放置在一个圆上，没有重叠，并且不远离首选Angular 。
为了检查弧是否重叠，我使用here中的这个小算法：

static constexpr double pi2 = 2*M_PI;
inline float posMod(float a, float n){
    return a - n * floor(a/n);
}

bool overlaps ( float arc1Start, float arc1Size, float arc2Start, float arc2Size ) {
    float c = posMod(arc2Start - arc1Start, pi2);
    float d = posMod(arc2Start + arc2Size - arc1Start, pi2);
    return arc1Size > c || c > d;//overlap. I've removed >=
    //if(b < c && c < d){
    //  //do not overlap
    //}
}

也许上下文有助于澄清一些事情。我有一些圆形的生物，它们可以在表面上进化出任意位置（以拉德为单位）和大小（以拉德为单位）的传感器（和其他东西）。我不希望它们重叠。也不希望传感器远离所需的位置。

这是我对我的问题的解决方案。它不是理想的，但我能想出的最好的。它不是最佳的错误，可以使用一些优化。它假设弧的大小之和小于360度。并不保证工作在所有如果它进入循环状态（最大迭代次数为360。可以更少，具体取决于可能的弧数。只是为了预防，最坏的情况是O（n^3），我认为其中n是要添加的弧的数目（不考虑可能的无限循环）。
完整代码：https://gist.github.com/avasilkov/8132266273a7edefe6df
视频外观：https://www.youtube.com/watch?v=-7QkNU0jZoI
算法要点：
首先，我有一个空的圆。然后，当我想添加一个新的弧，我检查它是否重叠任何已添加的弧。如果没有重叠捕捉-添加此弧，我们就完成了。

Arc arc(angleDestRef, preferredAngle, arcSize);
std::vector<int> ovs = getOverlapped(arc, -1);//overlapped arcs

if(ovs.size() == 0){
    arcs.push_back(arc);
    return;
}

如果有重叠（1个或更多），我迭代重叠的弧（包括我们要添加的弧、但它还没有在添加的弧中），并将它们的大小相加，找到它们位置的平均值。我再次检查重叠，但这次是新的弧，中心在平均值，大小是我刚刚找到的。（在求和时，我将新的更大圆弧的近似中心（refAngle）设为零（圆的起点），为了求平均值，我将所有位置归一化为-180 +180度之间）

float dummy;
Arc buffArc(dummy, 0.0f, 0.0f);
int iterCount = 0;
float refAngle = arc.cAngle;
while(iterCount++ < 360){
    float cAngle = normalizeAngle(arc.pAngle - refAngle);
    float size = arc.size;
    for(int i : ovs){
        cAngle += normalizeAngle(arcs[i].pAngle - refAngle);
        size += arcs[i].size;
    }
    cAngle /= ovs.size() + 1.0f;
    cAngle += refAngle;
    cAngle = posMod(cAngle, pi2);
    refAngle = cAngle;
    buffArc.set(cAngle, size);
    std::vector<int> ovsBefore = std::move(ovs);
    ovs = getOverlapped(buffArc, -1);

如果我得到相同的弧重叠，然后我退出while循环，并添加我的弧到主数组。

if(ovs.size() != ovsBefore.size()){
    continue;
}

bool stopIter = true;
loopy(i, ovs.size()){
    if(ovs[i] != ovsBefore[i]){
        stopIter = false;
        break;
    }
}
if(stopIter){
    iterCount = 10000;
    break;
}
}
arcs.push_back(arc);
ovs.push_back(arcs.size() - 1);

接下来我按CCW顺序对重叠的弧进行排序，并将它们的当前Angular 更改为新的Angular 。

auto& _arcs = arcs;
std::sort(ovs.begin(), ovs.end(),
     [buffArc, _arcs](const int a, const int b){
         return angleDiff(buffArc.cAngle, _arcs[a].pAngle) < angleDiff(buffArc.cAngle, _arcs[b].pAngle);
     }
);
float startAngle = buffArc.cAngle - buffArc.hs;
for(unsigned int i = 0; i < ovs.size(); i++){
    Arc& _arc = arcs[ovs[i]];
    startAngle += _arc.size;
    _arc.cAngle = startAngle - _arc.hs;
}

https://www.youtube.com/watch?v=nBMvQFBLv8k算法的另一个版本，其中首先我找到所有弧的最大尺寸，并使所有弧占用这个最大尺寸，而不是原来的（你可以看到宽透明扇区-空间占用，和不透明弧-实际弧大小）。但这是更糟糕的解决方案，如果你计算所有弧之间的总距离实际Angular 和他们的请求。

c++ 如何放置n个对象(弧)周围的圆，而不重叠考虑他们的首选Angular ？

1条答案

相关问题

热门标签

最新问答