任意二维图形(多边形)分割为子图形(子多边形)的算法及实现
在制作litecad图形填充时，遇到问题，需要对一个四点矩形进行分割填充。题设如下：
一个四点矩形，画任意多条曲线(采样出构成线的点)切割，要求求出所有子区域边框的点。
一、分割思想
经过研究后，发现不论画多少条线都可以当作一条线处理，将所有的线依次首尾相接(构想衔接处不通过矩形，即在外侧)，与矩形相交产生多个交点，每对交点构成两个分割子多边形。具体实现思想如下：
1.初始化
按照顺序（顺时针或逆时针），将多边形的顶点记录到point_list中，构成边框线，将所有的分割线按照顺序（采样顺序,如鼠标画笔移动时的采样）存入cut_list中。
2.执行分割
依次取出边框线point_list中的相邻两个点，依次去除cut_list中相邻的两个点，计算交点，不存在返回NULL，存在返回交点坐标(判断交点范围，不在四个点之间仍返回NULL)，存在交点时判断是否是已存在的点，如果不存在则加入到point_list和cut_list的相应位置。找到第一个交点后继续寻找第二个交点，找到后停止。对point_list和cut_list重新索引，找到两个交点(first、second)在point_list和cut_list的索引。构造新的point_list(子多边形边框)从first开始直到second将cut_list加入到子point_list中，之后顺序加入从second到first父point_list之间的点，构成了子多边形first_child，再次逆序加入从second到first父point_list之间的点，构成了子多边形second_child。弹出cut_list中second及second之前的所有点。至此一次分割完成。
3.递归分割
将两个子多边形分别调用第二步的方法，用cut_list（或cut_list的拷贝）分割，找到两个点后继续递归，找不到两个点后及不可分割返回。所有的子多边形找不到两个交点时即分割完成。
二、数据结构
1.点的数据结构
{
public:
CLinePoint(){
index = -1;
isInserted = false;
}
public:
double x;
double y;
int index;
bool isInserted;
};
2.矩形(多边形)的数据结构
{
public:
CRectSeparate();
~CRectSeparate();
friend class CRectLine;
public:
BOOL hasChild();
void separate(RECT_POINT_LIST* point_list);
void freeList(RECT_POINT_LIST* point_list);
public:
CRectSeparate* first_child;
CRectSeparate* second_child;
BOOL isSeparated;
CRectLine mRectLine;
};
3.线的数据结构
class CRectLine
{
public:
CRectLine();
~CRectLine();
void clear();
void sort();
void sortCutLine();
CLinePoint* findNode(RECT_POINT_LIST* pointList);
CLinePoint* findNextNode();
CLinePoint* getCrossPoint(CLinePoint* p1, CLinePoint* p2, CLinePoint* p3, CLinePoint* p4);
BOOL isInLine(CLinePoint* p1, CLinePoint* p2, CLinePoint* p3);
BOOL isInLine(RECT_POINT_LIST* pointList, CLinePoint* point);
int isRayIntersect(double x,double y,double X1,double Y1,double X2,double Y2);
int isInRegion(CLinePoint* point, RECT_POINT_LIST* region);
void copy(RECT_POINT_LIST* pointList, RECT_POINT_LIST* target);
BOOL isShortDistance(CLinePoint* p1, CLinePoint* p2);
void checkCutPoint();
void fixCutLine();
void freeList(RECT_POINT_LIST* point_list);
public:
RECT_POINT_LIST* mPointList;
RECT_POINT_LIST* cutList;
RECT_POINT_LIST* mCutLine;
CLinePoint* lastPoint;
int cutIndex;
double EPS;
};
Tags: 图像分割，图形分割，矩形分割
发表评论