clipper.hpp   clipper.hpp 
/************************************************************************** ***** /************************************************************************** *****
* * * *
* Author : Angus Johnson * * Author : Angus Johnson *
* Version : 5.1.6 * Version : 6.0.0
* *
* Date : 23 May 2013 * Date : 30 October 2013
* *
* Website : http://www.angusj.com * * Website : http://www.angusj.com *
* Copyright : Angus Johnson 2010-2013 * * Copyright : Angus Johnson 2010-2013 *
* * * *
* 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 37 skipping to change at line 37
* ASME 2005 International Design Engineering Technical Conferences * * ASME 2005 International Design Engineering Technical Conferences *
* and Computers and Information in Engineering Conference (IDETC/CIE2005) * * and Computers and Information in Engineering Conference (IDETC/CIE2005) *
* September 24-28, 2005 , Long Beach, California, USA * * September 24-28, 2005 , Long Beach, California, USA *
* http://www.me.berkeley.edu/~mcmains/pubs/DAC05OffsetPolygon.pdf * * http://www.me.berkeley.edu/~mcmains/pubs/DAC05OffsetPolygon.pdf *
* * * *
*************************************************************************** ****/ *************************************************************************** ****/
#ifndef clipper_hpp #ifndef clipper_hpp
#define clipper_hpp #define clipper_hpp
#define CLIPPER_VERSION "6.0.0"
//use_int32: When enabled 32bit ints are used instead of 64bit ints. This
//improve performance but coordinate values are limited to the range +/- 46
340
//#define use_int32
//use_xyz: adds a Z member to IntPoint. Adds a minor cost to perfomance.
//#define use_xyz
//use_lines: Enables line clipping. Adds a very minor cost to performance.
//#define use_lines
//When enabled, code developed with earlier versions of Clipper
//(ie prior to ver 6) should compile without changes.
//In a future update, this compatability code will be removed.
#define use_deprecated
#include <vector> #include <vector>
#include <set>
#include <stdexcept> #include <stdexcept>
#include <cstring> #include <cstring>
#include <cstdlib> #include <cstdlib>
#include <ostream> #include <ostream>
#include <functional>
namespace ClipperLib { namespace ClipperLib {
enum ClipType { ctIntersection, ctUnion, ctDifference, ctXor }; enum ClipType { ctIntersection, ctUnion, ctDifference, ctXor };
enum PolyType { ptSubject, ptClip }; enum PolyType { ptSubject, ptClip };
//By far the most widely used winding rules for polygon filling are //By far the most widely used winding rules for polygon filling are
//EvenOdd & NonZero (GDI, GDI+, XLib, OpenGL, Cairo, AGG, Quartz, SVG, Gr32 ) //EvenOdd & NonZero (GDI, GDI+, XLib, OpenGL, Cairo, AGG, Quartz, SVG, Gr32 )
//Others rules include Positive, Negative and ABS_GTR_EQ_TWO (only in OpenG L) //Others rules include Positive, Negative and ABS_GTR_EQ_TWO (only in OpenG L)
//see http://glprogramming.com/red/chapter11.html //see http://glprogramming.com/red/chapter11.html
enum PolyFillType { pftEvenOdd, pftNonZero, pftPositive, pftNegative }; enum PolyFillType { pftEvenOdd, pftNonZero, pftPositive, pftNegative };
typedef signed long long long64; #ifdef use_int32
typedef unsigned long long ulong64; typedef int cInt;
typedef unsigned int cUInt;
#else
typedef signed long long cInt;
typedef unsigned long long cUInt;
#endif
struct IntPoint { struct IntPoint {
public: cInt X;
long64 X; cInt Y;
long64 Y; #ifdef use_xyz
IntPoint(long64 x = 0, long64 y = 0): X(x), Y(y) {}; cInt Z;
friend std::ostream& operator <<(std::ostream &s, IntPoint &p); IntPoint(cInt x = 0, cInt y = 0, cInt z = 0): X(x), Y(y), Z(z) {};
#else
IntPoint(cInt x = 0, cInt y = 0): X(x), Y(y) {};
#endif
friend inline bool operator== (const IntPoint& a, const IntPoint& b)
{
return a.X == b.X && a.Y == b.Y;
}
friend inline bool operator!= (const IntPoint& a, const IntPoint& b)
{
return a.X != b.X || a.Y != b.Y;
}
}; };
//-------------------------------------------------------------------------
-----
typedef std::vector< IntPoint > Path;
typedef std::vector< Path > Paths;
typedef std::vector< IntPoint > Polygon; inline Path& operator <<(Path& poly, const IntPoint& p) {poly.push_back(p);
typedef std::vector< Polygon > Polygons; return poly;}
inline Paths& operator <<(Paths& polys, const Path& p) {polys.push_back(p);
return polys;}
std::ostream& operator <<(std::ostream &s, const IntPoint &p);
std::ostream& operator <<(std::ostream &s, const Path &p);
std::ostream& operator <<(std::ostream &s, const Paths &p);
#ifdef use_deprecated
typedef signed long long long64; //backward compatibility only
typedef Path Polygon;
typedef Paths Polygons;
#endif
struct DoublePoint
{
double X;
double Y;
DoublePoint(double x = 0, double y = 0) : X(x), Y(y) {}
DoublePoint(IntPoint ip) : X((double)ip.X), Y((double)ip.Y) {}
};
//-------------------------------------------------------------------------
-----
std::ostream& operator <<(std::ostream &s, Polygon &p); #ifdef use_xyz
std::ostream& operator <<(std::ostream &s, Polygons &p); typedef void (*TZFillCallback)(IntPoint& z1, IntPoint& z2, IntPoint& pt);
#endif
class PolyNode; class PolyNode;
typedef std::vector< PolyNode* > PolyNodes; typedef std::vector< PolyNode* > PolyNodes;
class PolyNode class PolyNode
{ {
public: public:
PolyNode(); PolyNode();
Polygon Contour; Path Contour;
PolyNodes Childs; PolyNodes Childs;
PolyNode* Parent; PolyNode* Parent;
PolyNode* GetNext() const; PolyNode* GetNext() const;
bool IsHole() const; bool IsHole() const;
bool IsOpen() const;
int ChildCount() const; int ChildCount() const;
private: private:
bool m_IsOpen;
PolyNode* GetNextSiblingUp() const; PolyNode* GetNextSiblingUp() const;
unsigned Index; //node index in Parent.Childs unsigned Index; //node index in Parent.Childs
void AddChild(PolyNode& child); void AddChild(PolyNode& child);
friend class Clipper; //to access Index friend class Clipper; //to access Index
}; };
class PolyTree: public PolyNode class PolyTree: public PolyNode
{ {
public: public:
~PolyTree(){Clear();}; ~PolyTree(){Clear();};
PolyNode* GetFirst() const; PolyNode* GetFirst() const;
void Clear(); void Clear();
int Total() const; int Total() const;
private: private:
PolyNodes AllNodes; PolyNodes AllNodes;
friend class Clipper; //to access AllNodes friend class Clipper; //to access AllNodes
}; };
enum JoinType { jtSquare, jtRound, jtMiter }; enum InitOptions {ioReverseSolution = 1, ioStrictlySimple = 2, ioPreserveCo
enum EndType { etClosed, etButt, etSquare, etRound}; llinear = 4};
enum JoinType {jtSquare, jtRound, jtMiter};
enum EndType {etClosed, etButt, etSquare, etRound};
bool Orientation(const Path &poly);
double Area(const Path &poly);
#ifdef use_deprecated
void OffsetPolygons(const Polygons &in_polys, Polygons &out_polys,
double delta, JoinType jointype = jtSquare, double limit = 0, bool auto
Fix = true);
void PolyTreeToPolygons(const PolyTree& polytree, Paths& paths);
void ReversePolygon(Path& p);
void ReversePolygons(Paths& p);
#endif
void OffsetPaths(const Paths &in_polys, Paths &out_polys,
double delta, JoinType jointype, EndType endtype, double limit = 0);
void SimplifyPolygon(const Path &in_poly, Paths &out_polys, PolyFillType fi
llType = pftEvenOdd);
void SimplifyPolygons(const Paths &in_polys, Paths &out_polys, PolyFillType
fillType = pftEvenOdd);
void SimplifyPolygons(Paths &polys, PolyFillType fillType = pftEvenOdd);
void CleanPolygon(const Path& in_poly, Path& out_poly, double distance = 1.
415);
void CleanPolygon(Path& poly, double distance = 1.415);
void CleanPolygons(const Paths& in_polys, Paths& out_polys, double distance
= 1.415);
void CleanPolygons(Paths& polys, double distance = 1.415);
void MinkowkiSum(const Path& poly, const Path& path, Paths& solution, bool
isClosed);
void MinkowkiDiff(const Path& poly, const Path& path, Paths& solution, bool
isClosed);
void PolyTreeToPaths(const PolyTree& polytree, Paths& paths);
void ClosedPathsFromPolyTree(const PolyTree& polytree, Paths& paths);
void OpenPathsFromPolyTree(PolyTree& polytree, Paths& paths);
bool Orientation(const Polygon &poly); void ReversePath(Path& p);
double Area(const Polygon &poly); void ReversePaths(Paths& p);
void OffsetPolygons(const Polygons &in_polys, Polygons &out_polys, struct IntRect { cInt left; cInt top; cInt right; cInt bottom; };
double delta, JoinType jointype = jtSquare, double limit = 0, bool autoFi
x = true);
void OffsetPolyLines(const Polygons &in_lines, Polygons &out_lines, //enums that are used internally ...
double delta, JoinType jointype = jtSquare, EndType endtype = etSquare, d
ouble limit = 0, bool autoFix = true);
void SimplifyPolygon(const Polygon &in_poly, Polygons &out_polys, PolyFillT
ype fillType = pftEvenOdd);
void SimplifyPolygons(const Polygons &in_polys, Polygons &out_polys, PolyFi
llType fillType = pftEvenOdd);
void SimplifyPolygons(Polygons &polys, PolyFillType fillType = pftEvenOdd);
void CleanPolygon(const Polygon& in_poly, Polygon& out_poly, double distanc
e = 1.415);
void CleanPolygons(const Polygons& in_polys, Polygons& out_polys, double di
stance = 1.415);
void PolyTreeToPolygons(const PolyTree& polytree, Polygons& polygons);
void ReversePolygon(Polygon& p);
void ReversePolygons(Polygons& p);
//used internally ...
enum EdgeSide { esLeft = 1, esRight = 2}; enum EdgeSide { esLeft = 1, esRight = 2};
enum IntersectProtects { ipNone = 0, ipLeft = 1, ipRight = 2, ipBoth = 3 };
//inline IntersectProtects operator|(IntersectProtects a, IntersectProtects
b)
//{return static_cast<IntersectProtects>(static_cast<int>(a) | static_cast<
int>(b));}
struct TEdge {
long64 xbot;
long64 ybot;
long64 xcurr;
long64 ycurr;
long64 xtop;
long64 ytop;
double dx;
long64 deltaX;
long64 deltaY;
PolyType polyType;
EdgeSide side;
int windDelta; //1 or -1 depending on winding direction
int windCnt;
int windCnt2; //winding count of the opposite polytype
int outIdx;
TEdge *next;
TEdge *prev;
TEdge *nextInLML;
TEdge *nextInAEL;
TEdge *prevInAEL;
TEdge *nextInSEL;
TEdge *prevInSEL;
};
struct IntersectNode {
TEdge *edge1;
TEdge *edge2;
IntPoint pt;
IntersectNode *next;
};
struct LocalMinima {
long64 Y;
TEdge *leftBound;
TEdge *rightBound;
LocalMinima *next;
};
struct Scanbeam {
long64 Y;
Scanbeam *next;
};
struct OutPt; //forward declaration
struct OutRec {
int idx;
bool isHole;
OutRec *FirstLeft; //see comments in clipper.pas
PolyNode *polyNode;
OutPt *pts;
OutPt *bottomPt;
};
struct OutPt { //forward declarations (for stuff used internally) ...
int idx; struct TEdge;
IntPoint pt; struct IntersectNode;
OutPt *next; struct LocalMinima;
OutPt *prev; struct Scanbeam;
}; struct OutPt;
struct OutRec;
struct JoinRec { struct Join;
IntPoint pt1a;
IntPoint pt1b;
int poly1Idx;
IntPoint pt2a;
IntPoint pt2b;
int poly2Idx;
};
struct HorzJoinRec {
TEdge *edge;
int savedIdx;
};
struct IntRect { long64 left; long64 top; long64 right; long64 bottom; };
typedef std::vector < OutRec* > PolyOutList; typedef std::vector < OutRec* > PolyOutList;
typedef std::vector < TEdge* > EdgeList; typedef std::vector < TEdge* > EdgeList;
typedef std::vector < JoinRec* > JoinList; typedef std::vector < Join* > JoinList;
typedef std::vector < HorzJoinRec* > HorzJoinList;
//-------------------------------------------------------------------------
-----
//ClipperBase is the ancestor to the Clipper class. It should not be //ClipperBase is the ancestor to the Clipper class. It should not be
//instantiated directly. This class simply abstracts the conversion of sets of //instantiated directly. This class simply abstracts the conversion of sets of
//polygon coordinates into edge objects that are stored in a LocalMinima li st. //polygon coordinates into edge objects that are stored in a LocalMinima li st.
class ClipperBase class ClipperBase
{ {
public: public:
ClipperBase(); ClipperBase();
virtual ~ClipperBase(); virtual ~ClipperBase();
bool AddPolygon(const Polygon &pg, PolyType polyType); bool AddPath(const Path &pg, PolyType PolyTyp, bool Closed);
bool AddPolygons( const Polygons &ppg, PolyType polyType); bool AddPaths(const Paths &ppg, PolyType PolyTyp, bool Closed);
#ifdef use_deprecated
bool AddPolygon(const Path &pg, PolyType PolyTyp);
bool AddPolygons(const Paths &ppg, PolyType PolyTyp);
#endif
virtual void Clear(); virtual void Clear();
IntRect GetBounds(); IntRect GetBounds();
bool PreserveCollinear() {return m_PreserveCollinear;};
void PreserveCollinear(bool value) {m_PreserveCollinear = value;};
protected: protected:
void DisposeLocalMinimaList(); void DisposeLocalMinimaList();
TEdge* AddBoundsToLML(TEdge *e); TEdge* AddBoundsToLML(TEdge *e, bool IsClosed);
void PopLocalMinima(); void PopLocalMinima();
virtual void Reset(); virtual void Reset();
void InsertLocalMinima(LocalMinima *newLm); void InsertLocalMinima(LocalMinima *newLm);
void DoMinimaLML(TEdge* E1, TEdge* E2, bool IsClosed);
TEdge* DescendToMin(TEdge *&E);
void AscendToMax(TEdge *&E, bool Appending, bool IsClosed);
LocalMinima *m_CurrentLM; LocalMinima *m_CurrentLM;
LocalMinima *m_MinimaList; LocalMinima *m_MinimaList;
bool m_UseFullRange; bool m_UseFullRange;
EdgeList m_edges; EdgeList m_edges;
bool m_PreserveCollinear;
bool m_HasOpenPaths;
}; };
//------------------------------------------------------------------------- -----
class Clipper : public virtual ClipperBase class Clipper : public virtual ClipperBase
{ {
public: public:
Clipper(); Clipper(int initOptions = 0);
~Clipper(); ~Clipper();
bool Execute(ClipType clipType, bool Execute(ClipType clipType,
Polygons &solution, Paths &solution,
PolyFillType subjFillType = pftEvenOdd, PolyFillType subjFillType = pftEvenOdd,
PolyFillType clipFillType = pftEvenOdd); PolyFillType clipFillType = pftEvenOdd);
bool Execute(ClipType clipType, bool Execute(ClipType clipType,
PolyTree &polytree, PolyTree &polytree,
PolyFillType subjFillType = pftEvenOdd, PolyFillType subjFillType = pftEvenOdd,
PolyFillType clipFillType = pftEvenOdd); PolyFillType clipFillType = pftEvenOdd);
void Clear(); void Clear();
bool ReverseSolution() {return m_ReverseOutput;}; bool ReverseSolution() {return m_ReverseOutput;};
void ReverseSolution(bool value) {m_ReverseOutput = value;}; void ReverseSolution(bool value) {m_ReverseOutput = value;};
bool ForceSimple() {return m_ForceSimple;}; bool StrictlySimple() {return m_StrictSimple;};
void ForceSimple(bool value) {m_ForceSimple = value;}; void StrictlySimple(bool value) {m_StrictSimple = value;};
//set the callback function for z value filling on intersections (otherwi
se Z is 0)
#ifdef use_xyz
void ZFillFunction(TZFillCallback zFillFunc);
#endif
protected: protected:
void Reset(); void Reset();
virtual bool ExecuteInternal(); virtual bool ExecuteInternal();
private: private:
PolyOutList m_PolyOuts; PolyOutList m_PolyOuts;
JoinList m_Joins; JoinList m_Joins;
HorzJoinList m_HorizJoins; JoinList m_GhostJoins;
ClipType m_ClipType; ClipType m_ClipType;
Scanbeam *m_Scanbeam; std::set< cInt, std::greater<cInt> > m_Scanbeam;
TEdge *m_ActiveEdges; TEdge *m_ActiveEdges;
TEdge *m_SortedEdges; TEdge *m_SortedEdges;
IntersectNode *m_IntersectNodes; IntersectNode *m_IntersectNodes;
bool m_ExecuteLocked; bool m_ExecuteLocked;
PolyFillType m_ClipFillType; PolyFillType m_ClipFillType;
PolyFillType m_SubjFillType; PolyFillType m_SubjFillType;
bool m_ReverseOutput; bool m_ReverseOutput;
bool m_UsingPolyTree; bool m_UsingPolyTree;
bool m_ForceSimple; bool m_StrictSimple;
void DisposeScanbeamList(); #ifdef use_xyz
TZFillCallback m_ZFill; //custom callback
#endif
void SetWindingCount(TEdge& edge); void SetWindingCount(TEdge& edge);
bool IsEvenOddFillType(const TEdge& edge) const; bool IsEvenOddFillType(const TEdge& edge) const;
bool IsEvenOddAltFillType(const TEdge& edge) const; bool IsEvenOddAltFillType(const TEdge& edge) const;
void InsertScanbeam(const long64 Y); void InsertScanbeam(const cInt Y);
long64 PopScanbeam(); cInt PopScanbeam();
void InsertLocalMinimaIntoAEL(const long64 botY); void InsertLocalMinimaIntoAEL(const cInt botY);
void InsertEdgeIntoAEL(TEdge *edge); void InsertEdgeIntoAEL(TEdge *edge, TEdge* startEdge);
void AddEdgeToSEL(TEdge *edge); void AddEdgeToSEL(TEdge *edge);
void CopyAELToSEL(); void CopyAELToSEL();
void DeleteFromSEL(TEdge *e); void DeleteFromSEL(TEdge *e);
void DeleteFromAEL(TEdge *e); void DeleteFromAEL(TEdge *e);
void UpdateEdgeIntoAEL(TEdge *&e); void UpdateEdgeIntoAEL(TEdge *&e);
void SwapPositionsInSEL(TEdge *edge1, TEdge *edge2); void SwapPositionsInSEL(TEdge *edge1, TEdge *edge2);
bool IsContributing(const TEdge& edge) const; bool IsContributing(const TEdge& edge) const;
bool IsTopHorz(const long64 XPos); bool IsTopHorz(const cInt XPos);
void SwapPositionsInAEL(TEdge *edge1, TEdge *edge2); void SwapPositionsInAEL(TEdge *edge1, TEdge *edge2);
void DoMaxima(TEdge *e, long64 topY); void DoMaxima(TEdge *e);
void ProcessHorizontals(); void PrepareHorzJoins(TEdge* horzEdge, bool isTopOfScanbeam);
void ProcessHorizontal(TEdge *horzEdge); void ProcessHorizontals(bool IsTopOfScanbeam);
void ProcessHorizontal(TEdge *horzEdge, bool isTopOfScanbeam);
void AddLocalMaxPoly(TEdge *e1, TEdge *e2, const IntPoint &pt); void AddLocalMaxPoly(TEdge *e1, TEdge *e2, const IntPoint &pt);
void AddLocalMinPoly(TEdge *e1, TEdge *e2, const IntPoint &pt); OutPt* AddLocalMinPoly(TEdge *e1, TEdge *e2, const IntPoint &pt);
OutRec* GetOutRec(int idx); OutRec* GetOutRec(int idx);
void AppendPolygon(TEdge *e1, TEdge *e2); void AppendPolygon(TEdge *e1, TEdge *e2);
void IntersectEdges(TEdge *e1, TEdge *e2, void IntersectEdges(TEdge *e1, TEdge *e2,
const IntPoint &pt, const IntersectProtects protects); const IntPoint &pt, bool protect = false);
OutRec* CreateOutRec(); OutRec* CreateOutRec();
void AddOutPt(TEdge *e, const IntPoint &pt); OutPt* AddOutPt(TEdge *e, const IntPoint &pt);
void DisposeAllPolyPts(); void DisposeAllOutRecs();
void DisposeOutRec(PolyOutList::size_type index); void DisposeOutRec(PolyOutList::size_type index);
bool ProcessIntersections(const long64 botY, const long64 topY); bool ProcessIntersections(const cInt botY, const cInt topY);
void InsertIntersectNode(TEdge *e1, TEdge *e2, const IntPoint &pt); void InsertIntersectNode(TEdge *e1, TEdge *e2, const IntPoint &pt);
void BuildIntersectList(const long64 botY, const long64 topY); void BuildIntersectList(const cInt botY, const cInt topY);
void ProcessIntersectList(); void ProcessIntersectList();
void ProcessEdgesAtTopOfScanbeam(const long64 topY); void ProcessEdgesAtTopOfScanbeam(const cInt topY);
void BuildResult(Polygons& polys); void BuildResult(Paths& polys);
void BuildResult2(PolyTree& polytree); void BuildResult2(PolyTree& polytree);
void SetHoleState(TEdge *e, OutRec *outrec); void SetHoleState(TEdge *e, OutRec *outrec);
void DisposeIntersectNodes(); void DisposeIntersectNodes();
bool FixupIntersectionOrder(); bool FixupIntersectionOrder();
void FixupOutPolygon(OutRec &outrec); void FixupOutPolygon(OutRec &outrec);
bool IsHole(TEdge *e); bool IsHole(TEdge *e);
void FixHoleLinkage(OutRec &outrec); void FixHoleLinkage(OutRec &outrec);
void AddJoin(TEdge *e1, TEdge *e2, int e1OutIdx = -1, int e2OutIdx = -1); void AddJoin(OutPt *op1, OutPt *op2, const IntPoint offPt);
void ClearJoins(); void ClearJoins();
void AddHorzJoin(TEdge *e, int idx); void ClearGhostJoins();
void ClearHorzJoins(); void AddGhostJoin(OutPt *op, const IntPoint offPt);
bool JoinPoints(const JoinRec *j, OutPt *&p1, OutPt *&p2); bool JoinPoints(const Join *j, OutPt *&p1, OutPt *&p2);
void FixupJoinRecs(JoinRec *j, OutPt *pt, unsigned startIdx);
void JoinCommonEdges(); void JoinCommonEdges();
void DoSimplePolygons(); void DoSimplePolygons();
void FixupFirstLefts1(OutRec* OldOutRec, OutRec* NewOutRec); void FixupFirstLefts1(OutRec* OldOutRec, OutRec* NewOutRec);
void FixupFirstLefts2(OutRec* OldOutRec, OutRec* NewOutRec); void FixupFirstLefts2(OutRec* OldOutRec, OutRec* NewOutRec);
#ifdef use_xyz
void SetZ(IntPoint& pt, TEdge& e);
#endif
}; };
//-------------------------------------------------------------------------
-----
//------------------------------------------------------------------------- ----- //------------------------------------------------------------------------- -----
class clipperException : public std::exception class clipperException : public std::exception
{ {
public: public:
clipperException(const char* description): m_descr(description) {} clipperException(const char* description): m_descr(description) {}
virtual ~clipperException() throw() {} virtual ~clipperException() throw() {}
virtual const char* what() const throw() {return m_descr.c_str();} virtual const char* what() const throw() {return m_descr.c_str();}
private: private:
std::string m_descr; std::string m_descr;
 End of changes. 44 change blocks. 
163 lines changed or deleted 196 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/