#include "ePolygon.h"
struct VPoint
{
Point2d* Point;
VPoint* mPro;
VPoint* mNext;
VPoint* sortNext;//排序下一个
void SetNull(){ mPro = 0; mNext = 0; }
bool IsInBox(VPoint* pt);
bool IsInThis(VPoint* pt);
VPoint* MinPoint(); //找最小点
VPoint* ConvexPoint(); //找凸点
};
struct BOX
{
public:
BOX(Point2d* pt1, Point2d* pt2, Point2d* pt3);
double X1()const;
double Y1()const;
double X2()const;
double Y2()const;
private:
double m_X1, m_Y1, m_X2, m_Y2;
};
BOX::BOX(Point2d* pt1, Point2d* pt2, Point2d* pt3)
{
m_Y1 = m_X1 = DBL_MAX;
m_X2 = m_Y2 = DBL_MIN;
if (pt1->X < m_X1) m_X1 = pt1->X;
if (pt2->X < m_X1) m_X1 = pt2->X;
if (pt3->X < m_X1) m_X1 = pt3->X;
if (pt1->Y < m_Y1) m_Y1 = pt1->Y;
if (pt2->Y < m_Y1) m_Y1 = pt2->Y;
if (pt3->Y < m_Y1) m_Y1 = pt3->Y;
if (pt1->X > m_X2) m_X2 = pt1->X;
if (pt2->X > m_X2) m_X2 = pt2->X;
if (pt3->X > m_X2) m_X2 = pt3->X;
if (pt1->Y > m_Y2) m_Y2 = pt1->Y;
if (pt2->Y > m_Y2) m_Y2 = pt2->Y;
if (pt3->Y > m_Y2) m_Y2 = pt3->Y;
}
double BOX::X1()const{ return m_X1; }
double BOX::Y1()const{ return m_Y1; }
double BOX::X2()const{ return m_X2; }
double BOX::Y2()const{ return m_Y2; }
bool VPoint::IsInBox(VPoint* pt)
{
BOX box(Point, mPro->Point, mNext->Point);
return !(pt->Point->X > box.X2() || pt->Point->X<box.X1() || pt->Point->Y>box.Y2() || pt->Point->Y < box.Y1());
}
bool VPoint::IsInThis(VPoint* point)
{
if (!IsInBox(point)) return false;
double d1 = (mNext->Point->X - Point->X)*(point->Point->Y - Point->Y) - (mNext->Point->Y - Point->Y)*(point->Point->X - Point->X);
double d2 = (mPro->Point->X - mNext->Point->X)*(point->Point->Y - mNext->Point->Y) - (mPro->Point->Y - mNext->Point->Y)*(point->Point->X - mNext->Point->X);
double d3 = (Point->X - mPro->Point->X)*(point->Point->Y - mPro->Point->Y) - (Point->Y - mPro->Point->Y)*(point->Point->X - mPro->Point->X);
return ((d1 >= 1e-5&&d2 >= 1e-5&&d3 >= 1e-5) || (d1 <= 1e5&&d2 <= 1e5&&d3 <= 1e5));
}
VPoint* VPoint::MinPoint()
{
VPoint* min = this;
VPoint* p = mNext;
while (p != this)
{
if (p->Point->X < min->Point->X || (p->Point->X == min->Point->X&&p->Point->Y < min->Point->Y))min = p;
p = p->mNext;
}
return min;
}
VPoint* VPoint::ConvexPoint()
{
VPoint* pt = this;
while (true)
{
if ((pt->Point->X - pt->mPro->Point->X)*(pt->mNext->Point->Y - pt->Point->Y) - (pt->mNext->Point->X - pt->Point->X)*(pt->Point->Y - pt->mPro->Point->Y) > 0)
break;
pt = pt->mNext;
}
return pt;
}
bool AscSort(VPoint* a, VPoint* b)
{
if (a->Point.X < b->Point->X)return true;
return a->Point->X == b->Point->X&&a->Point->Y < b->Point->Y;
}
class mPoly
{
/*三角形剖分流程
1:原始去耳法,随机找一点判断凸角,
若不是，判断下一个角
若是，轮询所有点是否在三角形内，若在则判断下一个角
2:优化去耳法（以X最小点为例子记录）
a:以X或Y向找到最大或最小点作为起始点
找到X向最小点(X相等，取Y比较小)肯定为凸角
判断是否有点在三角形内
若有，找到离最小点最近的点，并分别与最近点形成两个闭环，执行找点
若没有，添加到三角新内形成新链，继续找最小点
去耳法无法解决多边形有洞口的情况
3:解决有洞口的多边形（以X最小点为例子记录）
说明:多边形为逆时针，洞口为顺时针
以X或Y向找到最大或最小点作为起始点
a：对多边形双循环链接处理
b：对所有点进行升序排序(X相等，取Y比较小),形成一个新的位置关系单链表
c：判断是否有点在三角形内
若有点 判断是否与参照点形成闭环
形成闭环，设置参照点下一个点为无效点，修改双向循环列表；
若不形成闭环，则生成新的双循环列表，整理位置点关系
若没有点，形成闭环，设置成无效点
*/
public:
vector<VPoint*> mpoints;
~mPoly();
mPoly(const Point2d* pts, const int count);
void AddCave(const Point2d* pts, const int count);
VPoint* Find(VPoint *pf);
void Clip(vector<VTriangle>*vtri);
void Clip(vector<VTriangle>*vtri, VPoint* pf);
void RemoveEar(vector<VTriangle>*vtri);//原始去耳法
void RemoveEar(vector<VTriangle>*vtri, VPoint* pf);
void RemoveEarOpt(vector<VTriangle>*vtri); //优化去耳法
void RemoveEarOpt(vector<VTriangle>*vtri, VPoint* pf);
};
mPoly::mPoly(const Point2d* pts, const int count)
{
//逆时针添加外边
AddCave(pts, count);
}
mPoly::~mPoly()
{
for (vector<VPoint*>::iterator it = mpoints.begin(); it != mpoints.end(); it++)
{
delete (*it);
}
}
ePolygon::~ePolygon()
{
((mPoly*)mData)->~mPoly();
}
//顺时针添加洞
void mPoly::AddCave(const Point2d* pts, const int count)
{
VPoint**pfs = new VPoint*[count];
for (int i = 0; i < count; i++)
{
pfs[i] = new VPoint;
pfs[i]->Point = pts + i;
if (i > 0)
{
pfs[i]->mPro = pfs[i - 1];
pfs[i - 1]->mNext = pfs[i];
}
mpoints.push_back(pfs[i]);
}
pfs[0]->mPro = pfs[count - 1];
pfs[count - 1]->mNext = pfs[0];
delete[] pfs;
}
VPoint* mPoly::Find(VPoint *pf)
{
if (!pf->mPro || !pf->mNext)return 0;
VPoint* pt = 0;
VPoint* spt = pf->sortNext;
while (spt)
{
//自身上下点
if (spt != pf->mPro&& spt != pf->mNext&&pf->IsInThis(spt))
{
pt = spt;
break;
}
spt = spt->sortNext;
}
return pt;
}
void mPoly::Clip(vector<VTriangle>* vtri)
{
//1.排序
std::sort(mpoints.begin(), mpoints.end(), AscSort);
//2.设置顺序
int i = 1;
for (; i < mpoints.size(); i++)
{
mpoints[i - 1]->sortNext = mpoints[i];
}
mpoints[i - 1]->sortNext = 0;
Clip(vtri, mpoints[0]);
}
void mPoly::Clip(vector<VTriangle>* vtri, VPoint* pf)
{
if (!pf->mPro || !pf->mNext)
{
if (pf->sortNext) Clip(vtri, pf->sortNext);
return;
}
VPoint* p = Find(pf);
//没有内点，形成闭环
if (pf->mNext->mNext == pf->mPro&&!p)
{
vtri->push_back(VTriangle(pf->Point, pf->mNext->Point, pf->mPro->Point));
pf->mNext->SetNull();
pf->mPro->SetNull();
pf->SetNull();
if (pf->sortNext)Clip(vtri, pf->sortNext);
}
else
{
if (!p)
{
vtri->push_back(VTriangle(pf->Point, pf->mNext->Point, pf->mPro->Point));
pf->mNext->mPro = pf->mPro;
pf->mPro->mNext = pf->mNext;
pf->SetNull();
if (pf->sortNext) Clip(vtri, pf->sortNext);
}
else
{
VPoint p1, p2;
p1.Point = pf->Point;
p2.Point = p->Point;
p1.mNext = &p2;
p2.mPro = &p1;
p1.mPro = pf->mPro;
p2.mNext = p->mNext;
pf->mPro = p;
p->mNext = pf;
p1.sortNext = pf->sortNext;
pf->sortNext = &p1;
p2.sortNext = p->sortNext;
p->sortNext = &p2;
Clip(vtri, pf);
}
}
}
void mPoly::RemoveEar(vector<VTriangle>*vtri)
{
RemoveEar(vtri, mpoints.at(0)->ConvexPoint());
}
void mPoly::RemoveEar(vector<VTriangle>*vtri, VPoint* pf)
{
if (pf->mNext->mNext == pf->mPro)
{
vtri->push_back(VTriangle(pf->Point, pf->mNext->Point, pf->mPro->Point));
}
else
{
VPoint* pt = 0;
VPoint* spt = pf->mNext;
while (spt != pf->mPro)
{
if (spt != pf->mPro&& spt != pf->mNext&&pf->IsInThis(spt))
{
pt = spt;
break;
}
spt = spt->mNext;
}
if (pt)//有点
{
RemoveEar(vtri, pf->mNext->ConvexPoint());
}
else
{
vtri->push_back(VTriangle(pf->Point, pf->mNext->Point, pf->mPro->Point));
pf->mNext->mPro = pf->mPro;
pf->mPro->mNext = pf->mNext;
RemoveEar(vtri, pf->mNext->ConvexPoint());
}
}
}
void mPoly::RemoveEarOpt(vector<VTriangle>*vtri)
{
RemoveEarOpt(vtri, mpoints.at(0)->MinPoint());
}
void mPoly::RemoveEarOpt(vector<VTriangle>*vtri, VPoint* pf)
{
if (pf->mNext->mNext == pf->mPro)
{
vtri->push_back(VTriangle(pf->Point, pf->mNext->Point, pf->mPro->Point));
}
else
{
VPoint* min = 0;
VPoint* p = pf->mNext->mNext;
VTriangle v(pf->Point, pf->mNext->Point, pf->mPro->Point);
while (p != pf->mPro)
{
if (v.IsInThis(p->Point))
{
if (!min) min = p;
else if ((p->Point->X < min->Point->X) ||
(p->Point->X == min->Point->X&&p->Point->Y < min->Point->Y)) min = p;
}
p = p->mNext;
}
if (!min)
{
vtri->push_back(v);
pf-
评论0