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