请教：两个多边形A与B相交后，想要得到一个新的多边形C，怎么实现？

Question

请教：两个多边形A与B相交后，想要得到一个新的多边形C，怎么实现？
A多边形的点集 CPoint *aPts　　其中点个数　N1
B多边形的点集 CPoint *bPts　　其中点个数　N2
现在怎么实现新的多边形C？
A与B相交的点就不应该在C中出现，因最后想将多边形做平滑处理，有在多边形内的点平滑处理时可能会有问题。    %%%%%%%%%%%%
    %          %
    %          %           %%%%%%%%%%%%
    %          %            %         %
    %          %              %%%%%%%%%
    %          %                
    %%%%%%%%%%%%
相交后的多边形象下面这样    %%%%%%%%%%%%
    %          %
    %          %%%%%%%%%
    %                  %
    %          %%%%%%%%%
    %          %                
    %%%%%%%%%%%%
还有，两多边形相交可能不只一处，可能多处相交，请教怎么实现，谢谢指点。再问：
写画图程序都有那些比较好的图形算法说明书？

Answer 1

GDI中的Region，直接处理多边形，可以用：
CombineRgn

Answer 2

to  回复人：Mackz(在相互) ( 四星(高级)) 信誉：117
我能再取出新多边形的点吗？因为我后面要平滑处理，现用的平滑处理方法是传入点数组然后做计算，没有直接对RGN进行计算的。

Answer 3

//参数：XY1Array多边形A，XY2多边形B，N2是多边形B的顶点个数，*retPt是新的多边形C
//返回：新多边形顶点个数
int CalcPolygon3(CArray<class CPoint,class CPoint> &XY1Array,CPoint*XY2,int N2,CPoint *retPt)
{
int i,j;
int iCnt;
CRgn rgn;
float xc,yc;
CPoint twoPt1,twoPt2;
rgn.CreatePolygonRgn(XY2,N2,ALTERNATE)
iCnt = XY1Array.GetSize();
for(i=0; i<iCnt-1; i++)
{
int inum = 0;
CPoint tempPt1 = XY1Array.GetAt(i);
CPoint tempPt2 = XY1Array.GetAt(i+1);
if(rgn.PtInRegion(tempPt1)) inum++;
if(rgn.PtInRegion(tempPt2)) inum++;
if(inum==1)
{//计算相交线
//判断是否相交于在二条直线上：
for (j=0; j<N2; j++)
{
twoPt1 = XY2[j];
if(j != N2-1)
{
twoPt2 = XY2[j+1];
}
else
{
twoPt2 = XY2[0];
}
int t= testCross(
tempPt1.x, tempPt1.y,
tempPt2.x, tempPt2.y,
twoPt1.x, twoPt1.y,
twoPt2.x, twoPt2.y,
xc, yc);
if (t) 
{//存储交点 xc yc 
}
}
}
}
return 1;
}
上面是我写的方法，还远远没有完，没有清晰的思路.

Answer 4

testCross计算返回1表两线段相交，0表不相交。

Answer 5

你这不是交集 是并集
生成多边形 createployrgn 差不多是这个函数名 具体查看 apitext
CombineRgn 完全可以利用可以把要生成的多边形 加个底色 然后按底色采集 像素点

Answer 6

求平面区域的交和并，在GIS中有用处，偶用java做过

Answer 7

以前做过类似的问题。TRUE TYPE FONT 就是想你说的这种坐标序列组成的笔画，当时是把相交的笔画合并为一个。求出交点，然后生成新的序列。

Answer 8

gdiplus: Graphics graphcs(hdc);
SolidBrush sBrush( Color(0,255,102) );
Pen    pen1( Color( 255,0,102 ) , 2 );
Pen    pen2( Color( 0,0,102 ) , 2 );
Rect rc1,rc2;
rc1.X = 940;
rc1.Y = 330;
rc1.Height = 30;
rc1.Width = 50; rc2.X = 950;
rc2.Y = 340;
rc2.Height = 30;
rc2.Width = 50; Region rgn1(rc1);
Region rgn2(rc2); graphcs.DrawRectangle( &pen1,rc1 );
graphcs.DrawRectangle( &pen2,rc2 ); rgn1.Union(&rgn2);//作为参数
graphcs.FillRegion( &sBrush , &rgn1 );

Answer 9

如果是凸多边形好办，但任意多边形有可能是凹的，所以最好是把多边形分解为多个三角形，三角形没有凸凹之说，比较好分析。两个多边形都分解成几个三角形后就容易了。A多边形假设分成了A1,A2,A3三个三角形，B多边形假设分成了B1,B2,B3,B4四个三角形。那么就拿A1依次跟B1,B2,B3,B4求交，A2,A3也照此办理。这是第一步，问题转化为求三角形的交
//-------------------------
三角形的求交是很容易的了

Answer 10

谢谢各位，我现在是这样写的，判断其中一个多边形的各边（相邻两点）是否与另一个多边形相交:
如果两点全在多边形内的点，不处理，
如有相交，计算交点，设两点A1 与 A2,交点为C, A1在多边形内,则将C点插入一个 oneArray(“CArray<class CPoint,class CPoint>集合变量”) 中,再将A2插入;
如果两点都不在多边形内,则将A1插入oneArray中;
在每次相交的情况,要将前面的点集放到一个oneArray,将oneArray存储到一个m_PtList1(“CTypedPtrList<CObList,CSideLine*>集合变量,CSideLine类中有变量存oneArray”) 中。这样处理相当于交点将多边形分成了一些线段，象上面我用星画的图形只有两个交点，多边形只分成了一段，如果右边的图形再长一些，那组合的图形就象下面这样，每个多边形被分成为两部分
　　　********
*******　　　*********
*　　　　　　　　　　*
*******　　　*********
　　　*　　　*
　　　********
上面这样计算完一个多边形的分离的点集,再对另一个多边形做相同的处理. 
之后再以两个多边形的交点来判断他们是否应该连接起来.代码太长，也还没有运行过去，运行过去后就结帖，我总觉得这个方法不保险，想用VC提供的方法来处理，看帮助GetRegionData方法可以得到多边形的矩形，我不知道我取那些矩形上的那一个点做为我新多边形的点，我需要多边形边上的一些拐点，要按顺序的，这样后面我画图时也才是正确的多边形，最后我要对新多边形做平滑处理，处理时传入这些点会计算出新的点集，不知那位用过GetRegionData的给解释一下，VC自身方法能得到的点我想是最准确也最快的。代码先粘出来，没时间看代码的看前面文字就可以了。
int CalcPolygon3(CArray<class CPoint,class CPoint> &XY1Array,CPoint*XY2,int N2,CPoint *retPt)
{
int i,j,itmp;
int iCnt;
CRgn rgn1,rgn2;
long xc,yc;
CPoint onePt1,onePt2,twoPt1,twoPt2;
CTypedPtrList<CObList,CSideLine*> m_PtList1;
CTypedPtrList<CObList,CSideLine*> m_PtList2;
CArray<class CPoint,class CPoint> oneArray; BOOL b1,b2,bIns ;
b1 = b2 = bIns = FALSE;
CSideLine *sline = new CSideLine;
rgn2.CreatePolygonRgn(XY2,N2,ALTERNATE);
iCnt = XY1Array.GetSize();
for(i=0; i<iCnt-1; i++)
{

int inum = 0;
b1 = b2 = FALSE;
onePt1 = XY1Array.GetAt(i);
onePt2 = XY1Array.GetAt(i+1);
if(rgn2.PtInRegion(onePt1))
{
b1 = TRUE;
inum++;
}
if(rgn2.PtInRegion(onePt2))
{
b2 = TRUE;
inum++;
}
if(inum==0)
{
bIns = TRUE;
sline->m_pointArray.Add(onePt1);
}
else if(inum==1)
{//计算相交线 
bIns = TRUE;
for (j=0; j<N2; j++)
{
twoPt1 = XY2[j];
if(j != N2-1)
{
twoPt2 = XY2[j+1];
}
else
{
twoPt2 = XY2[0];
}
int t= testCross(
onePt1.x, onePt1.y,
onePt2.x, onePt2.y,
twoPt1.x, twoPt1.y,
twoPt2.x, twoPt2.y,
xc, yc);
if (t) 
{//存储交点 xc yc 
//XY1Array.InsertAt(i,CPoint(xc,yc));
break;//因为只有一个交点，所以跳出循环
}
}
if(!b1)
{
sline->m_pointArray.Add(onePt1);
sline->m_pointArray.Add(CPoint(xc,yc));
m_PtList1.AddTail(sline);
bIns = FALSE;
sline = new CSideLine;
}
else
{
sline->m_pointArray.Add(CPoint(xc,yc));
sline->m_pointArray.Add(onePt2);
}
}
}
if(bIns)
{
m_PtList1.AddTail(sline);
}
//分割第二个数组
CPoint *XY1 = new CPoint[iCnt];
for(i=0; i<iCnt; i++)
{
XY1[i] = XY1Array.GetAt(i);
}
sline = new CSideLine;
rgn1.CreatePolygonRgn(XY1,iCnt,ALTERNATE);
for(i=0; i<N2-1; i++)
{
int inum = 0;
b1 = b2 = FALSE;
twoPt1 = XY2[i];
twoPt2 = XY2[i+1];
if(rgn1.PtInRegion(twoPt1))
{
b1 = TRUE;
inum++;
}
if(rgn1.PtInRegion(twoPt2))
{
b2 = TRUE;
inum++;
}
if(inum==0)
{
bIns = TRUE;
sline->m_pointArray.Add(twoPt1);
}
else if(inum==1)
{//计算相交线 
bIns = TRUE;
for (j=0; j<iCnt; j++)
{
onePt1 = XY1[j];
if(j != iCnt-1)
{
onePt2 = XY1[j+1];
}
else
{
onePt2 = XY1[0];
}
int t= testCross(
twoPt1.x, twoPt1.y,
twoPt2.x, twoPt2.y,
onePt1.x, onePt1.y,
onePt2.x, onePt2.y,
xc, yc);
if (t) 
{//存储交点 xc yc 
break;//因为只有一个交点，所以跳出循环
}
}
if(!b1)
{
sline->m_pointArray.Add(twoPt1);
sline->m_pointArray.Add(CPoint(xc,yc));
m_PtList2.AddTail(sline);
bIns = FALSE;
sline = new CSideLine;
}
else
{
sline->m_pointArray.Add(CPoint(xc,yc));
sline->m_pointArray.Add(twoPt2);
}
}
}
if(bIns)
{
m_PtList2.AddTail(sline);
}
//下面是将两个list中的对象合成一个，合成时对比交点就可以了，交点相通说明其应是连接的点
POSITION pos = m_PtList1.GetHeadPosition();
BOOL bFind = FALSE;
while( pos!= NULL)
{
sline = m_PtList1.GetNext(pos);
onePt1 = sline->m_pointArray.GetAt(0);
POSITION pos2 = m_PtList2.GetHeadPosition();
while(pos2 != NULL)
{
CSideLine *sline2 = m_PtList2.GetNext(pos2);
itmp = sline2->m_pointArray.GetSize();
twoPt1 = sline2->m_pointArray.GetAt(0);
twoPt2 = sline2->m_pointArray.GetAt(itmp-1);
if(onePt1 == twoPt1)
{
for(i=1; i<itmp; i++)//相等的点就不再插入
{
sline->m_pointArray.Add(sline2->m_pointArray.GetAt(i)); 
}
break;
}
else if(onePt1 == twoPt2)
{
for(i=itmp-2; i>=0; i--)//相等的点就不再插入
{
sline->m_pointArray.Add(sline2->m_pointArray.GetAt(i)); 
}
break;
}
}
oneArray.Append(sline->m_pointArray);
}
itmp = oneArray.GetSize();
retPt = new CPoint[itmp];
for(i=0; i<itmp; i++)
{
onePt1 = oneArray.GetAt(i);
retPt[i] =  onePt1 ;
}
return itmp;
}

Answer 11

DWORD dwSize ;
dwSize = ::GetRegionData(rgnA, 0, NULL);
if (0 == dwSize)
{
return ;
}
BYTE *pData   =   new   BYTE[dwSize];  
if   (NULL   ==   pData)  
{  
return   ;  
}  

::GetRegionData(rgnA,   dwSize,   (RGNDATA*)pData);  
//C:   Get   the   number   of   rectangles   contained   in   the   Region.  
RGNDATA   *prData   =   (RGNDATA*)pData;  
RECT         *prRectangles   =   (RECT*)prData->Buffer;  
UINT   nCount   =   prData->rdh.nCount;  
//C:   Paint   each   rectangle   in   the   region   with   an   alternating   brush   color.  
UINT   index   =   0;  
for   (;index   <   nCount;   index++)  
{  
} GetRegionData得到的是水平的巨形,如果是凹多边形,情况就更复杂.

Answer 12

Weiler－Atherton任意多边形裁剪
Sutherland-Hodgman多边形裁剪