KiCad PCB EDA Suite
SutherlandHodgmanClipPoly.h
Go to the documentation of this file.
1 /********************************************************************************
2 * Copyright (C) 2004 Sjaak Priester
3 *
4 * This is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation; either version 2 of the License, or
7 * (at your option) any later version.
8 *
9 * This file is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with Tinter; if not, write to the Free Software
16 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17 ********************************************************************************/
18 
19 // SutherlandHodgman
20 // Class to perform polygon clipping against an upright rectangular boundary window.
21 // Implementation of Sutherland-Hodgman algorithm (1974).
22 //
23 // Version 1.0 (C) 2004, Sjaak Priester, Amsterdam.
24 // mailto:sjaak@sjaakpriester.nl
25 // http://www.sjaakpriester.nl
26 
27 #ifndef __SUTHERLAND_HODGMAN_H__
28 #define __SUTHERLAND_HODGMAN_H__
29 
30 
31 #include <vector>
32 #include <functional>
33 
34 #ifndef _GDIPLUS_H
35 
36 // I designed this with GDI+ in mind. However, this particular code doesn't
37 // use GDI+ at all, only some of it's variable types.
38 // These definitions are substitutes for those of GDI+.
39 typedef double REAL;
40 class PointF
41 {
42 public:
45 
46  PointF() : X( 0 )
47  , Y( 0 ) { }
48  PointF( const PointF& p ) : X( p.X )
49  , Y( p.Y ) { }
50  PointF( REAL x, REAL y ) : X( x )
51  , Y( y ) { }
52  PointF operator+( const PointF& p ) const { return PointF( X + p.X, Y + p.Y ); }
53  PointF operator-( const PointF& p ) const { return PointF( X - p.X, Y - p.Y ); }
54  bool Equals( const PointF& p ) { return (X == p.X) && (Y == p.Y); }
55 };
56 
57 class RectF
58 {
59 public:
64 
65  RectF() { X = 0, Y = 0, Height = 0, Width = 0; }
66  RectF( const RectF& r )
67  {
68  X = r.X; Y = r.Y; Height = r.Height, Width = r.Width;
69  }
70 
71 
72  RectF( REAL x, REAL y, REAL w, REAL h ) : X( x ), Y( y ),Width( w ), Height( h )
73  { }
74  REAL GetLeft() const { return X; }
75  REAL GetTop() const { return Y; }
76  REAL GetRight() const { return X + Width; }
77  REAL GetBottom() const { return Y + Height; }
78 };
79 
80 #endif // _GDIPLUS_H
81 
82 typedef std::vector<PointF> pointVector;
83 typedef std::vector<PointF>::iterator pointIterator;
84 typedef std::vector<PointF>::const_iterator cpointIterator;
85 
87 {
88 public:
89 
90  // Constructor. Parameter is the boundary rectangle.
91  // SutherlandHodgman expects a 'normalized' boundary rectangle, meaning
92  // that boundaries.GetRight() > boundaries.GetLeft() and
93  // boundaries.GetBottom() > boundaries.GetTop().
94  // In other words: boundary.Width > 0 and boundaries.Height > 0.
95  // If this is violated, nothing will be output.
96  SutherlandHodgman( RectF& boundaries ) :
97  m_stageBottom( m_stageOut, boundaries.GetBottom() )
98  , /* Initialize each stage */ m_stageLeft( m_stageBottom, boundaries.GetLeft() )
99  , /* with its next stage and */ m_stageTop( m_stageLeft, boundaries.GetTop() )
100  , /* the boundary position. */ m_stageRight( m_stageTop, boundaries.GetRight() )
101  {
102  }
103 
104 
105  void Clip( pointVector& input, pointVector& clipped )
106  {
107  clipped.clear();
108  m_stageOut.SetDestination( &clipped );
109 
110  // Clip each input vertex.
111  for( cpointIterator it = input.begin(); it != input.end(); ++it )
112  m_stageRight.HandleVertex( *it );
113 
114  // Do the final step.
116  }
117 
118 
119 private:
120 
121  // Implementation of a horizontal boundary (top or bottom).
122  // Comp is a std::binary_function object, comparing its two parameters, f.i. std::less.
123 
124  template <class Comp>
125 
127  {
128 public:
129  BoundaryHor( REAL y ) : m_Y( y ) { }
130  bool IsInside( const PointF& pnt ) const
131  {
132  return Comp ()( pnt.Y, m_Y );
133  } // return true if pnt.Y is at the inside of the boundary
134  PointF Intersect( const PointF& p0, const PointF& p1 ) const // return intersection point of line p0...p1 with boundary
135  { // assumes p0...p1 is not strictly horizontal
136  PointF d = p1 - p0;
137  REAL xslope = d.X / d.Y;
138 
139  PointF r;
140 
141  r.Y = m_Y;
142  r.X = p0.X + xslope * (m_Y - p0.Y);
143  return r;
144  }
145 
146 
147 private:
149  };
150 
151  // Implementation of a vertical boundary (left or right).
152  template <class Comp>
154  {
155 public:
156  BoundaryVert( REAL x ) : m_X( x )
157  { }
158  bool IsInside( const PointF& pnt ) const
159  {
160  return Comp() ( pnt.X, m_X );
161  }
162  PointF Intersect( const PointF& p0, const PointF& p1 ) const // assumes p0...p1 is not strictly vertical
163  {
164  PointF d = p1 - p0;
165  REAL yslope = d.Y / d.X;
166 
167  PointF r;
168 
169  r.X = m_X;
170  r.Y = p0.Y + yslope * (m_X - p0.X);
171  return r;
172  }
173 
174 
175 private:
177  };
178 
179  // This template class is the workhorse of the algorithm. It handles the clipping against one boundary.
180  // Boundary is either BoundaryHor or BoundaryVert, Stage is the next ClipStage, or the output stage.
181  template <class Boundary, class Stage>
182  class ClipStage : private Boundary
183  {
184 public:
185  ClipStage( Stage& nextStage, REAL position ) :
186  Boundary( position ) , m_NextStage( nextStage ), m_bFirst( true ), m_bPreviousInside( false )
187  { }
188 
189  // Function to handle one vertex
190  void HandleVertex( const PointF& pntCurrent )
191  {
192  bool bCurrentInside = this->IsInside( pntCurrent ); // See if vertex is inside the boundary.
193 
194  if( m_bFirst ) // If this is the first vertex...
195  {
196  m_pntFirst = pntCurrent; // ... just remember it,...
197 
198  m_bFirst = false;
199  }
200  else // Common cases, not the first vertex.
201  {
202  if( bCurrentInside ) // If this vertex is inside...
203  {
204  if( !m_bPreviousInside ) // ... and the previous one was outside
205  m_NextStage.HandleVertex( this->Intersect( m_pntPrevious, pntCurrent ) );
206 
207  // ... first output the intersection point.
208 
209  m_NextStage.HandleVertex( pntCurrent ); // Output the current vertex.
210  }
211  else if( m_bPreviousInside ) // If this vertex is outside, and the previous one was inside...
212  m_NextStage.HandleVertex( this->Intersect( m_pntPrevious, pntCurrent ) );
213 
214  // ... output the intersection point.
215 
216  // If neither current vertex nor the previous one are inside, output nothing.
217  }
218  m_pntPrevious = pntCurrent; // Be prepared for next vertex.
219  m_bPreviousInside = bCurrentInside;
220  }
221 
222 
223  void Finalize()
224  {
225  HandleVertex( m_pntFirst ); // Close the polygon.
226  m_NextStage.Finalize(); // Delegate to the next stage.
227  }
228 
229 
230 private:
231  Stage& m_NextStage; // the next stage
232  bool m_bFirst; // true if no vertices have been handled
233  PointF m_pntFirst; // the first vertex
234  PointF m_pntPrevious; // the previous vertex
235  bool m_bPreviousInside; // true if the previous vertex was inside the Boundary
236  };
237 
239  {
240 public:
241  OutputStage() : m_pDest( 0 ) { }
242  void SetDestination( pointVector* pDest ) { m_pDest = pDest; }
243  void HandleVertex( const PointF& pnt ) { m_pDest->push_back( pnt ); } // Append the vertex to the output container.
244  void Finalize() { } // Do nothing.
245 private:
247  };
248 
249  // These typedefs define the four boundaries. In keeping up with the GDI/GDI+ interpretation of
250  // rectangles, we include the left and top boundaries, but not the right and bottom boundaries.
251  // In other words: a vertex on the left boundary is considered to be inside, but a vertex
252  // on the right boundary is considered to be outside.
257 
258  // Next typedefs define the four stages. First template parameter is the boundary,
259  // second template parameter is the next stage.
264 
265  // Our data members.
267  ClipBottom m_stageBottom;
268  ClipLeft m_stageLeft;
269  ClipTop m_stageTop;
270  ClipRight m_stageRight;
271 };
272 
273 #endif
REAL GetBottom() const
bool IsInside(const PointF &pnt) const
std::vector< PointF > pointVector
ClipStage< BoundaryRight, ClipTop > ClipRight
double REAL
PointF(REAL x, REAL y)
bool IsInside(const PointF &pnt) const
BoundaryVert< std::greater_equal< REAL > > BoundaryLeft
REAL GetTop() const
std::vector< PointF >::const_iterator cpointIterator
bool Equals(const PointF &p)
ClipStage< BoundaryTop, ClipLeft > ClipTop
BoundaryHor< std::greater_equal< REAL > > BoundaryTop
RectF(const RectF &r)
RectF(REAL x, REAL y, REAL w, REAL h)
BoundaryHor< std::less< REAL > > BoundaryBottom
PointF operator+(const PointF &p) const
REAL GetRight() const
PointF Intersect(const PointF &p0, const PointF &p1) const
ClipStage(Stage &nextStage, REAL position)
SutherlandHodgman(RectF &boundaries)
void Clip(pointVector &input, pointVector &clipped)
std::vector< PointF >::iterator pointIterator
PointF Intersect(const PointF &p0, const PointF &p1) const
ClipStage< BoundaryBottom, OutputStage > ClipBottom
ClipStage< BoundaryLeft, ClipBottom > ClipLeft
void HandleVertex(const PointF &pntCurrent)
REAL GetLeft() const
BoundaryVert< std::less< REAL > > BoundaryRight
PointF operator-(const PointF &p) const
PointF(const PointF &p)