Diff: clipper.cpp - clipper.cpp

	clipper.cpp	clipper.cpp
	/************************************************************************ ***	/************************************************************************ ***
	* *	* *
	* Author : Angus Johnson *	* Author : Angus Johnson *

	* Version : 4.9.4	* Version : 4.9.6
	*	*
	* Date : 2 November 2012	* Date : 9 November 2012
	*	*
	* Website : http://www.angusj.com *	* Website : http://www.angusj.com *
	* Copyright : Angus Johnson 2010-2012 *	* Copyright : Angus Johnson 2010-2012 *
	* *	* *
	* License: *	* License: *
	* Use, modification & distribution is subject to Boost Software License Ver 1. *	* Use, modification & distribution is subject to Boost Software License Ver 1. *
	* http://www.boost.org/LICENSE_1_0.txt *	* http://www.boost.org/LICENSE_1_0.txt *
	* *	* *
	* Attributions: *	* Attributions: *
	* The code in this library is an extension of Bala Vatti's clipping algorit hm: *	* The code in this library is an extension of Bala Vatti's clipping algorit hm: *
	* "A generic solution to polygon clipping" *	* "A generic solution to polygon clipping" *

	skipping to change at line 369	skipping to change at line 369

	inline bool PointsEqual( const IntPoint &pt1, const IntPoint &pt2)	inline bool PointsEqual( const IntPoint &pt1, const IntPoint &pt2)
	{	{
	return ( pt1.X == pt2.X && pt1.Y == pt2.Y );	return ( pt1.X == pt2.X && pt1.Y == pt2.Y );
	}	}
	//------------------------------------------------------------------------- -----	//------------------------------------------------------------------------- -----

	bool Orientation(OutRec *outRec, bool UseFullInt64Range)	bool Orientation(OutRec *outRec, bool UseFullInt64Range)
	{	{
	//first make sure bottomPt is correctly assigned ...	//first make sure bottomPt is correctly assigned ...

	OutPt opBottom = outRec->pts, op = outRec->pts->next;	OutPt *opBottom = outRec->pts;
		if (!opBottom) return true;
		OutPt *op = outRec->pts->next;
	while (op != outRec->pts)	while (op != outRec->pts)
	{	{
	if (op->pt.Y >= opBottom->pt.Y)	if (op->pt.Y >= opBottom->pt.Y)
	{	{
	if (op->pt.Y > opBottom->pt.Y \|\| op->pt.X < opBottom->pt.X)	if (op->pt.Y > opBottom->pt.Y \|\| op->pt.X < opBottom->pt.X)
	opBottom = op;	opBottom = op;
	}	}
	op = op->next;	op = op->next;
	}	}
	outRec->bottomPt = opBottom;	outRec->bottomPt = opBottom;

	skipping to change at line 432	skipping to change at line 434
	for (int i = 0; i < highI; ++i)	for (int i = 0; i < highI; ++i)
	a += (double)poly[i].X * poly[i+1].Y - (double)poly[i+1].X * poly[i]. Y;	a += (double)poly[i].X * poly[i+1].Y - (double)poly[i+1].X * poly[i]. Y;
	return a/2;	return a/2;
	}	}
	}	}
	//------------------------------------------------------------------------- -----	//------------------------------------------------------------------------- -----

	double Area(const OutRec &outRec, bool UseFullInt64Range)	double Area(const OutRec &outRec, bool UseFullInt64Range)
	{	{
	OutPt *op = outRec.pts;	OutPt *op = outRec.pts;

		if (!op) return 0;
	if (UseFullInt64Range) {	if (UseFullInt64Range) {
	Int128 a(0);	Int128 a(0);
	do {	do {
	a += (Int128(op->prev->pt.X) * Int128(op->pt.Y)) -	a += (Int128(op->prev->pt.X) * Int128(op->pt.Y)) -
	Int128(op->pt.X) * Int128(op->prev->pt.Y);	Int128(op->pt.X) * Int128(op->prev->pt.Y);
	op = op->next;	op = op->next;
	} while (op != outRec.pts);	} while (op != outRec.pts);
	return a.AsDouble() / 2;	return a.AsDouble() / 2;
	}	}
	else	else

	skipping to change at line 619	skipping to change at line 622
	ip.Y = edge1.ybot;	ip.Y = edge1.ybot;
	} else	} else
	{	{
	b1 = edge1.ybot - (edge1.xbot/edge1.dx);	b1 = edge1.ybot - (edge1.xbot/edge1.dx);
	ip.Y = Round(ip.X/edge1.dx + b1);	ip.Y = Round(ip.X/edge1.dx + b1);
	}	}
	} else	} else
	{	{
	b1 = edge1.xbot - edge1.ybot * edge1.dx;	b1 = edge1.xbot - edge1.ybot * edge1.dx;
	b2 = edge2.xbot - edge2.ybot * edge2.dx;	b2 = edge2.xbot - edge2.ybot * edge2.dx;

	b2 = (b2-b1)/(edge1.dx - edge2.dx);	double q = (b2-b1)/(edge1.dx - edge2.dx);
	ip.Y = Round(b2);	ip.Y = Round(q);
	ip.X = Round(edge1.dx * b2 + b1);	if (std::fabs(edge1.dx) < std::fabs(edge2.dx))
		ip.X = Round(edge1.dx * q + b1);
		else
		ip.X = Round(edge2.dx * q + b2);
	}	}

	if (ip.Y < edge1.ytop \|\| ip.Y < edge2.ytop)	if (ip.Y < edge1.ytop \|\| ip.Y < edge2.ytop)
	{	{
	if (edge1.ytop > edge2.ytop)	if (edge1.ytop > edge2.ytop)
	{	{
	ip.X = edge1.xtop;	ip.X = edge1.xtop;
	ip.Y = edge1.ytop;	ip.Y = edge1.ytop;
	return TopX(edge2, edge1.ytop) < edge1.xtop;	return TopX(edge2, edge1.ytop) < edge1.xtop;
	} else	} else

	skipping to change at line 643	skipping to change at line 649
	ip.X = edge2.xtop;	ip.X = edge2.xtop;
	ip.Y = edge2.ytop;	ip.Y = edge2.ytop;
	return TopX(edge1, edge2.ytop) > edge2.xtop;	return TopX(edge1, edge2.ytop) > edge2.xtop;
	}	}
	}	}
	else	else
	return true;	return true;
	}	}
	//------------------------------------------------------------------------- -----	//------------------------------------------------------------------------- -----


	void ReversePolyPtLinks(OutPt &pp)	void ReversePolyPtLinks(OutPt *pp)
	{	{

		if (!pp) return;
	OutPt pp1, pp2;	OutPt pp1, pp2;

	pp1 = &pp;	pp1 = pp;
	do {	do {
	pp2 = pp1->next;	pp2 = pp1->next;
	pp1->next = pp1->prev;	pp1->next = pp1->prev;
	pp1->prev = pp2;	pp1->prev = pp2;
	pp1 = pp2;	pp1 = pp2;

	} while( pp1 != &pp );	} while( pp1 != pp );
	}	}
	//------------------------------------------------------------------------- -----	//------------------------------------------------------------------------- -----

	void DisposeOutPts(OutPt*& pp)	void DisposeOutPts(OutPt*& pp)
	{	{
	if (pp == 0) return;	if (pp == 0) return;
	pp->prev->next = 0;	pp->prev->next = 0;
	while( pp )	while( pp )
	{	{
	OutPt *tmpPp = pp;	OutPt *tmpPp = pp;

	skipping to change at line 868	skipping to change at line 875
	ClipperBase::~ClipperBase() //destructor	ClipperBase::~ClipperBase() //destructor
	{	{
	Clear();	Clear();
	}	}
	//------------------------------------------------------------------------- -----	//------------------------------------------------------------------------- -----

	bool ClipperBase::AddPolygon( const Polygon &pg, PolyType polyType)	bool ClipperBase::AddPolygon( const Polygon &pg, PolyType polyType)
	{	{
	int len = (int)pg.size();	int len = (int)pg.size();
	if (len < 3) return false;	if (len < 3) return false;


	Polygon p(len);	Polygon p(len);
	p[0] = pg[0];	p[0] = pg[0];
	int j = 0;	int j = 0;

	long64 maxVal;	long64 maxVal;
	if (m_UseFullRange) maxVal = hiRange; else maxVal = loRange;	if (m_UseFullRange) maxVal = hiRange; else maxVal = loRange;

	for (int i = 0; i < len; ++i)	for (int i = 0; i < len; ++i)
	{	{
	if (Abs(pg[i].X) > maxVal \|\| Abs(pg[i].Y) > maxVal)	if (Abs(pg[i].X) > maxVal \|\| Abs(pg[i].Y) > maxVal)

	skipping to change at line 1327	skipping to change at line 1335
	FixupOutPolygon(*outRec);	FixupOutPolygon(*outRec);
	if (!outRec->pts) continue;	if (!outRec->pts) continue;
	if (outRec->isHole && fixHoleLinkages) FixHoleLinkage(outRec);	if (outRec->isHole && fixHoleLinkages) FixHoleLinkage(outRec);

	if (outRec->bottomPt == outRec->bottomFlag &&	if (outRec->bottomPt == outRec->bottomFlag &&
	(Orientation(outRec, m_UseFullRange) != (Area(*outRec, m_UseFullRan ge) > 0)))	(Orientation(outRec, m_UseFullRange) != (Area(*outRec, m_UseFullRan ge) > 0)))
	DisposeBottomPt(*outRec);	DisposeBottomPt(*outRec);

	if (outRec->isHole ==	if (outRec->isHole ==
	(m_ReverseOutput ^ Orientation(outRec, m_UseFullRange)))	(m_ReverseOutput ^ Orientation(outRec, m_UseFullRange)))

	ReversePolyPtLinks(*outRec->pts);	ReversePolyPtLinks(outRec->pts);
	}	}

	JoinCommonEdges(fixHoleLinkages);	JoinCommonEdges(fixHoleLinkages);
	if (fixHoleLinkages)	if (fixHoleLinkages)
	std::sort(m_PolyOuts.begin(), m_PolyOuts.end(), PolySort);	std::sort(m_PolyOuts.begin(), m_PolyOuts.end(), PolySort);
	}	}

	ClearJoins();	ClearJoins();
	ClearHorzJoins();	ClearHorzJoins();
	return succeeded;	return succeeded;

	skipping to change at line 1676	skipping to change at line 1684
	//------------------------------------------------------------------------- -----	//------------------------------------------------------------------------- -----

	void Clipper::ClearHorzJoins()	void Clipper::ClearHorzJoins()
	{	{
	for (HorzJoinList::size_type i = 0; i < m_HorizJoins.size(); i++)	for (HorzJoinList::size_type i = 0; i < m_HorizJoins.size(); i++)
	delete m_HorizJoins[i];	delete m_HorizJoins[i];
	m_HorizJoins.resize(0);	m_HorizJoins.resize(0);
	}	}
	//------------------------------------------------------------------------- -----	//------------------------------------------------------------------------- -----


	void Clipper::InsertLocalMinimaIntoAEL( const long64 botY)	void Clipper::InsertLocalMinimaIntoAEL(const long64 botY)
	{	{
	while( m_CurrentLM && ( m_CurrentLM->Y == botY ) )	while( m_CurrentLM && ( m_CurrentLM->Y == botY ) )
	{	{
	TEdge* lb = m_CurrentLM->leftBound;	TEdge* lb = m_CurrentLM->leftBound;
	TEdge* rb = m_CurrentLM->rightBound;	TEdge* rb = m_CurrentLM->rightBound;

	InsertEdgeIntoAEL( lb );	InsertEdgeIntoAEL( lb );
	InsertScanbeam( lb->ytop );	InsertScanbeam( lb->ytop );
	InsertEdgeIntoAEL( rb );	InsertEdgeIntoAEL( rb );


	skipping to change at line 1780	skipping to change at line 1788
	if( !SelPrev && !SelNext && (e != m_SortedEdges) ) return; //already del eted	if( !SelPrev && !SelNext && (e != m_SortedEdges) ) return; //already del eted
	if( SelPrev ) SelPrev->nextInSEL = SelNext;	if( SelPrev ) SelPrev->nextInSEL = SelNext;
	else m_SortedEdges = SelNext;	else m_SortedEdges = SelNext;
	if( SelNext ) SelNext->prevInSEL = SelPrev;	if( SelNext ) SelNext->prevInSEL = SelPrev;
	e->nextInSEL = 0;	e->nextInSEL = 0;
	e->prevInSEL = 0;	e->prevInSEL = 0;
	}	}
	//------------------------------------------------------------------------- -----	//------------------------------------------------------------------------- -----

	void Clipper::IntersectEdges(TEdge e1, TEdge e2,	void Clipper::IntersectEdges(TEdge e1, TEdge e2,

	const IntPoint &pt, IntersectProtects protects)	const IntPoint &pt, const IntersectProtects protects)
	{	{
	//e1 will be to the left of e2 BELOW the intersection. Therefore e1 is be fore	//e1 will be to the left of e2 BELOW the intersection. Therefore e1 is be fore
	//e2 in AEL except when e1 is being inserted at the intersection point .. .	//e2 in AEL except when e1 is being inserted at the intersection point .. .
	bool e1stops = !(ipLeft & protects) && !e1->nextInLML &&	bool e1stops = !(ipLeft & protects) && !e1->nextInLML &&
	e1->xtop == pt.X && e1->ytop == pt.Y;	e1->xtop == pt.X && e1->ytop == pt.Y;
	bool e2stops = !(ipRight & protects) && !e2->nextInLML &&	bool e2stops = !(ipRight & protects) && !e2->nextInLML &&
	e2->xtop == pt.X && e2->ytop == pt.Y;	e2->xtop == pt.X && e2->ytop == pt.Y;
	bool e1Contributing = ( e1->outIdx >= 0 );	bool e1Contributing = ( e1->outIdx >= 0 );
	bool e2contributing = ( e2->outIdx >= 0 );	bool e2contributing = ( e2->outIdx >= 0 );


	skipping to change at line 1996	skipping to change at line 2004
	OutPt* p2_lft = outRec2->pts;	OutPt* p2_lft = outRec2->pts;
	OutPt* p2_rt = p2_lft->prev;	OutPt* p2_rt = p2_lft->prev;

	EdgeSide side;	EdgeSide side;
	//join e2 poly onto e1 poly and delete pointers to e2 ...	//join e2 poly onto e1 poly and delete pointers to e2 ...
	if( e1->side == esLeft )	if( e1->side == esLeft )
	{	{
	if( e2->side == esLeft )	if( e2->side == esLeft )
	{	{
	//z y x a b c	//z y x a b c

	ReversePolyPtLinks(*p2_lft);	ReversePolyPtLinks(p2_lft);
	p2_lft->next = p1_lft;	p2_lft->next = p1_lft;
	p1_lft->prev = p2_lft;	p1_lft->prev = p2_lft;
	p1_rt->next = p2_rt;	p1_rt->next = p2_rt;
	p2_rt->prev = p1_rt;	p2_rt->prev = p1_rt;
	outRec1->pts = p2_rt;	outRec1->pts = p2_rt;
	} else	} else
	{	{
	//x y z a b c	//x y z a b c
	p2_rt->next = p1_lft;	p2_rt->next = p1_lft;
	p1_lft->prev = p2_rt;	p1_lft->prev = p2_rt;
	p2_lft->prev = p1_rt;	p2_lft->prev = p1_rt;
	p1_rt->next = p2_lft;	p1_rt->next = p2_lft;
	outRec1->pts = p2_lft;	outRec1->pts = p2_lft;
	}	}
	side = esLeft;	side = esLeft;
	} else	} else
	{	{
	if( e2->side == esRight )	if( e2->side == esRight )
	{	{
	//a b c z y x	//a b c z y x

	ReversePolyPtLinks( *p2_lft );	ReversePolyPtLinks(p2_lft);
	p1_rt->next = p2_rt;	p1_rt->next = p2_rt;
	p2_rt->prev = p1_rt;	p2_rt->prev = p1_rt;
	p2_lft->next = p1_lft;	p2_lft->next = p1_lft;
	p1_lft->prev = p2_lft;	p1_lft->prev = p2_lft;
	} else	} else
	{	{
	//a b c x y z	//a b c x y z
	p1_rt->next = p2_lft;	p1_rt->next = p2_lft;
	p2_lft->prev = p1_rt;	p2_lft->prev = p1_rt;
	p1_lft->prev = p2_rt;	p1_lft->prev = p2_rt;

	skipping to change at line 2545	skipping to change at line 2553
	else	else
	e = eNext;	e = eNext;
	}	}
	if( e->prevInSEL ) e->prevInSEL->nextInSEL = 0;	if( e->prevInSEL ) e->prevInSEL->nextInSEL = 0;
	else break;	else break;
	}	}
	m_SortedEdges = 0;	m_SortedEdges = 0;
	}	}
	//------------------------------------------------------------------------- -----	//------------------------------------------------------------------------- -----


	bool ProcessParam1BeforeParam2(IntersectNode &node1, IntersectNode &node2)	bool ProcessParam1BeforeParam2(const IntersectNode &node1, const IntersectN ode &node2)
	{	{
	bool result;	bool result;
	if (node1.pt.Y == node2.pt.Y)	if (node1.pt.Y == node2.pt.Y)
	{	{
	if (node1.edge1 == node2.edge1 \|\| node1.edge2 == node2.edge1)	if (node1.edge1 == node2.edge1 \|\| node1.edge2 == node2.edge1)
	{	{
	result = node2.pt.X > node1.pt.X;	result = node2.pt.X > node1.pt.X;
	return node2.edge1->dx > 0 ? !result : result;	return node2.edge1->dx > 0 ? !result : result;
	}	}
	else if (node1.edge1 == node2.edge2 \|\| node1.edge2 == node2.edge2)	else if (node1.edge1 == node2.edge2 \|\| node1.edge2 == node2.edge2)

	skipping to change at line 2937	skipping to change at line 2945

	void Clipper::DoBothEdges(TEdge edge1, TEdge edge2, const IntPoint &pt)	void Clipper::DoBothEdges(TEdge edge1, TEdge edge2, const IntPoint &pt)
	{	{
	AddOutPt(edge1, pt);	AddOutPt(edge1, pt);
	AddOutPt(edge2, pt);	AddOutPt(edge2, pt);
	SwapSides( edge1 , edge2 );	SwapSides( edge1 , edge2 );
	SwapPolyIndexes( edge1 , edge2 );	SwapPolyIndexes( edge1 , edge2 );
	}	}
	//----------------------------------------------------------------------	//----------------------------------------------------------------------


	void Clipper::JoinCommonEdges(bool fixHoleLinkages)	bool Clipper::JoinPoints(const JoinRec j, OutPt &p1, OutPt *&p2)
	{	{

	for (JoinList::size_type i = 0; i < m_Joins.size(); i++)
	{
	JoinRec* j = m_Joins[i];
	OutRec *outRec1 = m_PolyOuts[j->poly1Idx];	OutRec *outRec1 = m_PolyOuts[j->poly1Idx];

	OutPt *pp1a = outRec1->pts;
	OutRec *outRec2 = m_PolyOuts[j->poly2Idx];	OutRec *outRec2 = m_PolyOuts[j->poly2Idx];

		if (!outRec1 \|\| !outRec2) return false;
		OutPt *pp1a = outRec1->pts;
	OutPt *pp2a = outRec2->pts;	OutPt *pp2a = outRec2->pts;
	IntPoint pt1 = j->pt2a, pt2 = j->pt2b;	IntPoint pt1 = j->pt2a, pt2 = j->pt2b;
	IntPoint pt3 = j->pt1a, pt4 = j->pt1b;	IntPoint pt3 = j->pt1a, pt4 = j->pt1b;

	if (!FindSegment(pp1a, pt1, pt2)) continue;	if (!FindSegment(pp1a, pt1, pt2)) return false;
	if (j->poly1Idx == j->poly2Idx)	if (outRec1 == outRec2)
	{	{
	//we're searching the same polygon for overlapping segments so	//we're searching the same polygon for overlapping segments so
	//segment 2 mustn't be the same as segment 1 ...	//segment 2 mustn't be the same as segment 1 ...
	pp2a = pp1a->next;	pp2a = pp1a->next;

	if (!FindSegment(pp2a, pt3, pt4) \|\| (pp2a == pp1a)) continue;	if (!FindSegment(pp2a, pt3, pt4) \|\| (pp2a == pp1a)) return false;
	}	}

	else if (!FindSegment(pp2a, pt3, pt4)) continue;	else if (!FindSegment(pp2a, pt3, pt4)) return false;


	if (!GetOverlapSegment(pt1, pt2, pt3, pt4, pt1, pt2)) continue;	if (!GetOverlapSegment(pt1, pt2, pt3, pt4, pt1, pt2)) return false;


	OutPt p1, p2, p3, p4;	OutPt p3, p4, *prev = pp1a->prev;
	OutPt *prev = pp1a->prev;
	//get p1 & p2 polypts - the overlap start & endpoints on poly1	//get p1 & p2 polypts - the overlap start & endpoints on poly1
	if (PointsEqual(pp1a->pt, pt1)) p1 = pp1a;	if (PointsEqual(pp1a->pt, pt1)) p1 = pp1a;
	else if (PointsEqual(prev->pt, pt1)) p1 = prev;	else if (PointsEqual(prev->pt, pt1)) p1 = prev;
	else p1 = InsertPolyPtBetween(pp1a, prev, pt1);	else p1 = InsertPolyPtBetween(pp1a, prev, pt1);

	if (PointsEqual(pp1a->pt, pt2)) p2 = pp1a;	if (PointsEqual(pp1a->pt, pt2)) p2 = pp1a;
	else if (PointsEqual(prev->pt, pt2)) p2 = prev;	else if (PointsEqual(prev->pt, pt2)) p2 = prev;
	else if ((p1 == pp1a) \|\| (p1 == prev))	else if ((p1 == pp1a) \|\| (p1 == prev))
	p2 = InsertPolyPtBetween(pp1a, prev, pt2);	p2 = InsertPolyPtBetween(pp1a, prev, pt2);
	else if (Pt3IsBetweenPt1AndPt2(pp1a->pt, p1->pt, pt2))	else if (Pt3IsBetweenPt1AndPt2(pp1a->pt, p1->pt, pt2))

	skipping to change at line 2996	skipping to change at line 3001
	p4 = InsertPolyPtBetween(pp2a, p3, pt2); else	p4 = InsertPolyPtBetween(pp2a, p3, pt2); else
	p4 = InsertPolyPtBetween(p3, prev, pt2);	p4 = InsertPolyPtBetween(p3, prev, pt2);

	//p1.pt == p3.pt and p2.pt == p4.pt so join p1 to p3 and p2 to p4 ...	//p1.pt == p3.pt and p2.pt == p4.pt so join p1 to p3 and p2 to p4 ...
	if (p1->next == p2 && p3->prev == p4)	if (p1->next == p2 && p3->prev == p4)
	{	{
	p1->next = p3;	p1->next = p3;
	p3->prev = p1;	p3->prev = p1;
	p2->prev = p4;	p2->prev = p4;
	p4->next = p2;	p4->next = p2;

		return true;
	}	}
	else if (p1->prev == p2 && p3->next == p4)	else if (p1->prev == p2 && p3->next == p4)
	{	{
	p1->prev = p3;	p1->prev = p3;
	p3->next = p1;	p3->next = p1;
	p2->next = p4;	p2->next = p4;
	p4->prev = p2;	p4->prev = p2;

		return true;
	}	}
	else	else

	continue; //an orientation is probably wrong	return false; //an orientation is probably wrong
		}
		//----------------------------------------------------------------------


	if (j->poly2Idx == j->poly1Idx)	void Clipper::FixupJoinRecs(JoinRec j, OutPt pt, unsigned startIdx)
		{
		for (JoinList::size_type k = startIdx; k < m_Joins.size(); k++)
		{
		JoinRec* j2 = m_Joins[k];
		if (j2->poly1Idx == j->poly1Idx && PointIsVertex(j2->pt1a, pt))
		j2->poly1Idx = j->poly2Idx;
		if (j2->poly2Idx == j->poly1Idx && PointIsVertex(j2->pt2a, pt))
		j2->poly2Idx = j->poly2Idx;
		}
		}
		//----------------------------------------------------------------------

		void Clipper::JoinCommonEdges(bool fixHoleLinkages)
		{
		for (JoinList::size_type i = 0; i < m_Joins.size(); i++)
		{
		JoinRec* j = m_Joins[i];
		OutPt p1, p2;
		if (!JoinPoints(j, p1, p2)) return;

		OutRec *outRec1 = m_PolyOuts[j->poly1Idx];
		OutRec *outRec2 = m_PolyOuts[j->poly2Idx];

		if (outRec1 == outRec2)
	{	{
	//instead of joining two polygons, we've just created a new one by	//instead of joining two polygons, we've just created a new one by
	//splitting one polygon into two.	//splitting one polygon into two.
	outRec1->pts = GetBottomPt(p1);	outRec1->pts = GetBottomPt(p1);
	outRec1->bottomPt = outRec1->pts;	outRec1->bottomPt = outRec1->pts;
	outRec1->bottomPt->idx = outRec1->idx;	outRec1->bottomPt->idx = outRec1->idx;
	outRec2 = CreateOutRec();	outRec2 = CreateOutRec();
	m_PolyOuts.push_back(outRec2);	m_PolyOuts.push_back(outRec2);
	outRec2->idx = (int)m_PolyOuts.size()-1;	outRec2->idx = (int)m_PolyOuts.size()-1;
	j->poly2Idx = outRec2->idx;	j->poly2Idx = outRec2->idx;
	outRec2->pts = GetBottomPt(p2);	outRec2->pts = GetBottomPt(p2);
	outRec2->bottomPt = outRec2->pts;	outRec2->bottomPt = outRec2->pts;
	outRec2->bottomPt->idx = outRec2->idx;	outRec2->bottomPt->idx = outRec2->idx;


	int K = 0;
	if (PointInPolygon(outRec2->pts->pt, outRec1->pts, m_UseFullRange))	if (PointInPolygon(outRec2->pts->pt, outRec1->pts, m_UseFullRange))
	{	{
	//outRec2 is contained by outRec1 ...	//outRec2 is contained by outRec1 ...

	K = 1;
	outRec2->isHole = !outRec1->isHole;	outRec2->isHole = !outRec1->isHole;
	outRec2->FirstLeft = outRec1;	outRec2->FirstLeft = outRec1;


		FixupJoinRecs(j, p2, i+1);
		FixupOutPolygon(*outRec1); //nb: do this BEFORE testing orientation
		FixupOutPolygon(*outRec2); // but AFTER calling FixupJoinRecs()

		if (outRec2->pts && outRec2->isHole ==
		(m_ReverseOutput ^ Orientation(outRec2, m_UseFullRange)))
		ReversePolyPtLinks(outRec2->pts);

	} else if (PointInPolygon(outRec1->pts->pt, outRec2->pts, m_UseFullRa nge))	} else if (PointInPolygon(outRec1->pts->pt, outRec2->pts, m_UseFullRa nge))
	{	{
	//outRec1 is contained by outRec2 ...	//outRec1 is contained by outRec2 ...

	K = 2;
	outRec2->isHole = outRec1->isHole;	outRec2->isHole = outRec1->isHole;
	outRec1->isHole = !outRec2->isHole;	outRec1->isHole = !outRec2->isHole;
	outRec2->FirstLeft = outRec1->FirstLeft;	outRec2->FirstLeft = outRec1->FirstLeft;
	outRec1->FirstLeft = outRec2;	outRec1->FirstLeft = outRec2;

	} else
		FixupJoinRecs(j, p2, i+1);
		FixupOutPolygon(*outRec1); //nb: do this BEFORE testing orientation
		FixupOutPolygon(*outRec2); // but AFTER calling FixupJoinRecs()

		if (outRec1->isHole ==
		(m_ReverseOutput ^ Orientation(outRec1, m_UseFullRange)))
		ReversePolyPtLinks(outRec1->pts);
		//make sure any contained holes now link to the correct polygon ...
		if (fixHoleLinkages && outRec1->isHole)
		for (PolyOutList::size_type k = 0; k < m_PolyOuts.size(); ++k)
		{
		OutRec *orec = m_PolyOuts[k];
		if (orec->isHole && orec->bottomPt && orec->FirstLeft == outRec
		1)
		orec->FirstLeft = outRec2;
		}
		}
		else
	{	{

		//the 2 polygons are completely separate ...
	outRec2->isHole = outRec1->isHole;	outRec2->isHole = outRec1->isHole;
	outRec2->FirstLeft = outRec1->FirstLeft;	outRec2->FirstLeft = outRec1->FirstLeft;

	}

	//now fixup any subsequent joins that match this polygon
	for (JoinList::size_type k = i+1; k < m_Joins.size(); k++)
	{
	JoinRec* j2 = m_Joins[k];
	if (j2->poly1Idx == j->poly1Idx && PointIsVertex(j2->pt1a, p2))
	j2->poly1Idx = j->poly2Idx;
	if (j2->poly2Idx == j->poly1Idx && PointIsVertex(j2->pt2a, p2))
	j2->poly2Idx = j->poly2Idx;
	}


	FixupOutPolygon(*outRec1); //nb: do this BEFORE testing orientation	FixupJoinRecs(j, p2, i+1);
	FixupOutPolygon(*outRec2); // but AFTER calling PointIsVertex()	FixupOutPolygon(*outRec1); //nb: do this BEFORE testing orientation
		FixupOutPolygon(*outRec2); // but AFTER calling FixupJoinRecs()


	switch( K ) {	if (fixHoleLinkages && outRec2->pts)
	case 1:	for (PolyOutList::size_type k = 0; k < m_PolyOuts.size(); ++k)
	{	{

	if (outRec2->pts && outRec2->isHole ==	OutRec *orec = m_PolyOuts[k];
	(m_ReverseOutput ^ Orientation(outRec2, m_UseFullRange)))	if (orec->isHole && orec->bottomPt && orec->FirstLeft == outRec
	ReversePolyPtLinks(*outRec2->pts);	1 &&
	break;	PointInPolygon(orec->bottomPt->pt, outRec2->pts, m_UseFullRan
	}	ge))
	case 2:	orec->FirstLeft = outRec2;
	{
	if (outRec1->pts)
	{
	if (outRec1->isHole ==
	(m_ReverseOutput ^ Orientation(outRec1, m_UseFullRange)))
	ReversePolyPtLinks(*outRec1->pts);
	//make sure any contained holes now link to the correct polyg
	on ...
	if (fixHoleLinkages && outRec1->isHole)
	for (PolyOutList::size_type k = 0; k < m_PolyOuts.size(); +
	+k)
	{
	OutRec *orec = m_PolyOuts[k];
	if (orec->isHole && orec->bottomPt && orec->FirstLeft ==
	outRec1)
	orec->FirstLeft = outRec2;
	}
	}
	break;
	}
	default:
	{
	//make sure any contained holes now link to the correct polygon
	...
	if (fixHoleLinkages)
	for (PolyOutList::size_type k = 0; k < m_PolyOuts.size(); ++k
	)
	{
	OutRec *orec = m_PolyOuts[k];
	if (orec->isHole && orec->bottomPt && orec->FirstLeft == ou
	tRec1 &&
	!PointInPolygon(orec->bottomPt->pt, outRec1->pts, m_UseFu
	llRange))
	orec->FirstLeft = outRec2;
	}

	}	}
	}	}


	if (outRec1->pts && Orientation(outRec1, m_UseFullRange) != (Area(*ou tRec1, m_UseFullRange) > 0))	if (Orientation(outRec1, m_UseFullRange) != (Area(*outRec1, m_UseFull Range) >= 0))
	DisposeBottomPt(*outRec1);	DisposeBottomPt(*outRec1);

	if (outRec2->pts && Orientation(outRec2, m_UseFullRange) != (Area(*ou tRec2, m_UseFullRange) > 0))	if (Orientation(outRec2, m_UseFullRange) != (Area(*outRec2, m_UseFull Range) >= 0))
	DisposeBottomPt(*outRec2);	DisposeBottomPt(*outRec2);

	} else	} else
	{	{
	//joined 2 polygons together ...	//joined 2 polygons together ...

	//make sure any holes contained by outRec2 now link to outRec1 ...	//make sure any holes contained by outRec2 now link to outRec1 ...
	if (fixHoleLinkages)	if (fixHoleLinkages)
	for (PolyOutList::size_type k = 0; k < m_PolyOuts.size(); ++k)	for (PolyOutList::size_type k = 0; k < m_PolyOuts.size(); ++k)
	if (m_PolyOuts[k]->isHole && m_PolyOuts[k]->bottomPt &&	if (m_PolyOuts[k]->isHole && m_PolyOuts[k]->bottomPt &&

	skipping to change at line 3185	skipping to change at line 3201
	for (int i = 0; i < n; ++i)	for (int i = 0; i < n; ++i)
	{	{
	result[i].X = pt.X + Round(std::cos(a)*r);	result[i].X = pt.X + Round(std::cos(a)*r);
	result[i].Y = pt.Y + Round(std::sin(a)*r);	result[i].Y = pt.Y + Round(std::sin(a)*r);
	a += da;	a += da;
	}	}
	return result;	return result;
	}	}
	//------------------------------------------------------------------------- -----	//------------------------------------------------------------------------- -----


	DoublePoint GetUnitNormal( const IntPoint &pt1, const IntPoint &pt2)	DoublePoint GetUnitNormal(const IntPoint &pt1, const IntPoint &pt2)
	{	{
	if(pt2.X == pt1.X && pt2.Y == pt1.Y)	if(pt2.X == pt1.X && pt2.Y == pt1.Y)
	return DoublePoint(0, 0);	return DoublePoint(0, 0);

	double dx = (double)(pt2.X - pt1.X);	double dx = (double)(pt2.X - pt1.X);
	double dy = (double)(pt2.Y - pt1.Y);	double dy = (double)(pt2.Y - pt1.Y);
	double f = 1 1.0/ std::sqrt( dxdx + dy*dy );	double f = 1 1.0/ std::sqrt( dxdx + dy*dy );
	dx *= f;	dx *= f;
	dy *= f;	dy *= f;
	return DoublePoint(dy, -dx);	return DoublePoint(dy, -dx);

	skipping to change at line 3215	skipping to change at line 3231
	Polygon* m_curr_poly;	Polygon* m_curr_poly;
	std::vector<DoublePoint> normals;	std::vector<DoublePoint> normals;
	double m_delta, m_RMin, m_R;	double m_delta, m_RMin, m_R;
	size_t m_i, m_j, m_k;	size_t m_i, m_j, m_k;
	static const int buffLength = 128;	static const int buffLength = 128;
	JoinType m_jointype;	JoinType m_jointype;

	public:	public:

	PolyOffsetBuilder(const Polygons& in_polys, Polygons& out_polys,	PolyOffsetBuilder(const Polygons& in_polys, Polygons& out_polys,

	double delta, JoinType jointype, double MiterLimit)	double delta, JoinType jointype, double MiterLimit, bool CheckInputs)
	{	{
	//nb precondition - out_polys != ptsin_polys	//nb precondition - out_polys != ptsin_polys
	if (NEAR_ZERO(delta))	if (NEAR_ZERO(delta))
	{	{
	out_polys = in_polys;	out_polys = in_polys;
	return;	return;
	}	}

	this->m_p = in_polys;	this->m_p = in_polys;
	this->m_delta = delta;	this->m_delta = delta;
	this->m_jointype = jointype;	this->m_jointype = jointype;


		//ChecksInput - fixes polygon orientation if necessary and removes
		//duplicate vertices. Can be set false when you're sure that polygon
		//orientation is correct and that there are no duplicate vertices.
		if (CheckInputs)
		{
		size_t Len = m_p.size(), botI = 0;
		while (botI < Len && m_p[botI].size() == 0) botI++;
		if (botI == Len) return;

		//botPt: used to find the lowermost (in inverted Y-axis) & leftmost p
		oint
		//This point (on m_p[botI]) must be on an outer polygon ring and if
		//its orientation is false (counterclockwise) then assume all polygon
		s
		//need reversing ...
		IntPoint botPt = m_p[botI][0];
		for (size_t i = botI; i < Len; ++i)
		{
		if (m_p[i].size() < 3) continue;
		if (UpdateBotPt(m_p[i][0], botPt)) botI = i;
		Polygon::iterator it = m_p[i].begin() +1;
		while (it != m_p[i].end())
		{
		if (PointsEqual(it, (it -1)))
		it = m_p[i].erase(it);
		else
		{
		if (UpdateBotPt(*it, botPt)) botI = i;
		++it;
		}
		}
		}
		if (!Orientation(m_p[botI]))
		ReversePolygons(m_p);
		}

	if (MiterLimit <= 1) MiterLimit = 1;	if (MiterLimit <= 1) MiterLimit = 1;
	m_RMin = 2/(MiterLimit*MiterLimit);	m_RMin = 2/(MiterLimit*MiterLimit);

	double deltaSq = delta*delta;	double deltaSq = delta*delta;
	out_polys.clear();	out_polys.clear();

	out_polys.resize(in_polys.size());	out_polys.resize(m_p.size());
	for (m_i = 0; m_i < in_polys.size(); m_i++)	for (m_i = 0; m_i < m_p.size(); m_i++)
	{	{
	m_curr_poly = &out_polys[m_i];	m_curr_poly = &out_polys[m_i];

	size_t len = in_polys[m_i].size();	size_t len = m_p[m_i].size();
	if (len > 1 && m_p[m_i][0].X == m_p[m_i][len - 1].X &&	if (len > 1 && m_p[m_i][0].X == m_p[m_i][len - 1].X &&
	m_p[m_i][0].Y == m_p[m_i][len-1].Y) len--;	m_p[m_i][0].Y == m_p[m_i][len-1].Y) len--;

	//when 'shrinking' polygons - to minimize artefacts	//when 'shrinking' polygons - to minimize artefacts
	//strip those polygons that have an area < pi * delta^2 ...	//strip those polygons that have an area < pi * delta^2 ...

	double a1 = Area(in_polys[m_i]);	double a1 = Area(m_p[m_i]);
	if (delta < 0) { if (a1 > 0 && a1 < deltaSq *pi) len = 0; }	if (delta < 0) { if (a1 > 0 && a1 < deltaSq *pi) len = 0; }
	else if (a1 < 0 && -a1 < deltaSq *pi) len = 0; //holes have neg. ar ea	else if (a1 < 0 && -a1 < deltaSq *pi) len = 0; //holes have neg. ar ea

	if (len == 0 \|\| (len < 3 && delta <= 0))	if (len == 0 \|\| (len < 3 && delta <= 0))
	continue;	continue;
	else if (len == 1)	else if (len == 1)
	{	{
	Polygon arc;	Polygon arc;

	arc = BuildArc(in_polys[m_i][len-1], 0, 2 * pi, delta);	arc = BuildArc(m_p[m_i][len-1], 0, 2 * pi, delta);
	out_polys[m_i] = arc;	out_polys[m_i] = arc;
	continue;	continue;
	}	}

	//build normals ...	//build normals ...
	normals.clear();	normals.clear();
	normals.resize(len);	normals.resize(len);

	normals[len-1] = GetUnitNormal(in_polys[m_i][len-1], in_polys[m_i][ 0]);	normals[len-1] = GetUnitNormal(m_p[m_i][len-1], m_p[m_i][0]);
	for (m_j = 0; m_j < len -1; ++m_j)	for (m_j = 0; m_j < len -1; ++m_j)

	normals[m_j] = GetUnitNormal(in_polys[m_i][m_j], in_polys[m_i][ m_j+1]);	normals[m_j] = GetUnitNormal(m_p[m_i][m_j], m_p[m_i][m_j+1]);

	m_k = len -1;	m_k = len -1;
	for (m_j = 0; m_j < len; ++m_j)	for (m_j = 0; m_j < len; ++m_j)
	{	{
	switch (jointype)	switch (jointype)
	{	{
	case jtMiter:	case jtMiter:
	{	{
	m_R = 1 + (normals[m_j].X*normals[m_k].X +	m_R = 1 + (normals[m_j].X*normals[m_k].X +
	normals[m_j].Y*normals[m_k].Y);	normals[m_j].Y*normals[m_k].Y);

	skipping to change at line 3400	skipping to change at line 3451
	for (Polygon::size_type m = 0; m < arc.size(); m++)	for (Polygon::size_type m = 0; m < arc.size(); m++)
	AddPoint(arc[m]);	AddPoint(arc[m]);
	}	}
	}	}
	else	else
	AddPoint(m_p[m_i][m_j]);	AddPoint(m_p[m_i][m_j]);
	AddPoint(pt2);	AddPoint(pt2);
	}	}
	//------------------------------------------------------------------------- -	//------------------------------------------------------------------------- -


		bool UpdateBotPt(const IntPoint &pt, IntPoint &botPt)
		{
		if (pt.Y > botPt.Y \|\| (pt.Y == botPt.Y && pt.X < botPt.X))
		{
		botPt = pt;
		return true;
		}
		else return false;
		}
		//-------------------------------------------------------------------------
		-

	}; //end PolyOffsetBuilder	}; //end PolyOffsetBuilder

	//------------------------------------------------------------------------- -----	//------------------------------------------------------------------------- -----
	//------------------------------------------------------------------------- -----	//------------------------------------------------------------------------- -----

	void OffsetPolygons(const Polygons &in_polys, Polygons &out_polys,	void OffsetPolygons(const Polygons &in_polys, Polygons &out_polys,

	double delta, JoinType jointype, double MiterLimit)	double delta, JoinType jointype, double MiterLimit, bool CheckInputs)
	{	{
	if (&out_polys == &in_polys)	if (&out_polys == &in_polys)
	{	{
	Polygons poly2(in_polys);	Polygons poly2(in_polys);

	PolyOffsetBuilder(poly2, out_polys, delta, jointype, MiterLimit);	PolyOffsetBuilder(poly2, out_polys, delta, jointype, MiterLimit, CheckI nputs);
	}	}

	else PolyOffsetBuilder(in_polys, out_polys, delta, jointype, MiterLimit);	else PolyOffsetBuilder(in_polys, out_polys, delta, jointype, MiterLimit, CheckInputs);
	}	}
	//------------------------------------------------------------------------- -----	//------------------------------------------------------------------------- -----

	void SimplifyPolygon(const Polygon &in_poly, Polygons &out_polys, PolyFillT ype fillType)	void SimplifyPolygon(const Polygon &in_poly, Polygons &out_polys, PolyFillT ype fillType)
	{	{
	Clipper c;	Clipper c;
	c.AddPolygon(in_poly, ptSubject);	c.AddPolygon(in_poly, ptSubject);
	c.Execute(ctUnion, out_polys, fillType, fillType);	c.Execute(ctUnion, out_polys, fillType, fillType);
	}	}
	//------------------------------------------------------------------------- -----	//------------------------------------------------------------------------- -----

End of changes. 53 change blocks.
	106 lines changed or deleted	167 lines changed or added
This html diff was produced by rfcdiff 1.41. The latest version is available from http://tools.ietf.org/tools/rfcdiff/