主页 > 未分类 > 任意二维图形(多边形)分割为子图形(子多边形)的算法及实现

任意二维图形(多边形)分割为子图形(子多边形)的算法及实现

在制作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.点的数据结构

class CLinePoint
{
public:
  CLinePoint(){
   index = -1;
   isInserted = false;
 }
public:
  double x;
 double y;
 int index;
  bool isInserted;
};

2.矩形(多边形)的数据结构

class CRectSeparate
{

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.线的数据结构

typedef list<CLinePoint> RECT_POINT_LIST;

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;
};

发表评论

邮箱地址不会被公开。 必填项已用*标注