KiCad PCB EDA Suite
POLYGON_2D Class Reference

Represent a sub polygon block. More...

#include <polygon_2d.h>

Inheritance diagram for POLYGON_2D:
OBJECT_2D

Public Member Functions

 POLYGON_2D (const SEGMENTS_WIDTH_NORMALS &aOpenSegmentList, const OUTERS_AND_HOLES &aOuterAndHoles, const BOARD_ITEM &aBoardItem)
 
bool Overlaps (const BBOX_2D &aBBox) const override
 Test if the box overlaps the object. More...
 
bool Intersects (const BBOX_2D &aBBox) const override
 a.Intersects(b) ⇔ !a.Disjoint(b) ⇔ !(a ∩ b = ∅) More...
 
bool Intersect (const RAYSEG2D &aSegRay, float *aOutT, SFVEC2F *aNormalOut) const override
 
INTERSECTION_RESULT IsBBoxInside (const BBOX_2D &aBBox) const override
 Test this object if it's completely outside, intersects, or is completely inside aBBox. More...
 
bool IsPointInside (const SFVEC2F &aPoint) const override
 
const BOARD_ITEMGetBoardItem () const
 
const BBOX_2DGetBBox () const
 
const SFVEC2FGetCentroid () const
 
OBJECT_2D_TYPE GetObjectType () const
 

Protected Attributes

BBOX_2D m_bbox
 
SFVEC2F m_centroid
 
OBJECT_2D_TYPE m_obj_type
 
const BOARD_ITEMm_boardItem
 

Private Attributes

SEGMENTS_WIDTH_NORMALS m_open_segments
 The outer part of the polygon. More...
 
OUTERS_AND_HOLES m_outers_and_holes
 

Detailed Description

Represent a sub polygon block.

This polygon block was created from a general polygon definition that was sub divided and to create blocks of polygons. This polygon class represent a sub part of that main polygon. There is information for the contours (used to test the ray2d intersection) and a close definition of the block polygon to test if a point is inside.

Definition at line 93 of file polygon_2d.h.

Constructor & Destructor Documentation

◆ POLYGON_2D()

POLYGON_2D::POLYGON_2D ( const SEGMENTS_WIDTH_NORMALS aOpenSegmentList,
const OUTERS_AND_HOLES aOuterAndHoles,
const BOARD_ITEM aBoardItem 
)

Definition at line 64 of file polygon_2d.cpp.

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 }
BBOX_2D m_bbox
Definition: object_2d.h:110
OUTERS_AND_HOLES m_outers_and_holes
Definition: polygon_2d.h:115
SFVEC2F GetCenter() const
Definition: bbox_2d.cpp:119
SFVEC2F m_centroid
Definition: object_2d.h:111
OBJECT_2D(OBJECT_2D_TYPE aObjType, const BOARD_ITEM &aBoardItem)
Definition: object_2d.cpp:36
void Reset()
Reset the bounding box to zero and uninitialize it.
Definition: bbox_2d.cpp:86
std::vector< SEGMENTS > m_Outers
Definition: polygon_2d.h:80
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
std::vector< POLYSEGMENT > SEGMENTS
Definition: polygon_2d.h:61
void ScaleNextUp()
Scale a bounding box to the next float representation making it larger.
Definition: bbox_2d.cpp:162
SEGMENTS_WIDTH_NORMALS m_open_segments
The outer part of the polygon.
Definition: polygon_2d.h:112
bool IsInitialized() const
Check if this bounding box is already initialized.
Definition: bbox_2d.cpp:79

References BBOX_2D::GetCenter(), BBOX_2D::IsInitialized(), OBJECT_2D::m_bbox, OBJECT_2D::m_centroid, OUTERS_AND_HOLES::m_Holes, m_open_segments, OUTERS_AND_HOLES::m_Outers, m_outers_and_holes, POLYGON, BBOX_2D::Reset(), BBOX_2D::ScaleNextUp(), and BBOX_2D::Union().

Member Function Documentation

◆ GetBBox()

◆ GetBoardItem()

const BOARD_ITEM& OBJECT_2D::GetBoardItem ( ) const
inlineinherited

Definition at line 66 of file object_2d.h.

66 { return m_boardItem; }
const BOARD_ITEM & m_boardItem
Definition: object_2d.h:114

References OBJECT_2D::m_boardItem.

Referenced by RENDER_3D_RAYTRACE::createItemsFromContainer().

◆ GetCentroid()

const SFVEC2F& OBJECT_2D::GetCentroid ( ) const
inlineinherited

Definition at line 105 of file object_2d.h.

105 { return m_centroid; }
SFVEC2F m_centroid
Definition: object_2d.h:111

References OBJECT_2D::m_centroid.

Referenced by LAYER_ITEM::LAYER_ITEM(), sortByCentroidX(), sortByCentroidY(), and sortByCentroidZ().

◆ GetObjectType()

◆ Intersect()

bool POLYGON_2D::Intersect ( const RAYSEG2D aSegRay,
float *  aOutT,
SFVEC2F aNormalOut 
) const
overridevirtual
Parameters
aOutTa value between 0.0 and 1.0 in relation to the time of the hit of the segment.

Implements OBJECT_2D.

Definition at line 120 of file polygon_2d.cpp.

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 }
glm::vec2 SFVEC2F
Definition: xv3d_types.h:42
SFVEC2F m_Start
Definition: ray.h:107
SEGMENTS_WIDTH_NORMALS m_open_segments
The outer part of the polygon.
Definition: polygon_2d.h:112
SFVEC2F m_End_minus_start
Definition: ray.h:109

References RAYSEG2D::m_End_minus_start, m_open_segments, and RAYSEG2D::m_Start.

◆ Intersects()

bool POLYGON_2D::Intersects ( const BBOX_2D aBBox) const
overridevirtual

a.Intersects(b) ⇔ !a.Disjoint(b) ⇔ !(a ∩ b = ∅)

Implements OBJECT_2D.

Definition at line 103 of file polygon_2d.cpp.

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 }
BBOX_2D m_bbox
Definition: object_2d.h:110
bool Intersects(const BBOX_2D &aBBox) const
Test if a bounding box intersects this box.
Definition: bbox_2d.cpp:211

References BBOX_2D::Intersects(), and OBJECT_2D::m_bbox.

◆ IsBBoxInside()

INTERSECTION_RESULT POLYGON_2D::IsBBoxInside ( const BBOX_2D aBBox) const
overridevirtual

Test this object if it's completely outside, intersects, or is completely inside aBBox.

Returns
INTERSECTION_RESULT

Implements OBJECT_2D.

Definition at line 179 of file polygon_2d.cpp.

180 {
181 
183 }

References MISSES.

◆ IsPointInside()

bool POLYGON_2D::IsPointInside ( const SFVEC2F aPoint) const
overridevirtual

Implements OBJECT_2D.

Definition at line 186 of file polygon_2d.cpp.

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 }
OUTERS_AND_HOLES m_outers_and_holes
Definition: polygon_2d.h:115
static bool polygon_IsPointInside(const SEGMENTS &aSegments, const SFVEC2F &aPoint)
Definition: polygon_2d.cpp:34
std::vector< SEGMENTS > m_Outers
Definition: polygon_2d.h:80
std::vector< SEGMENTS > m_Holes
Definition: polygon_2d.h:81

References OUTERS_AND_HOLES::m_Holes, OUTERS_AND_HOLES::m_Outers, m_outers_and_holes, and polygon_IsPointInside().

◆ Overlaps()

bool POLYGON_2D::Overlaps ( const BBOX_2D aBBox) const
overridevirtual

Test if the box overlaps the object.

Conformance Implements the Overlaps function from the OGC Simple Feature Specification at http://www.opengeospatial.org/standards/sfa. a.Overlaps(b) ⇔ ( dim(I(a)) = dim(I(b)) = dim(I(a)I(b))) ∧ (a ∩ b ≠ a) ∧ (a ∩ b ≠ b) It means that the result dimension of an overlap is the same dimensions of the bounding box (so the overlap cannot be a point or a line) and one of the boxes cannot full contain the other box.

Parameters
aBBoxis the bounding box to test.
Returns
true if the BBox intersects the object or is inside it.

Implements OBJECT_2D.

Definition at line 113 of file polygon_2d.cpp.

114 {
115  // NOT IMPLEMENTED, why?
116  return false;
117 }

Member Data Documentation

◆ m_bbox

◆ m_boardItem

const BOARD_ITEM& OBJECT_2D::m_boardItem
protectedinherited

Definition at line 114 of file object_2d.h.

Referenced by OBJECT_2D::GetBoardItem().

◆ m_centroid

◆ m_obj_type

OBJECT_2D_TYPE OBJECT_2D::m_obj_type
protectedinherited

Definition at line 112 of file object_2d.h.

Referenced by OBJECT_2D::GetObjectType(), and OBJECT_2D::OBJECT_2D().

◆ m_open_segments

SEGMENTS_WIDTH_NORMALS POLYGON_2D::m_open_segments
private

The outer part of the polygon.

This list is used to test a ray intersection with the boundaries of this sub polygon. It contains also the interpolated normals that are passed from the main polygon.A polygon block can have multiple polygon and holes

Definition at line 112 of file polygon_2d.h.

Referenced by Intersect(), and POLYGON_2D().

◆ m_outers_and_holes

OUTERS_AND_HOLES POLYGON_2D::m_outers_and_holes
private

Definition at line 115 of file polygon_2d.h.

Referenced by IsPointInside(), and POLYGON_2D().


The documentation for this class was generated from the following files: