OpenWalnut  1.4.0
WLine_test.h
00001 //---------------------------------------------------------------------------
00002 //
00003 // Project: OpenWalnut ( http://www.openwalnut.org )
00004 //
00005 // Copyright 2009 OpenWalnut Community, BSV@Uni-Leipzig and CNCF@MPI-CBS
00006 // For more information see http://www.openwalnut.org/copying
00007 //
00008 // This file is part of OpenWalnut.
00009 //
00010 // OpenWalnut is free software: you can redistribute it and/or modify
00011 // it under the terms of the GNU Lesser General Public License as published by
00012 // the Free Software Foundation, either version 3 of the License, or
00013 // (at your option) any later version.
00014 //
00015 // OpenWalnut is distributed in the hope that it will be useful,
00016 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00017 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00018 // GNU Lesser General Public License for more details.
00019 //
00020 // You should have received a copy of the GNU Lesser General Public License
00021 // along with OpenWalnut. If not, see <http://www.gnu.org/licenses/>.
00022 //
00023 //---------------------------------------------------------------------------
00024 
00025 #ifndef WLINE_TEST_H
00026 #define WLINE_TEST_H
00027 
00028 #include <sstream>
00029 #include <string>
00030 
00031 #include <cxxtest/TestSuite.h>
00032 
00033 #include "../../exceptions/WOutOfBounds.h"
00034 #include "../../WLimits.h"
00035 #include "../WLine.h"
00036 #include "WLineTraits.h"
00037 #include "WPositionTraits.h"
00038 
00039 /**
00040  * Unit tests the WLine class
00041  */
00042 class WLineTest : public CxxTest::TestSuite
00043 {
00044 public:
00045     /**
00046      * If two lines have different lengths they are considered diffrent
00047      * regardless on the given delta and the first point on which they
00048      * differ should be returned.
00049      */
00050     void testEqualsDeltaDifferentLength( void )
00051     {
00052         WLine line;
00053         line.push_back( WPosition( 0, 0, 0 ) );
00054         line.push_back( WPosition( 1, 0, 0 ) );
00055         WLine other;
00056         other.push_back( WPosition( 0, 0, 0 ) );
00057         TS_ASSERT_EQUALS( equalsDelta( line, other, 0.0 ), 1 );
00058     }
00059 
00060     /**
00061      * If both lines are of same size, but there is a point differing on
00062      * more than the given delta the first point which differs should be
00063      * returned.
00064      */
00065     void testEqualsDeltaOnRealDifferentLines( void )
00066     {
00067         WLine line;
00068         line.push_back( WPosition( 0, 0, 0 ) );
00069         line.push_back( WPosition( 1, 0, 0 ) );
00070         WLine other;
00071         other.push_back( WPosition( 0, 0, 0 ) );
00072         other.push_back( WPosition( 1, 0, 0 + 2 * wlimits::DBL_EPS ) );
00073         TS_ASSERT_EQUALS( equalsDelta( line, other, wlimits::DBL_EPS ), 1 );
00074     }
00075 
00076     /**
00077      * If both lines are of same size and every point pair don't differ in
00078      * terms of the given delta, -1 should be returned.
00079      */
00080     void testEqualsDeltaOnDifferentLinesButWithinDelta( void )
00081     {
00082         WLine line;
00083         line.push_back( WPosition( 0, 0, 0 ) );
00084         line.push_back( WPosition( 1, 0, 0 ) );
00085         WLine other;
00086         other.push_back( WPosition( 0, 0, 0 ) );
00087         other.push_back( WPosition( 1, 0, 0 + 2 * wlimits::DBL_EPS ) );
00088         TS_ASSERT_EQUALS( equalsDelta( line, other, 2 * wlimits::DBL_EPS ), -1 );
00089     }
00090 
00091     /**
00092      * When printing a line to stdout it the output should be as follows:
00093      * [first_pos, ..., last_pos] where the positions also should be in
00094      * the same format, so in the end we would have:
00095      * [[0,1,0],...[0,0,0]]
00096      */
00097     void testOutputOperator( void )
00098     {
00099         WLine l;
00100         l.push_back( WPosition( 1.0, 1.0, 3.1415 ) );
00101         l.push_back( WPosition( 0.0, 0.0, 0.44 ) );
00102         l.push_back( WPosition( 1.0, 1.0, 1.0 ) );
00103         std::string expected( "[1.0000000000000000e+00;1.0000000000000000e+00;3.1415000000000002e+00;, "
00104                                "0.0000000000000000e+00;0.0000000000000000e+00;4.4000000000000000e-01;, "
00105                                "1.0000000000000000e+00;1.0000000000000000e+00;1.0000000000000000e+00;]" );
00106         std::stringstream ss;
00107         ss << l;
00108         TS_ASSERT_EQUALS( expected, ss.str() );
00109     }
00110 
00111     /**
00112      * Two Lines are equal if they have the same points in the same order.
00113      */
00114     void testEqualityOperator( void )
00115     {
00116         WLine line1;
00117         line1.push_back( WPosition( 1.0, 1.0, 3.1415 ) );
00118         line1.push_back( WPosition( 0.0, 0.0, 0.44 ) );
00119         line1.push_back( WPosition( 1.0, 1.0, 1.0 ) );
00120         WLine line2;
00121         line2.push_back( WPosition( 1.0, 1.0, 3.1415 ) );
00122         line2.push_back( WPosition( 0.0, 0.0, 0.44 ) );
00123         line2.push_back( WPosition( 1.0, 1.0, 1.0 ) );
00124         TS_ASSERT_EQUALS( line1, line2 );
00125         line2.back()[1] += 0.0000000001;
00126         TS_ASSERT_DIFFERS( line1, line2 );
00127     }
00128 
00129     /**
00130      * When accessing an item within 0..length-1 a const reference to the
00131      * WPosition object should be returned.
00132      */
00133     void testAccessOperatorWithinValidBounds( void )
00134     {
00135         WLine line;
00136         line.push_back( WPosition( 1.0, 1.0, 3.1415 ) );
00137         line.push_back( WPosition( 0.0, 0.0, 0.44 ) );
00138         line.push_back( WPosition( 1.0, 1.0, 1.0 ) );
00139         WPosition expected( 1.0, 1.0, 1.0 );
00140         TS_ASSERT_EQUALS( expected, line[2] );
00141     }
00142 
00143     /**
00144      * If for example the start and end points of two lines are in opposite
00145      * direction we may want to change its direction.
00146      */
00147     void testReverseOrdering( void )
00148     {
00149         WLine line;
00150         line.push_back( WPosition( 1, 2, 3 ) );
00151         line.push_back( WPosition( 4, 5, 6 ) );
00152         line.push_back( WPosition( 7, 8, 9 ) );
00153         WLine expected;
00154         expected.push_back( WPosition( 7, 8, 9 ) );
00155         expected.push_back( WPosition( 4, 5, 6 ) );
00156         expected.push_back( WPosition( 1, 2, 3 ) );
00157         line.reverseOrder();
00158         TS_ASSERT_EQUALS( line, expected );
00159     }
00160 
00161     /**
00162      * The path length of the line is the accumulated path lengths of all
00163      * segements (point to point) in that line.
00164      */
00165     void testPathLength( void )
00166     {
00167         WLine line;
00168         line.push_back( WPosition( 1, 2, 3 ) );
00169         line.push_back( WPosition( 4, 5, 6 ) );
00170         line.push_back( WPosition( 7, 8, 9 ) );
00171         double expected = length( WPosition( 1, 2, 3 ) - WPosition( 4, 5, 6 ) ) +
00172                           length( WPosition( 4, 5, 6 ) - WPosition( 7, 8, 9 ) );
00173         TS_ASSERT_DELTA( expected, pathLength( line ), 1e-6 );
00174     }
00175 
00176     /**
00177      * When resampling a line a new line is generated having the given number
00178      * of sampling points. Its start and end points remain the same, but its
00179      * curvature may change a bit and also its length!
00180      * Down sampling means you will have
00181      */
00182     void testDownSampleLine( void )
00183     {
00184         WLine line;
00185         line.push_back( WPosition( 0, 0, 0 ) );
00186         line.push_back( WPosition( 1, 1, 0 ) );
00187         line.push_back( WPosition( 2, 0, 0 ) );
00188         line.push_back( WPosition( 3, 1, 0 ) );
00189         line.resampleByNumberOfPoints( 3 );
00190         WLine expected;
00191         expected.push_back( WPosition( 0, 0, 0 ) );
00192         expected.push_back( WPosition( 1.5, 0.5, 0 ) );
00193         expected.push_back( WPosition( 3, 1, 0 ) );
00194         assert_equals_delta( line, expected, 2 * wlimits::DBL_EPS );
00195     }
00196 
00197     /**
00198      * If the resampling rate of a line has as many points as the original line,
00199      * no sampling should be applied.
00200      */
00201     void testSamplingWithSameNumberOfPoints( void )
00202     {
00203         WLine line;
00204         for( size_t i = 0; i < 10; ++i )
00205         {
00206             line.push_back( WPosition( i, 3 * i, 10 - i ) );
00207         }
00208         TS_ASSERT( line.size() == 10 );
00209         WLine expected( line ); // make a copy of the original
00210         line.resampleByNumberOfPoints( 10 );
00211         assert_equals_delta( line, expected );
00212     }
00213 
00214     /**
00215      * If the points are exactly in between of a segement nothing should fail.
00216      */
00217     void testSamplingPointsAreExactlyInTheOldSegmentCenterAndCorners( void )
00218     {
00219         WLine line;
00220         WLine expected;
00221         for( int i = 0; i < 3; ++i )
00222         {
00223             line.push_back( WPosition( i, std::pow( -1.0, i % 2 ), 0 ) );
00224             expected.push_back( WPosition( i, std::pow( -1.0, i % 2 ), 0 ) );
00225             expected.push_back( WPosition( i + 0.5, 0, 0 ) );
00226         }
00227         expected.pop_back();
00228         line.resampleByNumberOfPoints( 5 );
00229         assert_equals_delta( expected, line );
00230     }
00231 
00232     /**
00233      * When resampling with many sample points the numerical errors may sum
00234      * up. Hence I watch if it not breaks a certain threshold: 1.0e-10*newSegmentLength.
00235      */
00236     void testNumericalStabilityOfResampling( void )
00237     {
00238         WLine line;
00239         WLine expected;
00240         for( int i = 0; i < 100; ++i )
00241         {
00242             line.push_back( WPosition( i, std::pow( -1.0, i % 2 ), 0 ) );
00243             expected.push_back( WPosition( i, std::pow( -1.0, i % 2 ), 0 ) );
00244             expected.push_back( WPosition( i + 0.25, std::pow( -1.0, i % 2 ) * 0.5, 0 ) );
00245             expected.push_back( WPosition( i + 0.5,  0, 0 ) );
00246             expected.push_back( WPosition( i + 0.75, std::pow( -1.0, ( i + 1 ) % 2 ) * 0.5, 0 ) );
00247         }
00248         expected.pop_back();
00249         expected.pop_back();
00250         expected.pop_back();
00251         line.resampleByNumberOfPoints( 4 * 99 + 1 );
00252         assert_equals_delta( expected, line, 1.0e-10 * std::sqrt( 5.0 ) / 4 );
00253     }
00254 
00255     /**
00256      * If there are many new sample points between two old sample points nothing should fail either.
00257      */
00258     void testManySampelsInBetweenOfTwoOldPoints( void )
00259     {
00260         WLine line;
00261         line.push_back( WPosition( 0, 0, 0 ) );
00262         line.push_back( WPosition( 1, 1, 0 ) );
00263         line.resampleByNumberOfPoints( 1001 );
00264         WLine expected;
00265         expected.push_back( WPosition( 0, 0, 0 ) );
00266         for( size_t i = 1; i < 1001; ++i )
00267         {
00268             expected.push_back( WPosition( i / 1000.0, i / 1000.0, 0 ) );
00269         }
00270         assert_equals_delta( expected, line, 1.0 / 1001.0 * 1.0e-10 );
00271     }
00272 
00273    /**
00274      * The mid point of a WLine is just the point in the middle of the line.
00275      * For lines with even numbered size the element before that non existing
00276      * midPoint is selected.
00277      */
00278     void testMidPointOnEvenSize( void )
00279     {
00280         WLine line;
00281         line.push_back( WPosition( 0, 0, 0 ) );
00282         line.push_back( WPosition( 1, 1, 0 ) );
00283         line.push_back( WPosition( 2, 0, 0 ) );
00284         line.push_back( WPosition( 3, 1, 0 ) );
00285         WPosition expected( 1, 1, 0 );
00286         TS_ASSERT_EQUALS( expected, WPosition( midPoint( line ) ) );
00287     }
00288 
00289     /**
00290      * When a line has uneven numbered size, the mid point is unique.
00291      */
00292     void testMidPointOnUnevenSize( void )
00293     {
00294         WLine line;
00295         line.push_back( WPosition( 0, 0, 0 ) );
00296         line.push_back( WPosition( 1, 1, 0 ) );
00297         line.push_back( WPosition( 2, 0, 0 ) );
00298         WPosition expected( 1, 1, 0 );
00299         TS_ASSERT_EQUALS( expected, WPosition( midPoint( line ) ) );
00300     }
00301 
00302     /**
00303      * When calling midPoint on empty lines => there is no point to return
00304      * hence an exception is generated.
00305      */
00306     void testMidPointOnEmptyLine( void )
00307     {
00308         WLine line;
00309         WPosition expected( 1, 1, 0 );
00310         TS_ASSERT_THROWS_EQUALS( midPoint( line ), WOutOfBounds &e, std::string( e.what() ), "There is no midpoint for an empty line." );
00311     }
00312 
00313     /**
00314      * The max segemnent length is the maximum length over all segments (p_i<->p_j). For further
00315      * information look just on the name of the test function, I think this is really precised ;).
00316      * (Ha one more line in hg churn!)
00317      * BTW: If there are multiple max lengths (equidistant sampled tracts) the first shall be
00318      * chosen, BTW: this is totally stupid!, if they are equals it doesn't matter anyway, huh???
00319      */
00320     void testMaxSegementLength( void )
00321     {
00322         WLine line;
00323         line.push_back( WPosition( 0, 0, 0 ) );
00324         line.push_back( WPosition( 1, 1, 0 ) );
00325         line.push_back( WPosition( 2, 0, 0 ) );
00326         TS_ASSERT_DELTA( maxSegmentLength( line ), std::sqrt( 2.0 ), wlimits::DBL_EPS );
00327         line.push_back( WPosition( 0, 0, 0 ) );
00328         TS_ASSERT_DELTA( maxSegmentLength( line ), 2.0, wlimits::DBL_EPS );
00329     }
00330 
00331     /**
00332      * If there no points at all, 0.0 shall be returned.
00333      */
00334     void testEmptyLineOnMaxSegementLength( void )
00335     {
00336         WLine line;
00337         TS_ASSERT_EQUALS( maxSegmentLength( line ), 0.0 );
00338         line.push_back( WPosition( 0, 3.1415, 0 ) );
00339         TS_ASSERT_EQUALS( maxSegmentLength( line ), 0.0 );
00340     }
00341 
00342     /**
00343      * If there are duplicates next to each other => collapse them.
00344      */
00345     void testRemoveAdjacentDuplicates( void )
00346     {
00347         WLine line;
00348         line.push_back( WPosition( 0.1, 3.4, 34254.5 ) );
00349         line.push_back( WPosition( 0.1, 3.4, 34254.5 ) );
00350         line.push_back( WPosition( 0.1, 3.4, 34254.5 ) );
00351         line.push_back( WPosition( 0.1, 3.4, 34254.5 ) );
00352         line.push_back( WPosition( 0.0, 0.0, 0.0 ) );
00353         line.push_back( WPosition( 0.1, 3.4, 34254.5 ) );
00354         line.push_back( WPosition( 0.1, 3.4, 34254.5 ) );
00355         line.push_back( WPosition( 0.1, 3.4, 34254.5 ) );
00356         WLine expected;
00357         expected.push_back( WPosition( 0.1, 3.4, 34254.5 ) );
00358         expected.push_back( WPosition( 0.0, 0.0, 0.0 ) );
00359         expected.push_back( WPosition( 0.1, 3.4, 34254.5 ) );
00360         line.removeAdjacentDuplicates();
00361         assert_equals_delta( line, expected );
00362     }
00363 
00364     /**
00365      * No sample points should remain no sample points.
00366      */
00367     void testResamplingByNewSegmentLengthWithZeroLine( void )
00368     {
00369         WLine line;
00370         line.resampleBySegmentLength( 3.1415f );
00371         assert_equals_delta( line, WLine() );
00372     }
00373 
00374     /**
00375      * Lines with size() == 1, should also remain untouched.
00376      */
00377     void testResamplingByNewSegementLengthWithLineHavingJustOnePoint( void )
00378     {
00379         WLine line;
00380         line.push_back( WPosition( 0.1, 3.4, 34254.5 ) );
00381         WLine expected( line );
00382         line.resampleBySegmentLength( 3.1415f );
00383         assert_equals_delta( line, expected );
00384     }
00385 
00386     /**
00387      * If there is a segement bigger than the newSegmentLength, then the new segment should be
00388      * inserted and then with the new point should be proceeded just the same.
00389      */
00390     void testResamplingByNewSegementLengthOldSegmentLengthBiggerAsNewSegmentLength( void )
00391     {
00392         WLine line;
00393         line.push_back( WPosition( 0.0, 0.0, 0.0 ) );
00394         line.push_back( WPosition( 1.1, 0.0, 0.0 ) );
00395         line.resampleBySegmentLength( 1.0 );
00396         WLine expected;
00397         expected.push_back( WPosition( 0.0, 0.0, 0.0 ) );
00398         expected.push_back( WPosition( 1.0, 0.0, 0.0 ) );
00399         assert_equals_delta( line, expected );
00400     }
00401 
00402     /**
00403      * Only if a sample point comes out of the circle with radius newSegmentLength then append the
00404      * point of intersection.
00405      */
00406     void testResamplingByNewSegementLengthTravelingOutOfTheCircle( void )
00407     {
00408         WLine line;
00409         line.push_back( WPosition( 0.0, 0.0, 0.0 ) );
00410         line.push_back( WPosition( 1.0, 1.0, 0.0 ) );
00411         line.push_back( WPosition( 0.0, 1.0, 0.0 ) );
00412         line.push_back( WPosition( 1.0, 2.0, 0.0 ) );
00413         line.push_back( WPosition( 0.0, 2.0, 0.0 ) );
00414         line.push_back( WPosition( 1.0, 3.0, 0.0 ) );
00415         line.resampleBySegmentLength( 3.0 );
00416         WLine expected;
00417         expected.push_back( WPosition( 0.0, 0.0, 0.0 ) );
00418         expected.push_back( WPosition( 0.870829, 2.87083, 0.0 ) );
00419         assert_equals_delta( line, expected, 0.00001 );
00420     }
00421 
00422 private:
00423     /**
00424      * TS_ASSERT_DELTA needs the operator+, operator- and operator< to be implemented especially for WPositions the operator< and operator +
00425      * makes not really sense. Hence I implemented an assert by my one, giving reasonable out put.
00426      *
00427      * \param first First line to compare with
00428      * \param second Second line to compare with
00429      * \param delta The delta within two points are considered as equally
00430      */
00431     void assert_equals_delta( const WLine& first, const WLine& second, double delta = wlimits::DBL_EPS ) const
00432     {
00433         int diffPos = 0;
00434         if( ( diffPos = equalsDelta( first, second, delta ) ) != -1 )
00435         {
00436             using string_utils::operator<<;
00437             std::stringstream msg;
00438             msg << "Lines are different in at least point: " << diffPos;
00439             TS_FAIL( msg.str() );
00440             if( static_cast< int >( first.size() ) > diffPos && static_cast< int >( second.size() ) > diffPos )
00441             {
00442                 std::cout << "first  line at: " << diffPos << std::endl << first[diffPos] << std::endl;
00443                 std::cout << "second line at: " << diffPos << std::endl << second[diffPos] << std::endl;
00444             }
00445             else
00446             {
00447                 std::cout << "lines does not have the same number of points: first=" << first.size() << " second=" << second.size() << std::endl;
00448             }
00449             std::cout << "first  line: " << std::endl << first << std::endl;
00450             std::cout << "second line: " << std::endl << second << std::endl;
00451         }
00452     }
00453 };
00454 #endif  // WLINE_TEST_H