trigo.cpp File Reference

Trigonometric and geometric basic functions. More...

#include <limits>
#include <stdlib.h>
#include <type_traits>
#include <geometry/seg.h>
#include <math/util.h>
#include <math/vector2d.h>
#include <trigo.h>

Go to the source code of this file.

Functions
bool	IsPointOnSegment (const wxPoint &aSegStart, const wxPoint &aSegEnd, const wxPoint &aTestPoint)
	Test if aTestPoint is on line defined by aSegStart and aSegEnd. More...
bool	SegmentIntersectsSegment (const wxPoint &a_p1_l1, const wxPoint &a_p2_l1, const wxPoint &a_p1_l2, const wxPoint &a_p2_l2, wxPoint *aIntersectionPoint)
	Test if two lines intersect. More...
bool	TestSegmentHit (const wxPoint &aRefPoint, const wxPoint &aStart, const wxPoint &aEnd, int aDist)
	Test if aRefPoint is with aDistance on the line defined by aStart and aEnd. More...
const VECTOR2I	CalcArcMid (const VECTOR2I &aStart, const VECTOR2I &aEnd, const VECTOR2I &aCenter, bool aMinArcAngle)
	Return the middle point of an arc, half-way between aStart and aEnd. More...
double	ArcTangente (int dy, int dx)
void	RotatePoint (int *pX, int *pY, double angle)
void	RotatePoint (int *pX, int *pY, int cx, int cy, double angle)
void	RotatePoint (wxPoint *point, const wxPoint &centre, double angle)
void	RotatePoint (VECTOR2I &point, const VECTOR2I &centre, double angle)
void	RotatePoint (double *pX, double *pY, double cx, double cy, double angle)
void	RotatePoint (double *pX, double *pY, double angle)
const VECTOR2D	CalcArcCenter (const VECTOR2D &aStart, const VECTOR2D &aEnd, double aAngle)
const VECTOR2D	CalcArcCenter (const VECTOR2D &aStart, const VECTOR2D &aMid, const VECTOR2D &aEnd)
const VECTOR2I	CalcArcCenter (const VECTOR2I &aStart, const VECTOR2I &aMid, const VECTOR2I &aEnd)
	Determine the center of an arc or circle given three points on its circumference. More...
const wxPoint	CalcArcCenter (const wxPoint &aStart, const wxPoint &aMid, const wxPoint &aEnd)
double	CalcArcAngle (const VECTOR2I &aStart, const VECTOR2I &aMid, const VECTOR2I &aEnd)
	Return the subtended angle for a given arc. More...

Detailed Description

Trigonometric and geometric basic functions.

Definition in file trigo.cpp.

Function Documentation

ArcTangente()

double ArcTangente	(	int	dy,
		int	dx
	)

Definition at line 183 of file trigo.cpp.

{

 /* gcc is surprisingly smart in optimizing these conditions in
 a tree! */

 if( dx == 0 && dy == 0 )
 return 0;

 if( dy == 0 )
 {
 if( dx >= 0 )
 return 0;
 else
 return -1800;
 }

 if( dx == 0 )
 {
 if( dy >= 0 )
 return 900;
 else
 return -900;
 }

 if( dx == dy )
 {
 if( dx >= 0 )
 return 450;
 else
 return -1800 + 450;
 }

 if( dx == -dy )
 {
 if( dx >= 0 )
 return -450;
 else
 return 1800 - 450;
 }

 // Of course dy and dx are treated as double
 return RAD2DECIDEG( std::atan2( (double) dy, (double) dx ) );
}

References RAD2DECIDEG().

Referenced by BuildCornersList_S_Shape(), LIB_SHAPE::CalcArcAngles(), CalcArcMid(), EDA_SHAPE::calcEdit(), EDA_SHAPE::computeArcBBox(), AM_PRIMITIVE::ConvertShapeToPolygon(), AR_MATRIX::drawSegmentQcq(), fillArcPOLY(), PCB_ARC::GetAngle(), SCH_LINE::GetAngleFrom(), PCB_ARC::GetArcAngleEnd(), PCB_ARC::GetArcAngleStart(), SHAPE_ARC::GetCentralAngle(), CADSTAR_SCH_ARCHIVE_LOADER::getPolarAngle(), CADSTAR_PCB_ARCHIVE_LOADER::getPolarAngle(), SCH_LINE::GetReverseAngleFrom(), GRCSegm(), PCB_ARC::HitTest(), DSN::SPECCTRA_DB::makeIMAGE(), PCAD2KICAD::PCB_ARC::Parse(), BRDITEMS_PLOTTER::PlotFootprintGraphicItem(), BRDITEMS_PLOTTER::PlotPcbShape(), PLOTTER::segmentAsOval(), SHAPE_ARC::SHAPE_ARC(), and AR_MATRIX::traceArc().

CalcArcAngle()

double CalcArcAngle	(	const VECTOR2I &	aStart,
		const VECTOR2I &	aMid,
		const VECTOR2I &	aEnd
	)

Return the subtended angle for a given arc.

Definition at line 567 of file trigo.cpp.

{
 VECTOR2I center = CalcArcCenter( aStart, aMid, aEnd );

 // Check if the new arc is CW or CCW
 VECTOR2D startLine = aStart - center;
 VECTOR2D endLine = aEnd - center;
 double angle = RAD2DECIDEG( endLine.Angle() - startLine.Angle() );

 VECTOR2D v1, v2;
 v1 = aStart - aMid;
 v2 = aEnd - aMid;
 double theta = RAD2DECIDEG( v1.Angle() );

 RotatePoint( &( v1.x ), &( v1.y ), theta );
 RotatePoint( &( v2.x ), &( v2.y ), theta );

 bool clockwise = ( ( v1.Angle() - v2.Angle() ) > 0 );

 // Normalize the angle
 if( clockwise && angle < 0.0 )
 angle += 3600.0;
 else if( !clockwise && angle > 0.0 )
 angle -= 3600.0;

 return angle;
}

References PNS::angle(), VECTOR2< T >::Angle(), CalcArcCenter(), RAD2DECIDEG(), RotatePoint(), v2, VECTOR2< T >::x, and VECTOR2< T >::y.

CalcArcCenter() [1/4]

const VECTOR2D CalcArcCenter	(	const VECTOR2D &	aStart,
		const VECTOR2D &	aEnd,
		double	aAngle
	)

Definition at line 362 of file trigo.cpp.

{
 VECTOR2D start = aStart;
 VECTOR2D end = aEnd;

 if( aAngle < 0 )
 {
 std::swap( start, end );
  aAngle = abs( aAngle );
 }

 if( aAngle > 180 )
 {
 std::swap( start, end );
 aAngle = 360 - aAngle;
 }

 double chord = ( start - end ).EuclideanNorm();
 double r = chord / ( 2.0 * sin( ( aAngle / 2.0 ) * M_PI / 180.0 ) );

 VECTOR2D vec = end - start;
 vec = vec.Resize( r );
 vec = vec.Rotate( ( 90.0 - aAngle / 2.0 ) * M_PI / 180.0 );

 return start + vec;
}

References EuclideanNorm(), r, VECTOR2< T >::Resize(), and VECTOR2< T >::Rotate().

Referenced by CalcArcAngle(), and CalcArcCenter().

CalcArcCenter() [2/4]

const VECTOR2D CalcArcCenter	(	const VECTOR2D &	aStart,
		const VECTOR2D &	aMid,
		const VECTOR2D &	aEnd
	)

Definition at line 390 of file trigo.cpp.

{
 VECTOR2D center;
 double yDelta_21 = aMid.y - aStart.y;
 double xDelta_21 = aMid.x - aStart.x;
 double yDelta_32 = aEnd.y - aMid.y;
 double xDelta_32 = aEnd.x - aMid.x;

 // This is a special case for aMid as the half-way point when aSlope = 0 and bSlope = inf
 // or the other way around. In that case, the center lies in a straight line between
 // aStart and aEnd
 if( ( ( xDelta_21 == 0.0 ) && ( yDelta_32 == 0.0 ) ) ||
 ( ( yDelta_21 == 0.0 ) && ( xDelta_32 == 0.0 ) ) )
 {
 center.x = ( aStart.x + aEnd.x ) / 2.0;
 center.y = ( aStart.y + aEnd.y ) / 2.0 ;
 return center;
 }

 // Prevent div=0 errors
 if( xDelta_21 == 0.0 )
 xDelta_21 = std::numeric_limits<double>::epsilon();

 if( xDelta_32 == 0.0 )
 xDelta_32 = -std::numeric_limits<double>::epsilon();

 double aSlope = yDelta_21 / xDelta_21;
 double bSlope = yDelta_32 / xDelta_32;

 double daSlope = aSlope * VECTOR2D( 0.5 / yDelta_21, 0.5 / xDelta_21 ).EuclideanNorm();
 double dbSlope = bSlope * VECTOR2D( 0.5 / yDelta_32, 0.5 / xDelta_32 ).EuclideanNorm();

 if( aSlope == bSlope )
 {
 if( aStart == aEnd )
 {
 // This is a special case for a 360 degrees arc. In this case, the center is halfway between
 // the midpoint and either end point
 center.x = ( aStart.x + aMid.x ) / 2.0;
 center.y = ( aStart.y + aMid.y ) / 2.0 ;
 return center;
 }
 else
 {
 // If the points are colinear, the center is at infinity, so offset
 // the slope by a minimal amount
 // Warning: This will induce a small error in the center location
 aSlope += std::numeric_limits<double>::epsilon();
 bSlope -= std::numeric_limits<double>::epsilon();
 }
 }

 // Prevent divide by zero error
 if( aSlope == 0.0 )
 aSlope = std::numeric_limits<double>::epsilon();

 // What follows is the calculation of the center using the slope of the two lines as well as
 // the propagated error that occurs when rounding to the nearest nanometer. The error can be
 // ±0.5 units but can add up to multiple nanometers after the full calculation is performed.
 // All variables starting with `d` are the delta of that variable. This is approximately equal
 // to the standard deviation.
 // We ignore the possible covariance between variables. We also truncate our series expansion
 // at the first term. These are reasonable assumptions as the worst-case scenario is that we
 // underestimate the potential uncertainty, which would potentially put us back at the status quo
 double abSlopeStartEndY = aSlope * bSlope * ( aStart.y - aEnd.y );
 double dabSlopeStartEndY = abSlopeStartEndY * std::sqrt( ( daSlope / aSlope * daSlope / aSlope )
 + ( dbSlope / bSlope * dbSlope / bSlope )
 + ( M_SQRT1_2 / ( aStart.y - aEnd.y )
 * M_SQRT1_2 / ( aStart.y - aEnd.y ) ) );

 double bSlopeStartMidX = bSlope * ( aStart.x + aMid.x );
 double dbSlopeStartMidX = bSlopeStartMidX * std::sqrt( ( dbSlope / bSlope * dbSlope / bSlope )
 + ( M_SQRT1_2 / ( aStart.x + aMid.x )
 * M_SQRT1_2 / ( aStart.x + aMid.x ) ) );

 double aSlopeMidEndX = aSlope * ( aMid.x + aEnd.x );
 double daSlopeMidEndX = aSlopeMidEndX * std::sqrt( ( daSlope / aSlope * daSlope / aSlope )
 + ( M_SQRT1_2 / ( aMid.x + aEnd.x )
 * M_SQRT1_2 / ( aMid.x + aEnd.x ) ) );

 double twiceBASlopeDiff = 2 * ( bSlope - aSlope );
 double dtwiceBASlopeDiff = 2 * std::sqrt( dbSlope * dbSlope + daSlope * daSlope );

 double centerNumeratorX = abSlopeStartEndY + bSlopeStartMidX - aSlopeMidEndX;
 double dCenterNumeratorX = std::sqrt( dabSlopeStartEndY * dabSlopeStartEndY
 + dbSlopeStartMidX * dbSlopeStartMidX
 + daSlopeMidEndX * daSlopeMidEndX );

 double centerX = ( abSlopeStartEndY + bSlopeStartMidX - aSlopeMidEndX ) / twiceBASlopeDiff;

 double dCenterX = centerX * std::sqrt( ( dCenterNumeratorX / centerNumeratorX * dCenterNumeratorX / centerNumeratorX )
 + ( dtwiceBASlopeDiff / twiceBASlopeDiff * dtwiceBASlopeDiff / twiceBASlopeDiff ) );


 double centerNumeratorY = ( ( aStart.x + aMid.x ) / 2.0 - centerX );
 double dCenterNumeratorY = std::sqrt( 1.0 / 8.0 + dCenterX * dCenterX );

 double centerFirstTerm = centerNumeratorY / aSlope;
 double dcenterFirstTermY = centerFirstTerm * std::sqrt(
 ( dCenterNumeratorY/ centerNumeratorY * dCenterNumeratorY / centerNumeratorY )
 + ( daSlope / aSlope * daSlope / aSlope ) );

 double centerY = centerFirstTerm + ( aStart.y + aMid.y ) / 2.0;
 double dCenterY = std::sqrt( dcenterFirstTermY * dcenterFirstTermY + 1.0 / 8.0 );

 double rounded100CenterX = std::floor( ( centerX + 50.0 ) / 100.0 ) * 100.0;
 double rounded100CenterY = std::floor( ( centerY + 50.0 ) / 100.0 ) * 100.0;
 double rounded10CenterX = std::floor( ( centerX + 5.0 ) / 10.0 ) * 10.0;
 double rounded10CenterY = std::floor( ( centerY + 5.0 ) / 10.0 ) * 10.0;

 // The last step is to find the nice, round numbers near our baseline estimate and see if they are within our uncertainty
 // range. If they are, then we use this round value as the true value. This is justified because ALL values within the
 // uncertainty range are equally true. Using a round number will make sure that we are on a multiple of 1mil or 100nm
 // when calculating centers.
 if( std::abs( rounded100CenterX - centerX ) < dCenterX && std::abs( rounded100CenterY - centerY ) < dCenterY )
 {
 center.x = rounded100CenterX;
 center.y = rounded100CenterY;
 }
 else if( std::abs( rounded10CenterX - centerX ) < dCenterX && std::abs( rounded10CenterY - centerY ) < dCenterY )
 {
 center.x = rounded10CenterX;
 center.y = rounded10CenterY;
 }
 else
 {
 center.x = centerX;
 center.y = centerY;
 }


 return center;
}

References VECTOR2< T >::EuclideanNorm(), VECTOR2< T >::x, and VECTOR2< T >::y.

CalcArcCenter() [3/4]

const VECTOR2I CalcArcCenter	(	const VECTOR2I &	aStart,
		const VECTOR2I &	aMid,
		const VECTOR2I &	aEnd
	)

Determine the center of an arc or circle given three points on its circumference.

Parameters

aStart	The starting point of the circle (equivalent to aEnd)
aMid	The point on the arc, half-way between aStart and aEnd
aEnd	The ending point of the circle (equivalent to aStart)

Returns

The center of the circle

Definition at line 525 of file trigo.cpp.

{
 VECTOR2D dStart( static_cast<double>( aStart.x ), static_cast<double>( aStart.y ) );
 VECTOR2D dMid( static_cast<double>( aMid.x ), static_cast<double>( aMid.y ) );
 VECTOR2D dEnd( static_cast<double>( aEnd.x ), static_cast<double>( aEnd.y ) );
 VECTOR2D dCenter = CalcArcCenter( dStart, dMid, dEnd );

 VECTOR2I iCenter;

 iCenter.x = KiROUND( Clamp<double>( double( std::numeric_limits<int>::min() / 2.0 ),
 dCenter.x,
 double( std::numeric_limits<int>::max() / 2.0 ) ) );

 iCenter.y = KiROUND( Clamp<double>( double( std::numeric_limits<int>::min() / 2.0 ),
 dCenter.y,
 double( std::numeric_limits<int>::max() / 2.0 ) ) );

 return iCenter;
}

References CalcArcCenter(), KiROUND(), VECTOR2< T >::x, and VECTOR2< T >::y.

Referenced by SHAPE_ARC::ConstructFromStartEndAngle(), SHAPE_ARC::GetCenter(), PCB_ARC::GetPosition(), PCB_ARC::GetRadius(), CONVERT_TOOL::SegmentToArc(), EDA_SHAPE::SetArcGeometry(), FP_SHAPE::SetArcGeometry0(), DIALOG_GRAPHIC_ITEM_PROPERTIES::TransferDataFromWindow(), and DIALOG_GRAPHIC_ITEM_PROPERTIES::Validate().

CalcArcCenter() [4/4]

const wxPoint CalcArcCenter	(	const wxPoint &	aStart,
		const wxPoint &	aMid,
		const wxPoint &	aEnd
	)

Definition at line 546 of file trigo.cpp.

{
 VECTOR2D dStart( static_cast<double>( aStart.x ), static_cast<double>( aStart.y ) );
 VECTOR2D dMid( static_cast<double>( aMid.x ), static_cast<double>( aMid.y ) );
 VECTOR2D dEnd( static_cast<double>( aEnd.x ), static_cast<double>( aEnd.y ) );
 VECTOR2D dCenter = CalcArcCenter( dStart, dMid, dEnd );

 wxPoint iCenter;

 iCenter.x = KiROUND( Clamp<double>( double( std::numeric_limits<int>::min() / 2.0 ),
 dCenter.x,
 double( std::numeric_limits<int>::max() / 2.0 ) ) );

 iCenter.y = KiROUND( Clamp<double>( double( std::numeric_limits<int>::min() / 2.0 ),
 dCenter.y,
 double( std::numeric_limits<int>::max() / 2.0 ) ) );

 return iCenter;
}

References CalcArcCenter(), KiROUND(), VECTOR2< T >::x, and VECTOR2< T >::y.

CalcArcMid()

const VECTOR2I CalcArcMid	(	const VECTOR2I &	aStart,
		const VECTOR2I &	aEnd,
		const VECTOR2I &	aCenter,
		bool	aMinArcAngle = true
	)

Return the middle point of an arc, half-way between aStart and aEnd.

There are two possible solutions which can be found by toggling aMinArcAngle. The behaviour is undefined for semicircles (i.e. 180 degree arcs).

Parameters

aStart	The starting point of the arc (for calculating the radius)
aEnd	The end point of the arc (for determining the arc angle)
aCenter	The center point of the arc
aMinArcAngle	If true, returns the point that results in the smallest arc angle.

Returns

The middle point of the arc

Definition at line 163 of file trigo.cpp.

{
 VECTOR2I startVector = aStart - aCenter;
 VECTOR2I endVector = aEnd - aCenter;

 double startAngle = ArcTangente( startVector.y, startVector.x );
 double endAngle = ArcTangente( endVector.y, endVector.x );
 double midPointRotAngleDeciDeg = NormalizeAngle180( startAngle - endAngle ) / 2;

 if( !aMinArcAngle )
 midPointRotAngleDeciDeg += 1800.0;

 VECTOR2I newMid = aStart;
 RotatePoint( newMid, aCenter, midPointRotAngleDeciDeg );

 return newMid;
}

References ArcTangente(), NormalizeAngle180(), RotatePoint(), VECTOR2< T >::x, and VECTOR2< T >::y.

Referenced by CIRCLE::ConstructFromTanTanPt(), EDIT_TOOL::DragArcTrack(), and SCH_EAGLE_PLUGIN::loadSymbolWire().

IsPointOnSegment()

bool IsPointOnSegment	(	const wxPoint &	aSegStart,
		const wxPoint &	aSegEnd,
		const wxPoint &	aTestPoint
	)

Test if aTestPoint is on line defined by aSegStart and aSegEnd.

This function is faster than TestSegmentHit() because aTestPoint should be exactly on the line. This works fine only for H, V and 45 degree line segments.

Parameters

aSegStart	The first point of the line segment.
aSegEnd	The second point of the line segment.
aTestPoint	The point to test.

Returns

true if the point is on the line segment.

Definition at line 42 of file trigo.cpp.

{
 wxPoint vectSeg = aSegEnd - aSegStart; // Vector from S1 to S2
 wxPoint vectPoint = aTestPoint - aSegStart; // Vector from S1 to P

 // Use long long here to avoid overflow in calculations
 if( (long long) vectSeg.x * vectPoint.y - (long long) vectSeg.y * vectPoint.x )
 return false; /* Cross product non-zero, vectors not parallel */

 if( ( (long long) vectSeg.x * vectPoint.x + (long long) vectSeg.y * vectPoint.y ) <
 ( (long long) vectPoint.x * vectPoint.x + (long long) vectPoint.y * vectPoint.y ) )
 return false; /* Point not on segment */

 return true;
}

Referenced by SCH_LINE_WIRE_BUS_TOOL::AddJunctionsIfNeeded(), SCH_EDIT_FRAME::BreakSegments(), SCH_LINE_WIRE_BUS_TOOL::finishSegments(), SCH_LINE_WIRE_BUS_TOOL::TrimOverLappingWires(), SCH_EDIT_FRAME::TrimWire(), SCH_BUS_WIRE_ENTRY::UpdateDanglingState(), and SCH_BUS_BUS_ENTRY::UpdateDanglingState().

RotatePoint() [1/6]

void RotatePoint	(	int *	pX,
		int *	pY,
		double	angle
	)

Definition at line 229 of file trigo.cpp.

{
 int tmp;

 NORMALIZE_ANGLE_POS( angle );

 // Cheap and dirty optimizations for 0, 90, 180, and 270 degrees.
 if( angle == 0 )
 return;

 if( angle == 900 ) /* sin = 1, cos = 0 */
 {
 tmp = *pX;
 *pX = *pY;
 *pY = -tmp;
 }
 else if( angle == 1800 ) /* sin = 0, cos = -1 */
 {
 *pX = -*pX;
 *pY = -*pY;
 }
 else if( angle == 2700 ) /* sin = -1, cos = 0 */
 {
 tmp = *pX;
 *pX = -*pY;
 *pY = tmp;
 }
 else
 {
 double fangle = DECIDEG2RAD( angle );
 double sinus = sin( fangle );
 double cosinus = cos( fangle );
 double fpx = (*pY * sinus ) + (*pX * cosinus );
 double fpy = (*pY * cosinus ) - (*pX * sinus );
 *pX = KiROUND( fpx );
 *pY = KiROUND( fpy );
 }
}

References PNS::angle(), DECIDEG2RAD(), KiROUND(), and NORMALIZE_ANGLE_POS().

Referenced by CADSTAR_PCB_ARCHIVE_LOADER::addAttribute(), PCAD2KICAD::PCB_FOOTPRINT::AddToBoard(), PCAD2KICAD::PCB_PAD::AddToFootprint(), CADSTAR_SCH_ARCHIVE_LOADER::applyTransform(), SVG_PLOTTER::Arc(), BuildConvexHull(), BuildCornersList_S_Shape(), PAD::BuildEffectiveShapes(), CalcArcAngle(), CalcArcMid(), EDA_SHAPE::calcEdit(), PSLIKE_PLOTTER::computeTextParameters(), SHAPE_ARC::ConstructFromStartEndAngle(), SHAPE_ARC::ConstructFromStartEndCenter(), ConvertOutlineToPolygon(), AM_PRIMITIVE::ConvertShapeToPolygon(), D_CODE::ConvertShapeToPolygon(), CornerListToPolygon(), PCAD2KICAD::CorrectTextPosition(), EXCELLON_WRITER::createDrillFile(), MICROWAVE_TOOL::createFootprint(), SCH_GLOBALLABEL::CreateGraphicShape(), AM_PRIMITIVE::DrawBasicShape(), CADSTAR_PCB_ARCHIVE_LOADER::drawCadstarText(), DrawHalfOpenCylinder(), AR_MATRIX::drawSegmentQcq(), GBR_TO_PCB_EXPORTER::export_segarc_copper_item(), EXPORTER_PCB_VRML::ExportVrmlFootprint(), fillArcPOLY(), CADSTAR_ARCHIVE_PARSER::FixTextPositionNoAlignment(), GERBER_PLOTTER::FlashPadChamferRoundRect(), GERBER_PLOTTER::FlashPadCustom(), PSLIKE_PLOTTER::FlashPadOval(), HPGL_PLOTTER::FlashPadOval(), PSLIKE_PLOTTER::FlashPadRect(), HPGL_PLOTTER::FlashPadRect(), DXF_PLOTTER::FlashPadRect(), PSLIKE_PLOTTER::FlashPadTrapez(), GERBER_PLOTTER::FlashPadTrapez(), HPGL_PLOTTER::FlashPadTrapez(), DXF_PLOTTER::FlashPadTrapez(), GERBER_PLOTTER::FlashRegularPolygon(), geom_transf(), GERBER_DRAW_ITEM::GetABPosition(), CN_ITEM::GetAnchor(), EDA_SHAPE::GetArcMid(), FP_SHAPE::GetArcMid0(), LIB_TEXT::GetBoundingBox(), SCH_FIELD::GetBoundingBox(), LIB_FIELD::GetBoundingBox(), LIB_PIN::GetBoundingBox(), SCH_TEXT::GetBoundingBox(), EDA_SHAPE::getBoundingBox(), SCH_LABEL::GetBoundingBox(), EDA_RECT::GetBoundingBoxRotated(), DS_DATA_ITEM_POLYGONS::GetCornerPosition(), CADSTAR_PCB_ARCHIVE_LOADER::getKiCadPad(), EDA_TEXT::GetLinePositions(), CADSTAR_SCH_ARCHIVE_LOADER::getLocationOfNetElement(), EDA_SHAPE::GetRectCorners(), ARRAY_CIRCULAR_OPTIONS::GetTransform(), GERBER_DRAW_ITEM::GetXYPosition(), GRArc(), GRCSegm(), ALTIUM_PCB::HelperParseDimensions6Center(), ALTIUM_PCB::HelperParseDimensions6Leader(), idf_export_footprint(), RENDER_3D_RAYTRACE::insertHole(), EDA_RECT::Intersects(), SCH_LEGACY_PLUGIN_CACHE::loadArc(), LEGACY_PLUGIN::loadPAD(), EAGLE_PLUGIN::loadPlain(), CADSTAR_SCH_ARCHIVE_LOADER::loadSchematicSymbolInstances(), SCH_EAGLE_PLUGIN::loadSymbolRectangle(), CADSTAR_SCH_ARCHIVE_LOADER::loadSymDefIntoLibrary(), FOOTPRINT::MoveAnchorPosition(), EAGLE_PLUGIN::packageCircle(), SCH_ALTIUM_PLUGIN::ParseArc(), ALTIUM_PCB::ParseComponentsBodies6Data(), GPCB_FPL_CACHE::parseFOOTPRINT(), PCB_PARSER::parseFOOTPRINT_unchecked(), BRDITEMS_PLOTTER::PlotFootprintGraphicItem(), GERBER_PLOTTER::plotRoundRectAsRegion(), FABMASTER::processArc(), PCB_TARGET::Rotate(), SCH_JUNCTION::Rotate(), SCH_NO_CONNECT::Rotate(), PCB_TRACK::Rotate(), PCB_TEXT::Rotate(), LIB_TEXT::Rotate(), SCH_BUS_ENTRY_BASE::Rotate(), FP_TEXT::Rotate(), SCH_BITMAP::Rotate(), LIB_FIELD::Rotate(), SCH_FIELD::Rotate(), SCH_SHEET_PIN::Rotate(), SCH_LINE::Rotate(), SCH_TEXT::Rotate(), LIB_PIN::Rotate(), PCB_DIMENSION_BASE::Rotate(), FOOTPRINT::Rotate(), PCB_ARC::Rotate(), EDA_SHAPE::rotate(), SCH_SHEET::Rotate(), SCH_GLOBALLABEL::Rotate(), ZONE::Rotate(), SCH_SYMBOL::Rotate(), PAD::Rotate(), SCH_GLOBALLABEL::Rotate90(), SCH_LINE::RotateEnd(), RotatePoint(), SCH_LINE::RotateStart(), EDA_SHAPE::SetArcAngleAndEnd(), FP_SHAPE::SetArcAngleAndEnd0(), DS_DATA_ITEM_POLYGONS::SetBoundingBox(), FP_SHAPE::SetDrawCoord(), FP_TEXT::SetDrawCoord(), PAD::SetDrawCoord(), FP_SHAPE::SetLocalCoord(), FP_TEXT::SetLocalCoord(), PAD::SetLocalCoord(), SHAPE_ARC::SHAPE_ARC(), PAD::ShapePos(), PLOTTER::sketchOval(), PNS_KICAD_IFACE_BASE::syncPad(), FP_TEXT::TextHitTest(), EDA_TEXT::TextHitTest(), AR_MATRIX::TraceFilledRectangle(), DIALOG_PAD_PROPERTIES::TransferDataFromWindow(), EAGLE_PLUGIN::transferPad(), BOARD_ADAPTER::transformArcToSegments(), EDA_TEXT::TransformBoundingBoxWithClearanceToPolygon(), TransformCircleToPolygon(), TransformOvalToPolygon(), EDA_SHAPE::TransformShapeWithClearanceToPolygon(), PAD::TransformShapeWithClearanceToPolygon(), PCB_POINT_EDITOR::updateItem(), and GERBER_PLOTTER::writeApertureList().

RotatePoint() [2/6]

void RotatePoint	(	int *	pX,
		int *	pY,
		int	cx,
		int	cy,
		double	angle
	)

Definition at line 269 of file trigo.cpp.

{
 int ox, oy;

 ox = *pX - cx;
 oy = *pY - cy;

 RotatePoint( &ox, &oy, angle );

 *pX = ox + cx;
 *pY = oy + cy;
}

References PNS::angle(), and RotatePoint().

RotatePoint() [3/6]

void RotatePoint	(	wxPoint *	point,
		const wxPoint &	centre,
		double	angle
	)

Definition at line 283 of file trigo.cpp.

{
 int ox, oy;

 ox = point->x - centre.x;
 oy = point->y - centre.y;

 RotatePoint( &ox, &oy, angle );
 point->x = ox + centre.x;
 point->y = oy + centre.y;
}

References PNS::angle(), and RotatePoint().

RotatePoint() [4/6]

void RotatePoint	(	VECTOR2I &	point,
		const VECTOR2I &	centre,
		double	angle
	)

Definition at line 295 of file trigo.cpp.

{
 wxPoint c( centre.x, centre.y );
 wxPoint p( point.x, point.y );

 RotatePoint(&p, c, angle);

 point.x = p.x;
 point.y = p.y;
}

References PNS::angle(), RotatePoint(), VECTOR2< T >::x, and VECTOR2< T >::y.

RotatePoint() [5/6]

void RotatePoint	(	double *	pX,
		double *	pY,
		double	cx,
		double	cy,
		double	angle
	)

Definition at line 307 of file trigo.cpp.

{
 double ox, oy;

 ox = *pX - cx;
 oy = *pY - cy;

 RotatePoint( &ox, &oy, angle );

 *pX = ox + cx;
 *pY = oy + cy;
}

References PNS::angle(), and RotatePoint().

RotatePoint() [6/6]

void RotatePoint	(	double *	pX,
		double *	pY,
		double	angle
	)

Definition at line 321 of file trigo.cpp.

{
 double tmp;

 NORMALIZE_ANGLE_POS( angle );

 // Cheap and dirty optimizations for 0, 90, 180, and 270 degrees.
 if( angle == 0 )
 return;

 if( angle == 900 ) /* sin = 1, cos = 0 */
 {
 tmp = *pX;
 *pX = *pY;
 *pY = -tmp;
 }
 else if( angle == 1800 ) /* sin = 0, cos = -1 */
 {
 *pX = -*pX;
 *pY = -*pY;
 }
 else if( angle == 2700 ) /* sin = -1, cos = 0 */
 {
 tmp = *pX;
 *pX = -*pY;
 *pY = tmp;
 }
 else
 {
 double fangle = DECIDEG2RAD( angle );
 double sinus = sin( fangle );
 double cosinus = cos( fangle );

 double fpx = (*pY * sinus ) + (*pX * cosinus );
 double fpy = (*pY * cosinus ) - (*pX * sinus );
 *pX = fpx;
 *pY = fpy;
 }
}

References PNS::angle(), DECIDEG2RAD(), and NORMALIZE_ANGLE_POS().

SegmentIntersectsSegment()

bool SegmentIntersectsSegment	(	const wxPoint &	a_p1_l1,
		const wxPoint &	a_p2_l1,
		const wxPoint &	a_p1_l2,
		const wxPoint &	a_p2_l2,
		wxPoint *	aIntersectionPoint = nullptr
	)

Test if two lines intersect.

Parameters

a_p1_l1	The first point of the first line.
a_p2_l1	The second point of the first line.
a_p1_l2	The first point of the second line.
a_p2_l2	The second point of the second line.
aIntersectionPoint	is filled with the intersection point if it exists

Returns

bool - true if the two segments defined by four points intersect. (i.e. if the 2 segments have at least a common point)

Definition at line 61 of file trigo.cpp.

{

 //We are forced to use 64bit ints because the internal units can overflow 32bit ints when
 // multiplied with each other, the alternative would be to scale the units down (i.e. divide
 // by a fixed number).
 int64_t dX_a, dY_a, dX_b, dY_b, dX_ab, dY_ab;
 int64_t num_a, num_b, den;

 //Test for intersection within the bounds of both line segments using line equations of the
 // form:
 // x_k(u_k) = u_k * dX_k + x_k(0)
 // y_k(u_k) = u_k * dY_k + y_k(0)
 // with 0 <= u_k <= 1 and k = [ a, b ]

 dX_a = int64_t{ a_p2_l1.x } - a_p1_l1.x;
 dY_a = int64_t{ a_p2_l1.y } - a_p1_l1.y;
 dX_b = int64_t{ a_p2_l2.x } - a_p1_l2.x;
 dY_b = int64_t{ a_p2_l2.y } - a_p1_l2.y;
 dX_ab = int64_t{ a_p1_l2.x } - a_p1_l1.x;
 dY_ab = int64_t{ a_p1_l2.y } - a_p1_l1.y;

 den = dY_a * dX_b - dY_b * dX_a ;

 //Check if lines are parallel
 if( den == 0 )
 return false;

 num_a = dY_ab * dX_b - dY_b * dX_ab;
 num_b = dY_ab * dX_a - dY_a * dX_ab;

 // Only compute the intersection point if requested
 if( aIntersectionPoint )
 {
 *aIntersectionPoint = a_p1_l1;
 aIntersectionPoint->x += KiROUND( dX_a * ( double )num_a / ( double )den );
 aIntersectionPoint->y += KiROUND( dY_a * ( double )num_b / ( double )den );
 }

 if( den < 0 )
 {
 den = -den;
 num_a = -num_a;
 num_b = -num_b;
 }

 //Test sign( u_a ) and return false if negative
 if( num_a < 0 )
 return false;

 //Test sign( u_b ) and return false if negative
 if( num_b < 0 )
 return false;

 //Test to ensure (u_a <= 1)
 if( num_a > den )
 return false;

 //Test to ensure (u_b <= 1)
 if( num_b > den )
 return false;

 return true;
}

References KiROUND().

Referenced by EDA_RECT::Intersects().

TestSegmentHit()

bool TestSegmentHit	(	const wxPoint &	aRefPoint,
		const wxPoint &	aStart,
		const wxPoint &	aEnd,
		int	aDist
	)

Test if aRefPoint is with aDistance on the line defined by aStart and aEnd.

Parameters

aRefPoint	= reference point to test
aStart	is the first end-point of the line segment
aEnd	is the second end-point of the line segment
aDist	= maximum distance for hit

Definition at line 129 of file trigo.cpp.

{
 int xmin = aStart.x;
 int xmax = aEnd.x;
 int ymin = aStart.y;
 int ymax = aEnd.y;
 wxPoint delta = aStart - aRefPoint;

 if( xmax < xmin )
 std::swap( xmax, xmin );

 if( ymax < ymin )
 std::swap( ymax, ymin );

 // First, check if we are outside of the bounding box
 if( ( ymin - aRefPoint.y > aDist ) || ( aRefPoint.y - ymax > aDist ) )
 return false;

 if( ( xmin - aRefPoint.x > aDist ) || ( aRefPoint.x - xmax > aDist ) )
 return false;

 // Next, eliminate easy cases
 if( aStart.x == aEnd.x && aRefPoint.y > ymin && aRefPoint.y < ymax )
 return std::abs( delta.x ) <= aDist;

 if( aStart.y == aEnd.y && aRefPoint.x > xmin && aRefPoint.x < xmax )
 return std::abs( delta.y ) <= aDist;

 SEG segment( aStart, aEnd );
 return segment.SquaredDistance( aRefPoint ) < SEG::Square( aDist + 1 );
}

References delta, SEG::Square(), and SEG::SquaredDistance().

Referenced by SCH_EAGLE_PLUGIN::addBusEntries(), EE_GRID_HELPER::computeAnchors(), DRAWING_TOOL::DrawVia(), SCH_BUS_ENTRY_BASE::HitTest(), DS_DRAW_ITEM_LINE::HitTest(), PCB_TRACK::HitTest(), GERBER_DRAW_ITEM::HitTest(), DS_DRAW_ITEM_RECT::HitTest(), SCH_LINE::HitTest(), EDA_SHAPE::hitTest(), SCH_EAGLE_PLUGIN::moveLabels(), and SCH_TEXT::UpdateDanglingState().