Быстрый алгоритм, находящий положение прямой с заданной длиной и положением центра тяжести, лежащей на некоторой заданной неровной поверхности (в плоскости) почти всегда за один проход
Алгоритм немного недоработан - иногда не может найти положение.
// This function represents the algorithm of finding the interval, that "lies
// on" the ground function
// GroundFunction is the function of ground height (in metres), depending on
// the integer absciss.
// GroundFunctionLength is the number of ground function points.
// The absciss in the ground function is calculated as the division of
// absciss in metres on the MetresPerInt value.
// The interval center has the IntervalCenterAbscissInt absciss in the
// ground function.
// IntervalLengthLeft and IntervalLengthRight are the interval's length
// in metres from the center of mass point.
// The sharpness fraction is used to define, if the ground function is
// higher, than the interval or not: when the ground is higher on the
// SharpnessCoeff, multiplicated by the current interval ordinate value, it
// is accepted as not higher value.
// This function calculates the IntervalAngle (radians) and
// IntervalCenterOrdinate (metres) of the interval, that "lies on" the ground
// function.
// Function returns "Success" if the calculation had been performed
// successfully and "Failure" if the interval intersects with the ground
// function in a too small absciss diapazone or if it has to recalculate
// the interval properties for too much times.
TResult FindClosestIntervalHigherGroundFunction( TFloat* GroundFunction,
TInteger GroundFunctionLength, TFloat MetresPerInt,
TInteger IntervalCenterAbscissInt,
TFloat IntervalLengthLeft, TFloat IntervalLengthRight,
TFloat SharpnessCoeff,
TFloat& IntervalAngle, TFloat& IntervalCenterOrdinate )
{
#ifdef LineOnCurveUnitCPP_DEBUG_MODE
// clearing
MainForm->OutputImage->Canvas->Brush->Color = BackgroundColor;
MainForm->OutputImage->Canvas->Brush->Style = bsSolid;
MainForm->OutputImage->Canvas->Pen->Width = 1;
MainForm->OutputImage->Canvas->Pen->Color = BackgroundColor;
MainForm->OutputImage->Canvas->Pen->Style = psSolid;
MainForm->OutputImage->Canvas->Rectangle( 0, 0,
MainForm->OutputImage->Width, MainForm->OutputImage->Height );
// drawing offset
TFloat DrawingOffsetX = (TDouble)
TDouble( MainForm->OutputImage->Width ) / 2. -
( MetresPerInt * TDouble( GroundFunctionLength ) / 2
GroundFunctionStartingAbsciss ) * Scale;
TFloat DrawingOffsetY = TDouble( MainForm->OutputImage->Height ) * 0.75;
#endif
// initializing
IntervalCenterOrdinate = GroundFunction[
Max( 0, Min( GroundFunctionLength, IntervalCenterAbscissInt ) ) ];
IntervalAngle = 0;
TInteger NumberOfRuns = 0;
// Moving from the center of the interval
TInteger CycleLength = Min(
Max( IntervalLengthLeft, IntervalLengthRight ) / MetresPerInt 1.,
Max( TDouble( GroundFunctionLength - IntervalCenterAbscissInt ),
TDouble( IntervalCenterAbscissInt ) ) );
// there's no function under the interval to work on
if ( CycleLength < 1 )
return Failure;
// the algorithm is runned from here again on rerun, if required
AlgorithmReRunStart:
// protecting from the infinite loop
NumberOfRuns ;
if ( NumberOfRuns > 3 )
return Failure;
TFloat prevTrapezeLeftX = 0;
TFloat prevTrapezeRightX = 0;
TFloat prevTrapezeLeftY = IntervalCenterOrdinate;
TFloat prevTrapezeRightY = IntervalCenterOrdinate;
for ( TInteger i = 1; i < CycleLength; i )
{
// moving in both directions
TInteger leftXInt = Max( IntervalCenterAbscissInt -
Min( i, TInteger( Round( IntervalLengthLeft / MetresPerInt ) ) ),
0 );
TInteger rightXInt = Min( IntervalCenterAbscissInt
Min( i, TInteger( Round( IntervalLengthRight / MetresPerInt ) ) ),
GroundFunctionLength - 1 );
TFloat leftX = 0
TDouble( leftXInt - IntervalCenterAbscissInt ) * MetresPerInt;
TFloat rightX = 0
TDouble( rightXInt - IntervalCenterAbscissInt ) * MetresPerInt;
TFloat leftY = GroundFunction[ leftXInt ];
TFloat rightY = GroundFunction[ rightXInt ];
// calculating the interval properties to make touch two points of four:
// 1) the previous tropeze
// 2) current points of the function
// and not allow any of those points to be higher, than the interval
TFloat newTrapezeLeftX = prevTrapezeLeftX;
TFloat newTrapezeRightX = prevTrapezeRightX;
TFloat newTrapezeLeftY = prevTrapezeLeftY;
TFloat newTrapezeRightY = prevTrapezeRightY;
// calculating wich of new points lie higher, than the line, coinciding to
// the interval, previously found
// if the point is higher, it will be the new point of the interval,
// otherwise the new point should be the previous point of the trapeze
if ( leftY > IntervalCenterOrdinate
( leftX - 0 ) * tan( IntervalAngle ) )
{
newTrapezeLeftX = leftX;
newTrapezeLeftY = leftY;
};
if ( rightY > IntervalCenterOrdinate
( rightX - 0 ) * tan( IntervalAngle ) )
{
newTrapezeRightX = rightX;
newTrapezeRightY = rightY;
};
#ifdef LineOnCurveUnitCPP_DEBUG_MODE
TFloat IntervalCenterAbsciss =
TDouble(IntervalCenterAbscissInt) * MetresPerInt
GroundFunctionStartingAbsciss;
// drawing the trapeze
MainForm->OutputImage->Canvas->Pen->Color = TrapezeColor;
MainForm->OutputImage->Canvas->MoveTo(
DrawingOffsetX ( newTrapezeLeftX IntervalCenterAbsciss ) * Scale,
DrawingOffsetY - newTrapezeLeftY * Scale );
MainForm->OutputImage->Canvas->LineTo(
DrawingOffsetX ( newTrapezeRightX IntervalCenterAbsciss ) * Scale,
DrawingOffsetY - newTrapezeRightY * Scale );
#endif
// calculating the new properties for the interval
if ( newTrapezeRightX != newTrapezeLeftX )
{
IntervalAngle = atan2(
newTrapezeRightY - newTrapezeLeftY,
newTrapezeRightX - newTrapezeLeftX );
IntervalCenterOrdinate = newTrapezeLeftY
( 0 - newTrapezeLeftX ) *
tan( IntervalAngle );
// the interval length (taking the angle of it into account) has the
// desired value already
TFloat CosIntervalAngle = cos( IntervalAngle );
if ( CosIntervalAngle != 0. )
if ( ( ( 0 - leftX ) / CosIntervalAngle >=
IntervalLengthLeft ) &&
( ( rightX - 0 ) / CosIntervalAngle >=
IntervalLengthRight ) )
goto CheckResult;
}
else
{
IntervalAngle = 0;
IntervalCenterOrdinate = Max( newTrapezeLeftY, newTrapezeRightY );
};
// calculating the the current trapeze will be used as the previous
// on the next step
prevTrapezeLeftX = newTrapezeLeftX;
prevTrapezeRightX = newTrapezeRightX;
prevTrapezeLeftY = newTrapezeLeftY;
prevTrapezeRightY = newTrapezeRightY;
};
// this algorighm requires checking, due to there could be some points
// over the interval in some cases, because the previous trapeze is
// build not as the previous by coordinates, but as the previous, that
// had been changed, so if there was a point in the function, that was
// not higher the interval in the current position, it woun't be taken
// into account in the next calculation and could be skept
// so the checking and the second run is required in that case
// checking
CheckResult:
TInteger IntervalStartInt = IntervalCenterAbscissInt -
Round( IntervalLengthLeft * cos( IntervalAngle ) / MetresPerInt ) 1;
TInteger IntervalEndInt = IntervalCenterAbscissInt
Round( IntervalLengthRight * cos( IntervalAngle ) / MetresPerInt ) - 1;
for ( TInteger i = Max( 0, IntervalStartInt );
i < Min( IntervalEndInt 1, GroundFunctionLength ); i )
{
TFloat IntervalCenterAbsciss =
TDouble(IntervalCenterAbscissInt) * MetresPerInt
GroundFunctionStartingAbsciss;
TFloat CurX = TDouble( i - IntervalCenterAbscissInt ) * MetresPerInt
IntervalCenterAbsciss;
TFloat CurY = IntervalCenterOrdinate
( CurX - IntervalCenterAbsciss ) * tan( IntervalAngle );
#ifdef LineOnCurveUnitCPP_DEBUG_MODE
MainForm->OutputImage->Canvas->Pen->Color = clBlue;
MainForm->OutputImage->Canvas->Ellipse(
DrawingOffsetX CurX * Scale 2,
DrawingOffsetY - CurY * Scale - 1,
DrawingOffsetX CurX * Scale - 1,
DrawingOffsetY - CurY * Scale 2 );
MainForm->OutputImage->Canvas->Pen->Width = 1;
#endif
if ( ( CurY > 0. ? ( 1. SharpnessCoeff ) * CurY :
( 1. - SharpnessCoeff ) * CurY ) <
GroundFunction[i] ) goto AlgorithmReRunStart;
};
// the function intersects with the interval in too few points
return Success;
}
