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