KiCad PCB EDA Suite
cpolygon2d.cpp
Go to the documentation of this file.
1 /*
2  * This program source code file is part of KiCad, a free EDA CAD application.
3  *
4  * Copyright (C) 2015-2016 Mario Luzeiro <mrluzeiro@ua.pt>
5  * Copyright (C) 1992-2016 KiCad Developers, see AUTHORS.txt for contributors.
6  *
7  * This program is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU General Public License
9  * as published by the Free Software Foundation; either version 2
10  * of the License, or (at your option) any later version.
11  *
12  * This program is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15  * GNU General Public License for more details.
16  *
17  * You should have received a copy of the GNU General Public License
18  * along with this program; if not, you may find one here:
19  * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
20  * or you may search the http://www.gnu.org website for the version 2 license,
21  * or you may write to the Free Software Foundation, Inc.,
22  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
23  */
24 
30 #include "cpolygon2d.h"
31 #include <wx/debug.h>
32 #include <fctsys.h>
33 
34 #ifdef PRINT_STATISTICS_3D_VIEWER
35 #include <stdio.h>
36 #endif
37 
38 // CPOLYGONBLOCK2D
39 // /////////////////////////////////////////////////////////////////////////////
40 
41 static bool polygon_IsPointInside( const SEGMENTS &aSegments, const SFVEC2F &aPoint )
42 {
43  wxASSERT( aSegments.size() >= 3 );
44 
45  unsigned int i;
46  unsigned int j = aSegments.size() - 1;
47  bool oddNodes = false;
48 
49  for( i = 0; i < aSegments.size(); j = i++ )
50  {
51  const float polyJY = aSegments[j].m_Start.y;
52  const float polyIY = aSegments[i].m_Start.y;
53 
54  if( ((polyIY <= aPoint.y) && (polyJY >= aPoint.y)) ||
55  ((polyJY <= aPoint.y) && (polyIY >= aPoint.y))
56  )
57  {
58  const float polyJX = aSegments[j].m_Start.x;
59  const float polyIX = aSegments[i].m_Start.x;
60 
61  if( (polyIX <= aPoint.x) || (polyJX <= aPoint.x) )
62  oddNodes ^= ( ( polyIX +
63  ( ( aPoint.y - polyIY ) *
64  aSegments[i].m_inv_JY_minus_IY ) *
65  aSegments[i].m_JX_minus_IX ) < aPoint.x );
66  }
67  }
68 
69  return oddNodes;
70 }
71 
72 
74  const OUTERS_AND_HOLES &aOuter_and_holes,
75  const BOARD_ITEM &aBoardItem ) :
76  COBJECT2D( OBJ2D_POLYGON, aBoardItem )
77 {
78  m_open_segments.resize( aOpenSegmentList.size() );
79 
80  // Copy vectors and structures
81  for( unsigned int i = 0; i < aOpenSegmentList.size(); i++ )
82  m_open_segments[i] = aOpenSegmentList[i];
83 
84  m_outers_and_holes = aOuter_and_holes;
85 
86  // Compute bounding box with the points of the polygon
87  m_bbox.Reset();
88 
89  for( unsigned int i = 0; i < m_outers_and_holes.m_Outers.size(); i++ )
90  {
91  for( unsigned int j = 0; j < m_outers_and_holes.m_Outers[i].size(); j++ )
92  m_bbox.Union( ((SEGMENTS)m_outers_and_holes.m_Outers[i])[j].m_Start );
93  }
94 
97 
98  // Some checks
99  wxASSERT( m_open_segments.size() == aOpenSegmentList.size() );
100  wxASSERT( m_open_segments.size() > 0 );
101 
102  wxASSERT( m_outers_and_holes.m_Outers.size() > 0 );
103  wxASSERT( m_outers_and_holes.m_Outers.size() == aOuter_and_holes.m_Outers.size() );
104  wxASSERT( m_outers_and_holes.m_Holes.size() == aOuter_and_holes.m_Holes.size() );
105 
106  wxASSERT( m_outers_and_holes.m_Outers[0].size() >= 3 );
107  wxASSERT( m_outers_and_holes.m_Outers[0].size() ==
108  aOuter_and_holes.m_Outers[0].size() );
109 
110  wxASSERT( m_bbox.IsInitialized() );
111 }
112 
113 
114 bool CPOLYGONBLOCK2D::Intersects( const CBBOX2D &aBBox ) const
115 {
116  return m_bbox.Intersects( aBBox );
117 
118  // !TODO: this is a quick not perfect implementation
119  // in order to make it perfect the box must be checked against all the
120  // polygons in the outers and not inside the holes
121 }
122 
123 
124 bool CPOLYGONBLOCK2D::Overlaps( const CBBOX2D &aBBox ) const
125 {
126  // NOT IMPLEMENTED
127  return false;
128 }
129 
130 
132  float *aOutT,
133  SFVEC2F *aNormalOut ) const
134 {
135  int hitIndex = -1;
136  float hitU = 0.0f;
137  float tMin = 0.0f;
138 
139  for( unsigned int i = 0; i < m_open_segments.size(); i++ )
140  {
141  const SFVEC2F &s = m_open_segments[i].m_Precalc_slope;
142  const SFVEC2F &q = m_open_segments[i].m_Start;
143 
144  float rxs = aSegRay.m_End_minus_start.x * s.y -
145  aSegRay.m_End_minus_start.y * s.x;
146 
147  if( fabs(rxs) > FLT_EPSILON )
148  {
149  const float inv_rxs = 1.0f / rxs;
150 
151  const SFVEC2F pq = q - aSegRay.m_Start;
152 
153  const float t = (pq.x * s.y - pq.y * s.x) * inv_rxs;
154 
155  if( (t < 0.0f) || (t > 1.0f) )
156  continue;
157 
158  const float u = ( pq.x * aSegRay.m_End_minus_start.y -
159  pq.y * aSegRay.m_End_minus_start.x ) * inv_rxs;
160 
161  if( (u < 0.0f) || (u > 1.0f) )
162  continue;
163 
164  if( ( hitIndex == -1 ) || ( t <= tMin ) )
165  {
166  tMin = t;
167  hitIndex = i;
168  hitU = u;
169  }
170  }
171  }
172 
173  if( hitIndex >= 0 )
174  {
175  wxASSERT( (tMin >= 0.0f) && (tMin <= 1.0f) );
176 
177  *aOutT = tMin;
178  *aNormalOut = glm::normalize(
179  m_open_segments[hitIndex].m_Normals.m_Start * hitU +
180  m_open_segments[hitIndex].m_Normals.m_End *
181  (1.0f - hitU) );
182 
183  return true;
184  }
185 
186  return false;
187 }
188 
189 
191 {
192 
193  return INTR_MISSES;
194 }
195 
196 
197 bool CPOLYGONBLOCK2D::IsPointInside( const SFVEC2F &aPoint ) const
198 {
199  // NOTE: we could add here a test for the bounding box, but because in the
200  // 3d object it already checked for a 3d bbox.
201 
202  // First test if point is inside a hole.
203  // If true it can early exit
204  for( unsigned int i = 0; i < m_outers_and_holes.m_Holes.size(); i++ )
205  if( !m_outers_and_holes.m_Holes[i].empty() )
207  return false;
208 
209  // At this moment, the point is not inside a hole, so check if it is
210  // inside the polygon
211  for( unsigned int i = 0; i < m_outers_and_holes.m_Outers.size(); i++ )
212  if( !m_outers_and_holes.m_Outers.empty() )
214  return true;
215 
216  // Miss the polygon
217  return false;
218 }
219 
220 
221 // CDUMMYBLOCK2D
222 // /////////////////////////////////////////////////////////////////////////////
223 
224 CDUMMYBLOCK2D::CDUMMYBLOCK2D( const SFVEC2F &aPbMin, const SFVEC2F &aPbMax,
225  const BOARD_ITEM &aBoardItem ) :
226  COBJECT2D( OBJ2D_DUMMYBLOCK, aBoardItem )
227 {
228  m_bbox.Set( aPbMin, aPbMax );
231 }
232 
233 
235  const BOARD_ITEM &aBoardItem ) :
236  COBJECT2D( OBJ2D_DUMMYBLOCK, aBoardItem )
237 {
238  m_bbox.Set( aBBox );
241 }
242 
243 
244 bool CDUMMYBLOCK2D::Intersects( const CBBOX2D &aBBox ) const
245 {
246  return m_bbox.Intersects( aBBox );
247 }
248 
249 
250 bool CDUMMYBLOCK2D::Overlaps( const CBBOX2D &aBBox ) const
251 {
252  // Not implemented
253  return false;
254 }
255 
256 
257 bool CDUMMYBLOCK2D::Intersect( const RAYSEG2D &aSegRay,
258  float *aOutT,
259  SFVEC2F *aNormalOut ) const
260 {
261  // The dummy block will be never intersected because it have no edges,
262  // only it have a plan surface of the size of the bounding box
263  return false;
264 }
265 
266 
268 {
270  return INTR_MISSES;
271 }
272 
273 
274 bool CDUMMYBLOCK2D::IsPointInside( const SFVEC2F &aPoint ) const
275 {
276  // The dummy is filled in all his bounding box, so if it hit the bbox
277  // it will hit this dummy
278  if( m_bbox.Inside( aPoint ) )
279  return true;
280 
281  return false;
282 }
283 
284 
285 // Polygon process and conversion
286 // ////////////////////////////////////////////////////////////////////////////
287 
288 typedef std::vector<SFVEC2F> KF_POINTS;
289 
290 #define MAX_NR_DIVISIONS 96
291 
292 
293 static bool intersect( const SEGMENT_WITH_NORMALS &aSeg,
294  const SFVEC2F &aStart,
295  const SFVEC2F &aEnd )
296 {
297  const SFVEC2F r = aEnd - aStart;
298  const SFVEC2F s = aSeg.m_Precalc_slope;
299  const SFVEC2F q = aSeg.m_Start;
300 
301  const float rxs = r.x * s.y - r.y * s.x;
302 
303  if( fabs(rxs) > glm::epsilon<float>() )
304  {
305  const float inv_rxs = 1.0f / rxs;
306 
307  const SFVEC2F pq = q - aStart;
308 
309  const float t = (pq.x * s.y - pq.y * s.x) * inv_rxs;
310 
311  if( (t < 0.0f) || (t > 1.0f) )
312  return false;
313 
314  const float u = (pq.x * r.y - pq.y * r.x) * inv_rxs;
315 
316  if( (u < 0.0f) || (u > 1.0f) )
317  return false;
318 
319  return true;
320  }
321 
322  return false;
323 }
324 
325 
326 static void extractPathsFrom( const SEGMENTS_WIDTH_NORMALS &aSegList,
327  const CBBOX2D &aBBox,
328  SEGMENTS_WIDTH_NORMALS &aOutSegThatIntersect )
329 {
330  wxASSERT( aSegList.size () >= 3 );
331 
332  unsigned int i;
333  unsigned int j = aSegList.size() - 1;
334 
335  const SFVEC2F p1( aBBox.Min().x, aBBox.Min().y );
336  const SFVEC2F p2( aBBox.Max().x, aBBox.Min().y );
337  const SFVEC2F p3( aBBox.Max().x, aBBox.Max().y );
338  const SFVEC2F p4( aBBox.Min().x, aBBox.Max().y );
339 
340  aOutSegThatIntersect.clear();
341 
342  for( i = 0; i < aSegList.size(); j = i++ )
343  {
344  if( aBBox.Inside( aSegList[i].m_Start ) ||
345  aBBox.Inside( aSegList[j].m_Start ) )
346  {
347  // if the segment points are inside the bounding box then this
348  // segment is touching the bbox.
349  aOutSegThatIntersect.push_back( aSegList[i] );
350  }
351  else
352  {
353  // Check if a segment intersects the bounding box
354 
355  // Make a bounding box based on the segments start and end
356  CBBOX2D segmentBBox( aSegList[i].m_Start,
357  aSegList[j].m_Start );
358 
359  if( aBBox.Intersects( segmentBBox ) )
360  {
361 
362  const SEGMENT_WITH_NORMALS &seg = aSegList[i];
363 
364  if( intersect( seg, p1, p2 ) ||
365  intersect( seg, p2, p3 ) ||
366  intersect( seg, p3, p4 ) ||
367  intersect( seg, p4, p1 ) )
368  {
369  aOutSegThatIntersect.push_back( seg );
370  }
371  }
372  }
373  }
374 }
375 
376 
377 static void polygon_Convert( const SHAPE_LINE_CHAIN &aPath,
378  SEGMENTS &aOutSegment,
379  float aBiuTo3DunitsScale )
380 {
381  aOutSegment.resize( aPath.PointCount() );
382 
383  for( int j = 0; j < aPath.PointCount(); j++ )
384  {
385  const VECTOR2I &a = aPath.CPoint( j );
386 
387  aOutSegment[j].m_Start = SFVEC2F( (float) a.x * aBiuTo3DunitsScale,
388  (float)-a.y * aBiuTo3DunitsScale );
389  }
390 
391  unsigned int i;
392  unsigned int j = aOutSegment.size () - 1;
393 
394  for( i = 0; i < aOutSegment.size (); j = i++ )
395  {
396  // Calculate constants for each segment
397  aOutSegment[i].m_inv_JY_minus_IY = 1.0f / ( aOutSegment[j].m_Start.y -
398  aOutSegment[i].m_Start.y );
399 
400  aOutSegment[i].m_JX_minus_IX = (aOutSegment[j].m_Start.x -
401  aOutSegment[i].m_Start.x);
402  }
403 }
404 
405 
407  const SHAPE_POLY_SET &aMainPath,
408  CGENERICCONTAINER2D &aDstContainer,
409  float aBiuTo3DunitsScale,
410  float aDivFactor,
411  const BOARD_ITEM &aBoardItem )
412 {
413  BOX2I pathBounds = aMainPath.BBox();
414 
415  // Get the path
416 
417  wxASSERT( aMainPath.OutlineCount() == 1 );
418  const SHAPE_POLY_SET::POLYGON& curr_polywithholes = aMainPath.CPolygon( 0 );
419 
420  wxASSERT( curr_polywithholes.size() == 1 );
421  const SHAPE_LINE_CHAIN& path = curr_polywithholes[0]; // a simple polygon
422 
423  // Convert the points to segments class
424  CBBOX2D bbox;
425  bbox.Reset();
426 
427  // Contains the main list of segments and each segment normal interpolated
428  SEGMENTS_WIDTH_NORMALS segments_and_normals;
429 
430  // Contains a closed polygon used to calc if points are inside
431  SEGMENTS segments;
432 
433  segments_and_normals.resize( path.PointCount() );
434  segments.resize( path.PointCount() );
435 
436  for( int i = 0; i < path.PointCount(); i++ )
437  {
438  const VECTOR2I& a = path.CPoint( i );
439 
440  const SFVEC2F point ( (float)( a.x) * aBiuTo3DunitsScale,
441  (float)(-a.y) * aBiuTo3DunitsScale );
442 
443  bbox.Union( point );
444  segments_and_normals[i].m_Start = point;
445  segments[i].m_Start = point;
446  }
447 
448  bbox.ScaleNextUp();
449 
450 
451  // Calc the slopes, normals and some statistics about this polygon
452  unsigned int i;
453  unsigned int j = segments_and_normals.size() - 1;
454 
455  // Temporary normal to the segment, it will later be used for interpolation
456  std::vector< SFVEC2F > tmpSegmentNormals;
457  tmpSegmentNormals.resize( segments_and_normals.size() );
458 
459  float medOfTheSquaresSegmentLength = 0.0f;
460 #ifdef PRINT_STATISTICS_3D_VIEWER
461  float minLength = FLT_MAX;
462 #endif
463 
464  for( i = 0; i < segments_and_normals.size(); j = i++ )
465  {
466  const SFVEC2F slope = segments_and_normals[j].m_Start -
467  segments_and_normals[i].m_Start;
468 
469  segments_and_normals[i].m_Precalc_slope = slope;
470 
471  // Calculate constants for each segment
472  segments[i].m_inv_JY_minus_IY = 1.0f / ( segments_and_normals[j].m_Start.y -
473  segments_and_normals[i].m_Start.y );
474 
475  segments[i].m_JX_minus_IX = ( segments_and_normals[j].m_Start.x -
476  segments_and_normals[i].m_Start.x );
477 
478  // The normal orientation expect a fixed polygon orientation (!TODO: which one?)
479  //tmpSegmentNormals[i] = glm::normalize( SFVEC2F( -slope.y, +slope.x ) );
480  tmpSegmentNormals[i] = glm::normalize( SFVEC2F( slope.y, -slope.x ) );
481 
482  const float length = slope.x * slope.x + slope.y * slope.y;
483 
484 #ifdef PRINT_STATISTICS_3D_VIEWER
485  if( length < minLength )
486  minLength = length;
487 #endif
488 
489  medOfTheSquaresSegmentLength += length;
490  }
491 
492 #ifdef PRINT_STATISTICS_3D_VIEWER
493  float minSegmentLength = sqrt( minLength );
494 #endif
495 
496  // This calc an approximation of medium lengths, that will be used to calc
497  // the size of the division.
498  medOfTheSquaresSegmentLength /= segments_and_normals.size();
499  medOfTheSquaresSegmentLength = sqrt( medOfTheSquaresSegmentLength );
500 
501 
502  // Compute the normal interpolation
503  // If calculate the dot between the segments, if they are above/below some
504  // threshould it will not interpolated it (ex: if you are in a edge corner
505  // or in a smooth transaction)
506  j = segments_and_normals.size() - 1;
507  for( i = 0; i < segments_and_normals.size(); j = i++ )
508  {
509  const SFVEC2F normalBeforeSeg = tmpSegmentNormals[j];
510  const SFVEC2F normalSeg = tmpSegmentNormals[i];
511  const SFVEC2F normalAfterSeg = tmpSegmentNormals[ (i + 1) %
512  segments_and_normals.size() ];
513 
514  const float dotBefore = glm::dot( normalBeforeSeg, normalSeg );
515  const float dotAfter = glm::dot( normalAfterSeg, normalSeg );
516 
517  if( dotBefore < 0.7f )
518  segments_and_normals[i].m_Normals.m_Start = normalSeg;
519  else
520  segments_and_normals[i].m_Normals.m_Start =
521  glm::normalize( (((normalBeforeSeg * dotBefore ) + normalSeg) * 0.5f) );
522 
523  if( dotAfter < 0.7f )
524  segments_and_normals[i].m_Normals.m_End = normalSeg;
525  else
526  segments_and_normals[i].m_Normals.m_End =
527  glm::normalize( (((normalAfterSeg * dotAfter ) + normalSeg) * 0.5f) );
528  }
529 
530  if( aDivFactor == 0.0f )
531  aDivFactor = medOfTheSquaresSegmentLength;
532 
533  SFVEC2UI grid_divisions;
534  grid_divisions.x = (unsigned int)( (bbox.GetExtent().x / aDivFactor) );
535  grid_divisions.y = (unsigned int)( (bbox.GetExtent().y / aDivFactor) );
536 
537  grid_divisions = glm::clamp( grid_divisions ,
538  SFVEC2UI( 1, 1 ),
540 
541  // Calculate the steps advance of the grid
542  SFVEC2F blockAdvance;
543 
544  blockAdvance.x = bbox.GetExtent().x / (float)grid_divisions.x;
545  blockAdvance.y = bbox.GetExtent().y / (float)grid_divisions.y;
546 
547  wxASSERT( blockAdvance.x > 0.0f );
548  wxASSERT( blockAdvance.y > 0.0f );
549 
550  const int leftToRight_inc = (pathBounds.GetRight() - pathBounds.GetLeft()) /
551  grid_divisions.x;
552 
553  const int topToBottom_inc = (pathBounds.GetBottom() - pathBounds.GetTop()) /
554  grid_divisions.y;
555 
556  // Statistics
557  unsigned int stats_n_empty_blocks = 0;
558  unsigned int stats_n_dummy_blocks = 0;
559  unsigned int stats_n_poly_blocks = 0;
560  unsigned int stats_sum_size_of_polygons = 0;
561 
562 
563  // Step by each block of a grid trying to extract segments and create
564  // polygon blocks
565 
566  int topToBottom = pathBounds.GetTop();
567  float blockY = bbox.Max().y;
568 
569  for( unsigned int iy = 0; iy < grid_divisions.y; iy++ )
570  {
571 
572  int leftToRight = pathBounds.GetLeft();
573  float blockX = bbox.Min().x;
574 
575  for( unsigned int ix = 0; ix < grid_divisions.x; ix++ )
576  {
577  CBBOX2D blockBox( SFVEC2F( blockX,
578  blockY - blockAdvance.y ),
579  SFVEC2F( blockX + blockAdvance.x,
580  blockY ) );
581 
582  // Make the box large to it will catch (intersect) the edges
583  blockBox.ScaleNextUp();
584  blockBox.ScaleNextUp();
585  blockBox.ScaleNextUp();
586 
587  SEGMENTS_WIDTH_NORMALS extractedSegments;
588 
589  extractPathsFrom( segments_and_normals, blockBox, extractedSegments );
590 
591 
592  if( extractedSegments.empty() )
593  {
594 
595  SFVEC2F p1( blockBox.Min().x, blockBox.Min().y );
596  SFVEC2F p2( blockBox.Max().x, blockBox.Min().y );
597  SFVEC2F p3( blockBox.Max().x, blockBox.Max().y );
598  SFVEC2F p4( blockBox.Min().x, blockBox.Max().y );
599 
600  if( polygon_IsPointInside( segments, p1 ) ||
601  polygon_IsPointInside( segments, p2 ) ||
602  polygon_IsPointInside( segments, p3 ) ||
603  polygon_IsPointInside( segments, p4 ) )
604  {
605  // In this case, the segments are not intersecting the
606  // polygon, so it means that if any point is inside it,
607  // then all other are inside the polygon.
608  // This is a full bbox inside, so add a dummy box
609 
610  aDstContainer.Add( new CDUMMYBLOCK2D( blockBox, aBoardItem ) );
611  stats_n_dummy_blocks++;
612  }
613  else
614  {
615  // Points are outside, so this block complety missed the polygon
616  // In this case, no objects need to be added
617  stats_n_empty_blocks++;
618  }
619  }
620  else
621  {
622  // At this point, the borders of polygon were intersected by the
623  // bounding box, so we must calculate a new polygon that will
624  // close that small block.
625  // This block will be used to calculate if points are inside
626  // the (sub block) polygon.
627 
628  SHAPE_POLY_SET subBlockPoly;
629 
631  VECTOR2I( leftToRight,
632  topToBottom ),
633  VECTOR2I( leftToRight + leftToRight_inc,
634  topToBottom ),
635  VECTOR2I( leftToRight + leftToRight_inc,
636  topToBottom + topToBottom_inc ),
637  VECTOR2I( leftToRight,
638  topToBottom + topToBottom_inc ) );
639 
640  //sb.Append( leftToRight, topToBottom );
641  sb.SetClosed( true );
642 
643  subBlockPoly.AddOutline( sb );
644 
645  // We need here a strictly simple polygon with outlines and holes
646  SHAPE_POLY_SET solution;
647  solution.BooleanIntersection( aMainPath,
648  subBlockPoly,
650 
651  OUTERS_AND_HOLES outersAndHoles;
652 
653  outersAndHoles.m_Holes.clear();
654  outersAndHoles.m_Outers.clear();
655 
656  for( int idx = 0; idx < solution.OutlineCount(); idx++ )
657  {
658  const SHAPE_LINE_CHAIN & outline = solution.Outline( idx );
659 
660  SEGMENTS solutionSegment;
661 
662  polygon_Convert( outline, solutionSegment, aBiuTo3DunitsScale );
663  outersAndHoles.m_Outers.push_back( solutionSegment );
664 
665  stats_sum_size_of_polygons += solutionSegment.size();
666 
667  for( int holeIdx = 0;
668  holeIdx < solution.HoleCount( idx );
669  holeIdx++ )
670  {
671  const SHAPE_LINE_CHAIN & hole = solution.Hole( idx, holeIdx );
672 
673  polygon_Convert( hole, solutionSegment, aBiuTo3DunitsScale );
674  outersAndHoles.m_Holes.push_back( solutionSegment );
675  stats_sum_size_of_polygons += solutionSegment.size();
676  }
677 
678  }
679 
680  if( !outersAndHoles.m_Outers.empty() )
681  {
682  aDstContainer.Add( new CPOLYGONBLOCK2D( extractedSegments,
683  outersAndHoles,
684  aBoardItem ) );
685  stats_n_poly_blocks++;
686  }
687  }
688 
689  blockX += blockAdvance.x;
690  leftToRight += leftToRight_inc;
691  }
692 
693  blockY -= blockAdvance.y;
694  topToBottom += topToBottom_inc;
695  }
696 
697 #ifdef PRINT_STATISTICS_3D_VIEWER
698  printf( "////////////////////////////////////////////////////////////////////////////////\n" );
699  printf( "Convert_path_polygon_to_polygon_blocks_and_dummy_blocks\n" );
700  printf( " grid_divisions (%u, %u)\n", grid_divisions.x, grid_divisions.y );
701  printf( " N Total Blocks %u\n", grid_divisions.x * grid_divisions.y );
702  printf( " N Empty Blocks %u\n", stats_n_empty_blocks );
703  printf( " N Dummy Blocks %u\n", stats_n_dummy_blocks );
704  printf( " N Polyg Blocks %u\n", stats_n_poly_blocks );
705  printf( " Med N Seg Poly %u\n", stats_sum_size_of_polygons / stats_n_poly_blocks );
706  printf( " medOfTheSquaresSegmentLength %f\n", medOfTheSquaresSegmentLength );
707  printf( " minSegmentLength %f\n", minSegmentLength );
708  printf( " aDivFactor %f\n", aDivFactor );
709  printf( "////////////////////////////////////////////////////////////////////////////////\n" );
710 #endif
711 }
712 
713 
714 void Polygon_Calc_BBox_3DU( const SHAPE_POLY_SET &aPolysList,
715  CBBOX2D &aOutBBox ,
716  float aBiuTo3DunitsScale )
717 {
718  aOutBBox.Reset();
719 
720  for( int idx = 0; idx < aPolysList.OutlineCount(); ++idx )
721  {
722  // Each polygon in aPolysList is a polygon with holes
723  const SHAPE_POLY_SET::POLYGON& curr_polywithholes = aPolysList.CPolygon( idx );
724 
725  for( unsigned ipoly = 0; ipoly < curr_polywithholes.size(); ++ipoly )
726  {
727  const SHAPE_LINE_CHAIN& path = curr_polywithholes[ipoly]; // a simple polygon
728 
729  for( int jj = 0; jj < path.PointCount(); jj++ )
730  {
731  const VECTOR2I& a = path.CPoint( jj );
732 
733  aOutBBox.Union( SFVEC2F( (float) a.x * aBiuTo3DunitsScale,
734  (float)-a.y * aBiuTo3DunitsScale ) );
735  }
736  }
737  }
738 
739  aOutBBox.ScaleNextUp();
740 }
741 
742 
743 void Polygon_Convert( const KI_POLYGON &aPolygon,
744  ClipperLib::Path &aOutPath,
745  CBBOX2D &aOutBBox,
746  float aBiuTo3DunitsScale )
747 {
748  aOutPath.resize( aPolygon.size() );
749  aOutBBox.Reset();
750 
751  for( unsigned i = 0; i < aPolygon.size(); i++ )
752  {
753  const KI_POLY_POINT point = *(aPolygon.begin() + i);
754 
755  aOutPath[i] = ClipperLib::IntPoint( (ClipperLib::cInt)point.x(),
756  (ClipperLib::cInt)point.y() );
757 
758  aOutBBox.Union( SFVEC2F( (float) point.x() * aBiuTo3DunitsScale,
759  (float)-point.y() * aBiuTo3DunitsScale ) );
760  }
761 
762  aOutBBox.ScaleNextUp();
763 
764  ClipperLib::CleanPolygon( aOutPath );
765 }
766 
767 
768 #ifdef DEBUG
769 static void polygon_Convert( const ClipperLib::Path &aPath,
770  SEGMENTS &aOutSegment,
771  float aBiuTo3DunitsScale )
772 {
773  aOutSegment.resize( aPath.size() );
774 
775  for( unsigned i = 0; i < aPath.size(); i++ )
776  {
777  aOutSegment[i].m_Start = SFVEC2F( (float) aPath[i].X * aBiuTo3DunitsScale,
778  (float)-aPath[i].Y * aBiuTo3DunitsScale );
779  }
780 
781  unsigned int i;
782  unsigned int j = aOutSegment.size () - 1;
783 
784  for( i = 0; i < aOutSegment.size (); j = i++ )
785  {
786  // Calculate constants for each segment
787  aOutSegment[i].m_inv_JY_minus_IY = 1.0f / ( aOutSegment[j].m_Start.y -
788  aOutSegment[i].m_Start.y );
789  aOutSegment[i].m_JX_minus_IX = (aOutSegment[j].m_Start.x - aOutSegment[i].m_Start.x);
790  }
791 }
792 
794 {
795  // "This structure contains a sequence of IntPoint vertices defining a
796  // single contour"
797  ClipperLib::Path aPath;
798 
799  SEGMENTS aSegments;
800 
801  aPath.resize( 4 );
802 
803  aPath[0] = ClipperLib::IntPoint( -2, -2 );
804  aPath[1] = ClipperLib::IntPoint( 2, -2 );
805  aPath[2] = ClipperLib::IntPoint( 2, 2 );
806  aPath[3] = ClipperLib::IntPoint( -2, 2 );
807 
808  // It must be an outter polygon
809  wxASSERT( ClipperLib::Orientation( aPath ) );
810 
811  polygon_Convert( aPath, aSegments, 1.0f );
812 
813  wxASSERT( aPath.size() == aSegments.size() );
814 
815  wxASSERT( aSegments[0].m_Start == SFVEC2F( -2.0f, 2.0f ) );
816  wxASSERT( aSegments[1].m_Start == SFVEC2F( 2.0f, 2.0f ) );
817  wxASSERT( aSegments[2].m_Start == SFVEC2F( 2.0f, -2.0f ) );
818  wxASSERT( aSegments[3].m_Start == SFVEC2F( -2.0f, -2.0f ) );
819 
820  wxASSERT( polygon_IsPointInside( aSegments, SFVEC2F( 0.0f, 0.0f ) ) );
821  wxASSERT( polygon_IsPointInside( aSegments, SFVEC2F( -1.9f, -1.9f ) ) );
822  wxASSERT( polygon_IsPointInside( aSegments, SFVEC2F( -1.9f, 1.9f ) ) );
823  wxASSERT( polygon_IsPointInside( aSegments, SFVEC2F( 1.9f, 1.9f ) ) );
824  wxASSERT( polygon_IsPointInside( aSegments, SFVEC2F( 1.9f, -1.9f ) ) );
825 
826  wxASSERT( polygon_IsPointInside( aSegments, SFVEC2F( -2.1f, -2.0f ) ) == false );
827  wxASSERT( polygon_IsPointInside( aSegments, SFVEC2F( -2.1f, 2.0f ) ) == false );
828  wxASSERT( polygon_IsPointInside( aSegments, SFVEC2F( 2.1f, 2.0f ) ) == false );
829  wxASSERT( polygon_IsPointInside( aSegments, SFVEC2F( 2.1f, -2.0f ) ) == false );
830 }
831 #endif
std::vector< SHAPE_LINE_CHAIN > POLYGON
represents a single polygon outline with holes.
INTERSECTION_RESULT
Definition: cobject2d.h:38
bool Overlaps(const CBBOX2D &aBBox) const override
Function Overlaps.
Definition: cpolygon2d.cpp:250
SFVEC2F m_Precalc_slope
Definition: cpolygon2d.h:58
bool IsInitialized() const
Function IsInitialized check if this bounding box is already initialized.
Definition: cbbox2d.cpp:79
void Union(const SFVEC2F &aPoint)
Function Union recalculate the bounding box adding a point.
Definition: cbbox2d.cpp:95
void Polygon_Calc_BBox_3DU(const SHAPE_POLY_SET &aPolysList, CBBOX2D &aOutBBox, float aBiuTo3DunitsScale)
Definition: cpolygon2d.cpp:714
Class BOARD_ITEM is a base class for any item which can be embedded within the BOARD container class...
int PointCount() const
Function PointCount()
bool Intersect(const RAYSEG2D &aSegRay, float *aOutT, SFVEC2F *aNormalOut) const override
Function Intersect.
Definition: cpolygon2d.cpp:257
Class CBBOX manages a bounding box defined by two SFVEC2F min max points.
Definition: cbbox2d.h:40
int HoleCount(int aOutline) const
Returns the number of holes in a given outline
coord_type GetRight() const
Definition: box2.h:187
SHAPE_LINE_CHAIN & Hole(int aOutline, int aHole)
Returns the reference to aHole-th hole in the aIndex-th outline
INTERSECTION_RESULT IsBBoxInside(const CBBOX2D &aBBox) const override
Function IsBBoxInside.
Definition: cpolygon2d.cpp:267
bool IsPointInside(const SFVEC2F &aPoint) const override
Definition: cpolygon2d.cpp:274
int OutlineCount() const
Returns the number of outlines in the set
VECTOR2< int > VECTOR2I
Definition: vector2d.h:590
coord_type GetTop() const
Definition: box2.h:192
std::vector< POLYSEGMENT > SEGMENTS
Definition: cpolygon2d.h:63
bool Intersects(const CBBOX2D &aBBox) const
Function Intersects test if a bounding box intersects this box.
Definition: cbbox2d.cpp:213
void Reset()
Function Reset reset the bounding box to zero and de-initialized it.
Definition: cbbox2d.cpp:88
glm::uvec2 SFVEC2UI
Definition: xv3d_types.h:41
bool Intersect(const RAYSEG2D &aSegRay, float *aOutT, SFVEC2F *aNormalOut) const override
Function Intersect.
Definition: cpolygon2d.cpp:131
static void extractPathsFrom(const SEGMENTS_WIDTH_NORMALS &aSegList, const CBBOX2D &aBBox, SEGMENTS_WIDTH_NORMALS &aOutSegThatIntersect)
Definition: cpolygon2d.cpp:326
void SetClosed(bool aClosed)
Function SetClosed()
bool Overlaps(const CBBOX2D &aBBox) const override
Function Overlaps.
Definition: cpolygon2d.cpp:124
OUTERS_AND_HOLES m_outers_and_holes
A polygon block can have multiple polygon and holes.
Definition: cpolygon2d.h:97
glm::vec2 SFVEC2F
Definition: xv3d_types.h:45
bool IsPointInside(const SFVEC2F &aPoint) const override
Definition: cpolygon2d.cpp:197
INTERSECTION_RESULT IsBBoxInside(const CBBOX2D &aBBox) const override
Function IsBBoxInside.
Definition: cpolygon2d.cpp:190
Class SHAPE_POLY_SET.
SHAPE_LINE_CHAIN & Outline(int aIndex)
Returns the reference to aIndex-th outline in the set
coord_type GetBottom() const
Definition: box2.h:188
std::vector< SEGMENTS > m_Outers
Definition: cpolygon2d.h:77
void Set(const SFVEC2F &aPbMin, const SFVEC2F &aPbMax)
Function Set Set bounding box with new parameters.
Definition: cbbox2d.cpp:61
This structured will be used to handle a sub set of a polygon.
Definition: cpolygon2d.h:75
static bool intersect(const SEGMENT_WITH_NORMALS &aSeg, const SFVEC2F &aStart, const SFVEC2F &aEnd)
Definition: cpolygon2d.cpp:293
std::vector< SFVEC2F > KF_POINTS
Definition: cpolygon2d.cpp:288
void BooleanIntersection(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Performs boolean polyset intersection For aFastMode meaning, see function booleanOp ...
#define MAX_NR_DIVISIONS
Definition: cpolygon2d.cpp:290
static void polygon_Convert(const SHAPE_LINE_CHAIN &aPath, SEGMENTS &aOutSegment, float aBiuTo3DunitsScale)
Definition: cpolygon2d.cpp:377
std::vector< SEGMENTS > m_Holes
Definition: cpolygon2d.h:78
void ScaleNextUp()
Function ScaleNextUp scales a bounding box to the next float representation making it larger...
Definition: cbbox2d.cpp:164
CBBOX2D m_bbox
Definition: cobject2d.h:65
int AddOutline(const SHAPE_LINE_CHAIN &aOutline)
Adds a new outline to the set and returns its index
void Polygon2d_TestModule()
bpl::polygon_data< int > KI_POLYGON
KI_POLYGON defines a single polygon ( boost::polygon_data type.
Definition: polygons_defs.h:49
void Add(COBJECT2D *aObject)
Definition: ccontainer2d.h:51
SFVEC2F GetCenter() const
Function GetCenter return the center point of the bounding box.
Definition: cbbox2d.cpp:121
SFVEC2F m_Start
Definition: ray.h:88
void Polygon_Convert(const KI_POLYGON &aPolygon, ClipperLib::Path &aOutPath, CBBOX2D &aOutBBox, float aBiuTo3DunitsScale)
Definition: cpolygon2d.cpp:743
bool Intersects(const CBBOX2D &aBBox) const override
Function Intersects.
Definition: cpolygon2d.cpp:244
static bool polygon_IsPointInside(const SEGMENTS &aSegments, const SFVEC2F &aPoint)
Definition: cpolygon2d.cpp:41
CDUMMYBLOCK2D(const SFVEC2F &aPbMin, const SFVEC2F &aPbMax, const BOARD_ITEM &aBoardItem)
Definition: cpolygon2d.cpp:224
Class SHAPE_LINE_CHAIN.
SFVEC2F m_centroid
Definition: cobject2d.h:66
SEGMENTS_WIDTH_NORMALS m_open_segments
This is the outter part of the polygon.
Definition: cpolygon2d.h:94
CPOLYGONBLOCK2D(const SEGMENTS_WIDTH_NORMALS &aOpenSegmentList, const OUTERS_AND_HOLES &aOuter_and_holes, const BOARD_ITEM &aBoardItem)
Definition: cpolygon2d.cpp:73
bool Intersects(const CBBOX2D &aBBox) const override
Function Intersects.
Definition: cpolygon2d.cpp:114
const POLYGON & CPolygon(int aIndex) const
coord_type GetLeft() const
Definition: box2.h:191
bool Inside(const SFVEC2F &aPoint) const
Function Inside check is a point is inside this bounding box.
Definition: cbbox2d.cpp:225
bpl::point_data< int > KI_POLY_POINT
KI_POLY_POINT defines a point for boost::polygon.
Definition: polygons_defs.h:66
const SFVEC2F & Min() const
Function Min return the minimun vertex pointer.
Definition: cbbox2d.h:176
This dummy block will be defined by a 2d box size.
Definition: cpolygon2d.h:118
SFVEC2F GetExtent() const
Function GetExtent.
Definition: cbbox2d.cpp:127
const VECTOR2I & CPoint(int aIndex) const
Function CPoint()
const BOX2I BBox(int aClearance=0) const override
Function BBox()
SFVEC2F m_End_minus_start
Definition: ray.h:90
const SFVEC2F & Max() const
Function Max return the maximum vertex pointer.
Definition: cbbox2d.h:183
void Convert_path_polygon_to_polygon_blocks_and_dummy_blocks(const SHAPE_POLY_SET &aMainPath, CGENERICCONTAINER2D &aDstContainer, float aBiuTo3DunitsScale, float aDivFactor, const BOARD_ITEM &aBoardItem)
Convert_path_polygon_to_polygon_blocks_and_dummy_blocks This function will use a polygon in the forma...
Definition: cpolygon2d.cpp:406
std::vector< SEGMENT_WITH_NORMALS > SEGMENTS_WIDTH_NORMALS
This list will be used to test ray2d intersections.
Definition: cpolygon2d.h:68
This class represents a sub polygon block.
Definition: cpolygon2d.h:87
Definition: ray.h:86