判断一个简单图是否为平面图(c++ )

ment *f = createGraph(pointCount);
f->at(i)->push_back(*ltra);
f->at(*ltra)->push_back(i);
fragmentsVector->push_back(f);
parent[*ltra] = i;
colour[*ltra] = BLACK;
}
}
colour[i] = BLACK;
}
}
}
return fragmentsVector;
}

vector< face* >* getFacesFromOneCircle(circle*& c)
{
vector< face* > *faces = new vector< face* >;
face* tempFace = new face; ///面用链表表示即可, 链表按顺时针记录面的点
tempFace->push_back(MAXINT); ///带MAXINT(当作无穷)的面是外面
circle::iterator ctra = c->begin();
circle::iterator cend = c->end();
for (; ctra != cend; ctra++)
{
tempFace->push_back(*ctra);
}
faces->push_back(tempFace);
faces->push_back(c);
c = NULL; ///circle c已经转变为其中一个face, 防止通过指针c改变它
return faces;
}

///标记已经嵌入到平面的点
void markEmbedPoint(const circle *c, int pointCount)
{
memset(pointEmbed, false, sizeof(bool)*pointCount);
circle::const_iterator ctra = c->begin();
circle::const_iterator cend = c->end();
for (; ctra != cend; ctra++)
{
if (*ctra != MAXINT)
{
pointEmbed[*ctra] = true;
}
}
}
///每次将alpha path嵌入到平面时, 更新已经嵌入到平面的结点
void addPoint(const path *alphaPath)
{
path::const_iterator ptra = alphaPath->begin();
path::const_iterator pend = alphaPath->end();
for (; ptra != pend; ptra++)
{
pointEmbed[*ptra] = true;
}
}

///标记已经嵌入到平面的边
void markEmbedEdge(const circle *c, int pointCount)
{
for (int i=0; i<pointCount; i++)
{
for (int j=0; j<pointCount; j++)
{
edgeEmbed[i][j] = false;
}
}
circle::const_iterator ctra = c->begin();
circle::const_iterator cend = c->end();
circle::const_iterator pre;
for (pre=ctra++; ctra != cend; ctra++)
{
edgeEmbed[*pre][*ctra] = true;
edgeEmbed[*ctra][*pre] = true;
pre = ctra;
}
edgeEmbed[*(c->begin())][*pre] = true;
edgeEmbed[*pre][*(c->begin())] = true;
}
///每次将alpha path嵌入到平面时更新已经嵌入到平面的边
void addEdge(const path *alphPath)
{
path::const_iterator ptra = alphPath->begin();
path::const_iterator pend = alphPath->end();
path::const_iterator pre;
for (pre = ptra++; ptra!=pend; ptra++)
{
edgeEmbed[*pre][*ptra] = true;
edgeEmbed[*ptra][*pre] = true;
pre = ptra;
}
}


///fragment与已经嵌入平面的子图的公共点就是contact point
bool* findContactPoint(const fragment *f)
{
int pointCount = f->size();
bool *contactPoint = new bool[pointCount];
memset(contactPoint, false, sizeof(bool) * pointCount);
for(int i=0; i < pointCount; i++)
{
if (pointEmbed[i] && !(f->at(i)->empty()))
{
contactPoint[i] = true;
}
}
return contactPoint;
}
///找一个face所包含的所有点
bool *findFacePoint(const face *fa, int pointCount)
{
bool *facePoint