多个圆环组成的区域的合并

最近很忙，忙的连写日记的功夫都没有了。

有个项目的需求是需要把多个圆环的区域合并。得到包络线和内部空洞的线。

查了查google。类似的实现比较少见。简单的说说我的实现方法。

基本想法就是通过判断一段圆弧和圆环组的关系，来判断这段圆弧是否是属于合并后的包络线的一部分

如图，左边的圆盒右边的圆相交。则这两个圆就被分成了两段。

对外包络线，如上图。将所有圆环的外圆（粗线）相交。把每个圆都切成一段段的圆弧，如左边的黑色圆，则切成了黑色段和黑色+红色的两段。对每一段，我们测试这一段弧是否在其它圆环的大圆内部，如果这段圆弧不在其它的环的大圆内部（不包括内部小圆），则这段圆弧属于外包络线的一部分。否则不是。

内部透空的小圆的合并稍微麻烦一些。因为透空的部分，不光是小圆的弧，还会有大圆弧的参与。

考察小圆的圆弧，同样的，我们将小圆 和其它圆环的求交点，把小圆切成一段段的弧线（注意小圆和其它环求交的时候，就要跟这个环的大小圆都交一遍，而不光是小圆和小圆了）。如果这一段弧线不在这组圆环内（指的是环的内部，而不是大圆的内部），则表示这段弧是属于内包络线的一部分。

考察大圆的弧，大圆产生内包络线的原因主要是大圆会抵消一部分小圆的透空作用。所以同样的我们将大圆 和其它圆环的求交点，把小圆切成一段段的弧线--跟外包络不同，这次求交的时候，该大圆要和其它圆环的大小圆都求交，而不光是大圆对大圆。 对每一段圆弧，如果弧线不在环的内部，而且该段弧应该还需要位于某个环的小圆内部（看图就明白为什么了）。则该大圆弧也是内包络的一部分。

这里求圆弧在环的内部还是在大小圆内，有一个偷懒的方法。因为我们已经保证这段圆弧除了两个端点以外不和其它任何弧相交，所以只要用这段弧的中点来代替弧来作判断就好了。使得复杂性大大降低了。

以上是效果图，三个环合并成一个区域。

以下是主要代码

class CRingGroup
{
public:
bool load(const wchar_t* _ringGroupsFile)
{
xXmlDocument doc;
if(doc.load(_ringGroupsFile) == false )
return false;

xXmlNode::XmlNodes ringNodes;
doc.findAllNode(L"ring" , ringNodes);
if(ringNodes.size() == 0)
return false;

for(size_t i = 0 ; i < ringNodes.size() ; i ++)
{
xXmlNode* pNode = ringNodes[i];
xRing _ring;
_ring.m_InnerR = pNode->float_value(L"r1");
_ring.m_OutR = pNode->float_value(L"r2");
_ring.m_Center = pNode->get_value<float2>(L"center");
m_vRings.push_back(_ring);
}
}

void toSplineDrawer(CSplineDraw& drawer)
{
drawer.m_vArcs.clear();
for(int i = 0 ; i < m_vRings.size() ; i ++)
{
std::vector<float> CutPoints;
xRing& ring = m_vRings[i];
ring.toArcs(CutPoints , true , drawer.m_vArcs);
}

for(int i = 0 ; i < m_vRings.size() ; i ++)
{
std::vector<float> CutPoints;
xRing& ring = m_vRings[i];
ring.toArcs(CutPoints , false , drawer.m_vArcs);
}
}

void toInnerLine(std::vector<xArc>& vOut)
{
for(int i = 0 ; i < m_vRings.size() ; i ++)
{
std::vector<float> vCutPoints;
std::vector<xArc> vArcs;

//先来切内圆
xRing& _ring = m_vRings[i];
for(int j = 0 ; j < m_vRings.size() ; j ++)
{
if(j == i) continue;
xRing& _ring2 = m_vRings[j];
_ring.CutByCircle(_ring2.m_Center , _ring2.m_OutR , vCutPoints , false );
_ring.CutByCircle(_ring2.m_Center , _ring2.m_InnerR , vCutPoints , false);
}

_ring.toArcs(vCutPoints , false , vArcs);

//内圆的弧，必须在所有的外圆的外部。
for(int iArc = 0 ; iArc < vArcs.size() ; iArc ++)
{
xArc& _arc = vArcs[iArc];
bool bInRing = false;
for(int k = 0 ; k < m_vRings.size() ; k ++)
{
if( k == i ) continue;
xRing& _ring2 = m_vRings[k];
if( true == _ring2.IsInRing( _arc ) )
{
bInRing = true;
}
}

//////////////////////////////////////////////////////////////////////////
if(bInRing == false)
{
vOut.push_back(_arc);
}
}

//内圆切完了。来切外圆套在其它内圆中的部分。
vCutPoints.clear();
vArcs.clear();
for(int j = 0 ; j < m_vRings.size() ; j ++)
{
if(j == i) continue;
xRing& _ring2 = m_vRings[j];
_ring.CutByCircle(_ring2.m_Center , _ring2.m_OutR , vCutPoints , true );
_ring.CutByCircle(_ring2.m_Center , _ring2.m_InnerR , vCutPoints , true);
}

_ring.toArcs(vCutPoints , true , vArcs);

//内圆的弧，必须在所有的外圆的外部。
for(int iArc = 0 ; iArc < vArcs.size() ; iArc ++)
{
xArc& _arc = vArcs[iArc];
bool bInRing = false;
bool bInSmallRing = false;
for(int k = 0 ; k < m_vRings.size() ; k ++)
{
if( k == i ) continue;
xRing& _ring2 = m_vRings[k];
if( true == _ring2.IsInRing( _arc ) )
{
bInRing = true;
}

if( true == _ring2.IsInSmallRing( _arc) )
{
bInSmallRing = true;
}
}

//////////////////////////////////////////////////////////////////////////
if(bInRing == false && bInSmallRing == true)
{
vOut.push_back(_arc);
}
}
}
return ;
}

void toOutLine(std::vector<xArc>& vOut)
{
//return ;
for(int i = 0 ; i < m_vRings.size() ; i ++)
{
std::vector<float> vCutPoints;
xRing& _ring = m_vRings[i];
for(int j = 0 ; j < m_vRings.size() ; j ++)
{
if(j == i) continue;
xRing& _ring2 = m_vRings[j];
_ring.CutByCircle(_ring2.m_Center , _ring2.m_OutR , vCutPoints , true);

}

std::vector<xArc> vArcs;
_ring.toArcs(vCutPoints , true , vArcs);

//判断生成的圆弧是不是在内部。
for(int iArc = 0 ; iArc < vArcs.size() ; iArc ++)
{
xArc& _arc = vArcs[iArc];
bool bInRing = false;
for(int k = 0 ; k < m_vRings.size() ; k ++)
{
if( k == i ) continue;
xRing& _ring2 = m_vRings[k];
if( true == _ring2.IsInOutRing(_arc ) )
{
bInRing = true;
}
}

//////////////////////////////////////////////////////////////////////////
if(bInRing == false)
{
vOut.push_back(_arc);
}
}
}
return ;
}
public:
std::vector<xRing> m_vRings;
};