geometry_utils.h File Reference

a few functions useful in geometry calculations. More...

#include <math.h>
#include <stdlib.h>
#include <math/vector2d.h>

Go to the source code of this file.

Classes
class	DISABLE_ARC_RADIUS_CORRECTION
	When creating polygons to create a clearance polygonal area, the polygon must be same or bigger than the original shape. More...

Macros
#define	DOT_WIDTH_MILS   0.0254
	Dashed and dotted line patterns. More...
#define	DOT_MARK_LEN(aLineWidth)   ( std::max( 1.0, IU_PER_MILS * DOT_WIDTH_MILS - aLineWidth ) )
#define	DASH_GAP_LEN(aLineWidth)   ( 3.0 * DOT_MARK_LEN( aLineWidth ) + ( 2.0 * aLineWidth ) )
#define	DASH_MARK_LEN(aLineWidth)   ( std::max( DASH_GAP_LEN( aLineWidth ), 5.0 * DOT_MARK_LEN( aLineWidth ) ) )

Enumerations
enum	ERROR_LOC { ERROR_OUTSIDE, ERROR_INSIDE }
	When approximating an arc or circle, should the error be placed on the outside or inside of the curve? (Generally speaking filled shape errors go on the inside and knockout errors go on the outside. More...

Functions
int	GetArcToSegmentCount (int aRadius, int aErrorMax, double aArcAngleDegree)
int	CircleToEndSegmentDeltaRadius (int aInnerCircleRadius, int aSegCount)
int	GetCircleToPolyCorrection (int aMaxError)
template<typename T >
VECTOR2< T >	GetVectorSnapped45 (const VECTOR2< T > &aVec, bool only45=false)
	Snap a vector onto the nearest 0, 45 or 90 degree line. More...
bool	ClipLine (const EDA_RECT *aClipBox, int &x1, int &y1, int &x2, int &y2)
	Test if any part of a line falls within the bounds of a rectangle. More...

Detailed Description

a few functions useful in geometry calculations.

Definition in file geometry_utils.h.

Macro Definition Documentation

DASH_GAP_LEN

#define DASH_GAP_LEN

(

aLineWidth

)

( 3.0 * DOT_MARK_LEN( aLineWidth ) + ( 2.0 * aLineWidth ) )

Definition at line 164 of file geometry_utils.h.

DASH_MARK_LEN

#define DASH_MARK_LEN

(

aLineWidth

)

( std::max( DASH_GAP_LEN( aLineWidth ), 5.0 * DOT_MARK_LEN( aLineWidth ) ) )

Definition at line 167 of file geometry_utils.h.

DOT_MARK_LEN

#define DOT_MARK_LEN

(

aLineWidth

)

( std::max( 1.0, IU_PER_MILS * DOT_WIDTH_MILS - aLineWidth ) )

Definition at line 161 of file geometry_utils.h.

DOT_WIDTH_MILS

#define DOT_WIDTH_MILS   0.0254

Dashed and dotted line patterns.

Note: these are all macros because they're included from files with different IU definitions.

Definition at line 159 of file geometry_utils.h.

Enumeration Type Documentation

ERROR_LOC

enum ERROR_LOC

When approximating an arc or circle, should the error be placed on the outside or inside of the curve? (Generally speaking filled shape errors go on the inside and knockout errors go on the outside.

This preserves minimum clearances.)

Enumerator
ERROR_OUTSIDE
ERROR_INSIDE

Definition at line 45 of file geometry_utils.h.

{ ERROR_OUTSIDE, ERROR_INSIDE };

Function Documentation

CircleToEndSegmentDeltaRadius()

int CircleToEndSegmentDeltaRadius	(	int	aInnerCircleRadius,
		int	aSegCount
	)

Returns

the radius diffence of the circle defined by segments inside the circle and the radius of the circle tangent to the middle of segments (defined by segments outside this circle)

Parameters

aInnerCircleRadius	is the radius of the circle tangent to the middle of segments
aSegCount	is the seg count to approximate the circle

Definition at line 67 of file geometry_utils.cpp.

{
    // The minimal seg count is 3, otherwise we cannot calculate the result
    // in practice, the min count is clamped to 8 in kicad
    if( aSegCount <= 2 )
        aSegCount = 3;

    // The angle between the center of the segment and one end of the segment
    // when the circle is approximated by aSegCount segments
    double alpha = M_PI / aSegCount;

    // aRadius is the radius of the circle tangent to the middle of each segment
    // and aRadius/cos(aplha) is the radius of the circle defined by seg ends
    int delta = KiROUND( aRadius * ( 1/cos(alpha) - 1 ) );

    return delta;
}

References delta, and KiROUND().

Referenced by ConvertArcToPolyline(), SHAPE_ARC::ConvertToPolyline(), CornerListToPolygon(), TransformArcToPolygon(), TransformCircleToPolygon(), TransformOvalToPolygon(), and PAD::TransformShapeWithClearanceToPolygon().

ClipLine()

bool ClipLine	(	const EDA_RECT *	aClipBox,
		int &	x1,
		int &	y1,
		int &	x2,
		int &	y2
	)

Test if any part of a line falls within the bounds of a rectangle.

Please note that this is only accurate for lines that are one pixel wide.

Parameters

aClipBox	- The rectangle to test.
x1	- X coordinate of one end of a line.
y1	- Y coordinate of one end of a line.
x2	- X coordinate of the other end of a line.
y2	- Y coordinate of the other end of a line.

Returns

- False if any part of the line lies within the rectangle.

Definition at line 137 of file geometry_utils.cpp.

{
    // Stock Cohen-Sutherland algorithm; check *any* CG book for details
    int outcode1 = clipOutCode( aClipBox, x1, y1 );
    int outcode2 = clipOutCode( aClipBox, x2, y2 );

    while( outcode1 || outcode2 )
    {
        // Fast reject
        if( outcode1 & outcode2 )
            return true;

        // Choose a side to clip
        int thisoutcode, x, y;

        if( outcode1 )
            thisoutcode = outcode1;
        else
            thisoutcode = outcode2;

        /* One clip round
         * Since we use the full range of 32 bit ints, the proportion
         * computation has to be done in 64 bits to avoid horrible
         * results */
        if( thisoutcode & 1 ) // Clip the bottom
        {
            y = aClipBox->GetBottom();
            x = x1 + (x2 - x1) * std::int64_t(y - y1) / (y2 - y1);
        }
        else if( thisoutcode & 2 ) // Clip the top
        {
            y = aClipBox->GetY();
            x = x1 + ( x2 - x1 ) * std::int64_t( y - y1 ) / ( y2 - y1 );
        }
        else if( thisoutcode & 8 ) // Clip the right
        {
            x = aClipBox->GetRight();
            y = y1 + ( y2 - y1 ) * std::int64_t( x - x1 ) / ( x2 - x1 );
        }
        else // if( thisoutcode & 4), obviously, clip the left
        {
            x = aClipBox->GetX();
            y = y1 + ( y2 - y1 ) * std::int64_t( x - x1 ) / ( x2 - x1 );
        }

        // Put the result back and update the boundary code
        // No ambiguity, otherwise it would have been a fast reject
        if( thisoutcode == outcode1 )
        {
            x1 = x;
            y1 = y;
            outcode1 = clipOutCode( aClipBox, x1, y1 );
        }
        else
        {
            x2 = x;
            y2 = y;
            outcode2 = clipOutCode( aClipBox, x2, y2 );
        }
    }
    return false;
}

References clipOutCode(), EDA_RECT::GetBottom(), EDA_RECT::GetRight(), EDA_RECT::GetX(), and EDA_RECT::GetY().

Referenced by KIGFX::SCH_PAINTER::draw(), GRCSegm(), GRLineArray(), SCH_BUS_ENTRY_BASE::Print(), SCH_LINE::Print(), KIGFX::ORIGIN_VIEWITEM::ViewDraw(), and WinClipAndDrawLine().

GetArcToSegmentCount()

int GetArcToSegmentCount	(	int	aRadius,
		int	aErrorMax,
		double	aArcAngleDegree
	)

Returns

the number of segments to approximate a arc by segments with a given max error (this number is >= 1)

Parameters

aRadius	is the radius od the circle or arc
aErrorMax	is the max error This is the max distance between the middle of a segment and the circle.
aArcAngleDegree	is the arc angle in degrees

Definition at line 43 of file geometry_utils.cpp.

{
    // calculate the number of segments to approximate a circle by segments
    // given the max distance between the middle of a segment and the circle

    // avoid divide-by-zero
    aRadius = std::max( 1, aRadius );

    // error relative to the radius value:
    double rel_error = (double)aErrorMax / aRadius;
    // minimal arc increment in degrees:
    double arc_increment = 180 / M_PI * acos( 1.0 - rel_error ) * 2;

    // Ensure a minimal arc increment reasonable value for a circle
    // (360.0 degrees). For very small radius values, this is mandatory.
    arc_increment = std::min( 360.0/MIN_SEGCOUNT_FOR_CIRCLE, arc_increment );

    int segCount = KiROUND( fabs( aArcAngleDegree ) / arc_increment );

    // Ensure at least two segments are used for algorithmic safety
    return std::max( segCount, 2 );
}

References KiROUND(), and MIN_SEGCOUNT_FOR_CIRCLE.

Referenced by SHAPE_POLY_SET::chamferFilletPolygon(), ZONE_FILLER::computeRawFilledArea(), ConvertArcToPolyline(), ConvertOutlineToPolygon(), SHAPE_ARC::ConvertToPolyline(), CornerListToPolygon(), BOARD_ADAPTER::createTrack(), KIGFX::PCB_PAINTER::draw(), KIGFX::OPENGL_GAL::DrawArcSegment(), EXPORTER_PCB_VRML::ExportVrmlPadHole(), EXPORTER_PCB_VRML::ExportVrmlViaHoles(), ZONE_FILLER::fillSingleZone(), gen_arc(), BOARD_ADAPTER::GetCircleSegmentCount(), EAGLE_PLUGIN::loadPolygon(), EAGLE_PLUGIN::loadSignals(), EAGLE_PLUGIN::packagePolygon(), PlotSolderMaskLayer(), PlotStandardLayer(), TransformCircleToPolygon(), TransformOvalToPolygon(), PAD::TransformShapeWithClearanceToPolygon(), ZONE::TransformShapeWithClearanceToPolygon(), ZONE::TransformSmoothedOutlineToPolygon(), and ZONE::TransformSolidAreasShapesToPolygon().

GetCircleToPolyCorrection()

int GetCircleToPolyCorrection

(

int

aMaxError

)

Returns

the radius correction to approximate a circle.

Parameters

aMaxError

is the same error value used to calculate the number of segments.

When creating a polygon from a circle, the polygon is inside the circle. Only corners are on the circle. This is incorrect when building clearance areas of circles, that need to build the equivalent polygon outside the circle.

Definition at line 106 of file geometry_utils.cpp.

{
    // Push all the error to the outside by increasing the radius
    return s_disable_arc_correction ? 0 : aMaxError;
}

References s_disable_arc_correction.

Referenced by CornerListToPolygon(), TransformCircleToPolygon(), TransformOvalToPolygon(), and PAD::TransformShapeWithClearanceToPolygon().

GetVectorSnapped45()

template<typename T >

VECTOR2<T> GetVectorSnapped45	(	const VECTOR2< T > &	aVec,
		bool	only45 = false
	)

Snap a vector onto the nearest 0, 45 or 90 degree line.

The magnitude of the vector is NOT kept, instead the coordinates are set equal (and/or opposite) or to zero as needed. The effect of this is that if the starting vector is on a square grid, the resulting snapped vector will still be on the same grid.

Parameters

a	vector to be snapped

Returns

the snapped vector

Definition at line 107 of file geometry_utils.h.

{
    auto newVec = aVec;
    const VECTOR2<T> absVec { std::abs( aVec.x ), std::abs( aVec.y ) };

    if ( !only45 && absVec.x > absVec.y * 2 )
    {
        // snap along x-axis
        newVec.y = 0;
    }
    else if ( !only45 && absVec.y > absVec.x * 2 )
    {
        // snap onto y-axis
        newVec.x = 0;
    }
    else if ( absVec.x > absVec.y )
    {
        // snap away from x-axis towards 45
        newVec.y = std::copysign( aVec.x, aVec.y );
    } else
    {
        // snap away from y-axis towards 45
        newVec.x = std::copysign( aVec.y, aVec.x );
    }

    return newVec;
}

References VECTOR2< T >::x, and VECTOR2< T >::y.

Referenced by EC_45DEGREE::Apply(), DRAWING_TOOL::constrainDimension(), EDIT_TOOL::doMoveSelection(), DRAWING_TOOL::DrawDimension(), DRAWING_TOOL::drawSegment(), KIGFX::PREVIEW::TWO_POINT_GEOMETRY_MANAGER::SetEnd(), and POLYGON_GEOM_MANAGER::updateLeaderPoints().