Changeset 84:ab3beb283aa3 in rrlib_geometry


Ignore:
Timestamp:
08.03.2017 18:21:08 (3 years ago)
Author:
Tobias Föhst <tobias.foehst@…>
Branch:
14.08
Children:
86:d5f3717879e9, 88:0652d9041270
Phase:
public
Message:

Fixes detection of infinite intersection points for line segments and general intersection of degraded lines

Files:
3 edited

Legend:

Unmodified
Added
Removed
  • curves/tBezierCurve.hpp

    r78 r84  
    3434#include "rrlib/util/variadic_templates.h" 
    3535 
    36 #include <iomanip> 
    3736//---------------------------------------------------------------------- 
    3837// Internal includes with "" 
     
    254253  { 
    255254    intersection_points.push_back(intersection_point); 
    256     const auto baseline_parameter = math::LimitedValue<tParameter>((intersection_points.back() - this->control_points[0]).Length() / (this->control_points[Tdegree] - this->control_points[0]).Length(), 0, 1); 
     255    const auto baseline_length = (this->control_points[Tdegree] - this->control_points[0]).Length(); 
     256    const auto baseline_parameter = baseline_length == 0 ? 0 : math::LimitedValue<tParameter>((intersection_points.back() - this->control_points[0]).Length() / baseline_length, 0, 1); 
    257257    assert(!std::isnan(baseline_parameter)); 
    258258    intersection_parameters.push_back(min_parameter + (max_parameter - min_parameter) * baseline_parameter); 
     
    292292  { 
    293293    intersection_points.push_back(intersection_point); 
    294     const auto baseline_parameter = math::LimitedValue<tParameter>((intersection_points.back() - this->control_points[0]).Length() / (this->control_points[Tdegree] - this->control_points[0]).Length(), 0, 1); 
     294    const auto baseline_length = (this->control_points[Tdegree] - this->control_points[0]).Length(); 
     295    const auto baseline_parameter = baseline_length == 0 ? 0 : math::LimitedValue<tParameter>((intersection_points.back() - this->control_points[0]).Length() / baseline_length, 0, 1); 
    295296    assert(!std::isnan(baseline_parameter)); 
    296297    intersection_parameters.push_back(min_parameter + (max_parameter - min_parameter) * baseline_parameter); 
  • tLine.hpp

    r82 r84  
    136136tIntersectionType IntersectLineWithLine(typename tLine<Tdimension, TElement>::tPoint &intersection_point, const tLine<Tdimension, TElement> &left, const tLine<Tdimension, TElement> &right) 
    137137{ 
     138  if (left.Direction().Length() == 0) 
     139  { 
     140    intersection_point = left.Support(); 
     141    return right.GetClosestPoint(intersection_point) == intersection_point ? tIntersectionType::SINGLE : tIntersectionType::NONE; 
     142  } 
     143  if (right.Direction().Length() == 0) 
     144  { 
     145    intersection_point = right.Support(); 
     146    return left.GetClosestPoint(intersection_point) == intersection_point ? tIntersectionType::SINGLE : tIntersectionType::NONE; 
     147  } 
     148 
    138149  if (left.Direction() == right.Direction() || left.Direction() == -right.Direction()) 
    139150  { 
    140     if (left.GetClosestPoint(right.Support()) == right.Support()) 
     151    if (left.tLine<Tdimension, TElement>::GetClosestPoint(right.Support()) == right.Support()) 
    141152    { 
    142153      intersection_point = right.Support(); 
     
    168179tIntersectionType IntersectLineWithLineSegment(typename tLine<Tdimension, TElement>::tPoint &intersection_point, const tLine<Tdimension, TElement> &left, const geometry::tLineSegment<Tdimension, TElement> &right) 
    169180{ 
    170   if (!IntersectLineWithLine(intersection_point, left, right)) 
     181  auto intersection_type = IntersectLineWithLine(intersection_point, left, right); 
     182  if (intersection_type == tIntersectionType::INFINITE || intersection_type == tIntersectionType::NONE) 
     183  { 
     184    intersection_point = right.GetClosestPoint(intersection_point); 
     185    return intersection_type; 
     186  } 
     187  return math::IsEqual(right.GetDistanceToPoint(intersection_point), 0) ? tIntersectionType::SINGLE : tIntersectionType::NONE; 
     188} 
     189 
     190template <size_t Tdimension, typename TElement> 
     191tIntersectionType IntersectLineSegmentWithLineSegment(typename tLine<Tdimension, TElement>::tPoint &intersection_point, const tLineSegment<Tdimension, TElement> &left, const tLineSegment<Tdimension, TElement> &right) 
     192{ 
     193  if (!left.BoundingBox().Intersects(right.BoundingBox())) 
    171194  { 
    172195    return tIntersectionType::NONE; 
    173196  } 
    174   return math::IsEqual(right.GetDistanceToPoint(intersection_point), 0) ? tIntersectionType::SINGLE : tIntersectionType::NONE; 
    175 } 
    176  
    177 template <size_t Tdimension, typename TElement> 
    178 tIntersectionType IntersectLineSegmentWithLineSegment(typename tLine<Tdimension, TElement>::tPoint &intersection_point, const tLineSegment<Tdimension, TElement> &left, const tLineSegment<Tdimension, TElement> &right) 
    179 { 
    180   if (!left.BoundingBox().Intersects(right.BoundingBox())) 
    181   { 
    182     return tIntersectionType::NONE; 
    183   } 
    184  
    185   if (!IntersectLineWithLineSegment(intersection_point, left, right)) 
    186   { 
    187     return tIntersectionType::NONE; 
     197 
     198  auto intersection_type = IntersectLineWithLineSegment(intersection_point, left, right); 
     199  if (intersection_type == tIntersectionType::NONE || intersection_type == tIntersectionType::INFINITE) 
     200  { 
     201    intersection_point = left.GetClosestPoint(intersection_point); 
     202    return intersection_type; 
    188203  } 
    189204  return math::IsEqual(left.GetDistanceToPoint(intersection_point), 0) ? tIntersectionType::SINGLE : tIntersectionType::NONE; 
  • tests/geometry.cpp

    r82 r84  
    7474  RRLIB_UNIT_TESTS_BEGIN_SUITE(TestGeometry); 
    7575  RRLIB_UNIT_TESTS_ADD_TEST(LineSegmentBoundingBoxIntersectionTest); 
     76  RRLIB_UNIT_TESTS_ADD_TEST(OverlappingLineIntersections); 
     77  RRLIB_UNIT_TESTS_ADD_TEST(DegradedLineIntersections); 
    7678  RRLIB_UNIT_TESTS_END_SUITE; 
    7779 
    7880private: 
    79  
    80   virtual void InitializeTests() override 
    81   { 
    82   } 
    83  
    84   virtual void CleanUp() override 
    85   { 
    86   } 
    8781 
    8882  template <size_t Tdimension, typename TElement> 
     
    109103  void LineSegmentBoundingBoxIntersectionTestHelper(double x) 
    110104  { 
     105    { 
     106      tLine2D line1(tPoint2D(0, 0), tPoint2D(0, 1)); 
     107      tLine2D line2(tPoint2D(0, 0.5), tPoint2D(0, 0.6)); 
     108      tLine2D line3(tPoint2D(0, 0.5), tPoint2D(0, 0.5)); 
     109      tLineSegment2D line_segment1(tPoint2D(0, 0), tPoint2D(0, 1)); 
     110      tLineSegment2D line_segment2(tPoint2D(0, 0.5), tPoint2D(0, 0.6)); 
     111      tLineSegment2D line_segment3(tPoint2D(0, 0.5), tPoint2D(0, 0.5)); 
     112      tPoint2D intersection; 
     113      RRLIB_UNIT_TESTS_EQUALITY(tIntersectionType::INFINITE, line1.GetIntersection(intersection, line2)); 
     114      RRLIB_UNIT_TESTS_ASSERT(intersection.X() == 0); 
     115      RRLIB_UNIT_TESTS_EQUALITY(tIntersectionType::INFINITE, line2.GetIntersection(intersection, line1)); 
     116      RRLIB_UNIT_TESTS_ASSERT(intersection.X() == 0); 
     117      RRLIB_UNIT_TESTS_EQUALITY(tIntersectionType::INFINITE, line1.GetIntersection(intersection, line_segment2)); 
     118      RRLIB_UNIT_TESTS_ASSERT(intersection.X() == 0 && intersection.Y() >= 0.5 && intersection.Y() <= 0.6); 
     119      RRLIB_UNIT_TESTS_EQUALITY(tIntersectionType::INFINITE, line_segment2.GetIntersection(intersection, line1)); 
     120      RRLIB_UNIT_TESTS_ASSERT(intersection.X() == 0 && intersection.Y() >= 0.5 && intersection.Y() <= 0.6); 
     121      RRLIB_UNIT_TESTS_EQUALITY(tIntersectionType::INFINITE, line_segment1.GetIntersection(intersection, line2)); 
     122      RRLIB_UNIT_TESTS_ASSERT(intersection.X() == 0 && intersection.Y() >= 0 && intersection.Y() <= 1); 
     123      RRLIB_UNIT_TESTS_EQUALITY(tIntersectionType::INFINITE, line2.GetIntersection(intersection, line_segment1)); 
     124      RRLIB_UNIT_TESTS_ASSERT(intersection.X() == 0 && intersection.Y() >= 0 && intersection.Y() <= 1); 
     125      RRLIB_UNIT_TESTS_EQUALITY(tIntersectionType::INFINITE, line_segment1.GetIntersection(intersection, line_segment2)); 
     126      RRLIB_UNIT_TESTS_ASSERT(intersection.X() == 0 && intersection.Y() >= 0.5 && intersection.Y() <= 0.6); 
     127      RRLIB_UNIT_TESTS_EQUALITY(tIntersectionType::INFINITE, line_segment2.GetIntersection(intersection, line_segment1)); 
     128      RRLIB_UNIT_TESTS_ASSERT(intersection.X() == 0 && intersection.Y() >= 0.5 && intersection.Y() <= 0.6); 
     129 
     130      RRLIB_UNIT_TESTS_EQUALITY(tIntersectionType::SINGLE, line1.GetIntersection(intersection, line3)); 
     131      RRLIB_UNIT_TESTS_EQUALITY(line3.Support(), intersection); 
     132      RRLIB_UNIT_TESTS_EQUALITY(tIntersectionType::SINGLE, line3.GetIntersection(intersection, line1)); 
     133      RRLIB_UNIT_TESTS_EQUALITY(line3.Support(), intersection); 
     134      RRLIB_UNIT_TESTS_EQUALITY(tIntersectionType::SINGLE, line1.GetIntersection(intersection, line_segment3)); 
     135      RRLIB_UNIT_TESTS_EQUALITY(line_segment3.Support(), intersection); 
     136      RRLIB_UNIT_TESTS_EQUALITY(tIntersectionType::SINGLE, line_segment3.GetIntersection(intersection, line1)); 
     137      RRLIB_UNIT_TESTS_EQUALITY(line_segment3.Support(), intersection); 
     138      RRLIB_UNIT_TESTS_EQUALITY(tIntersectionType::SINGLE, line_segment1.GetIntersection(intersection, line3)); 
     139      RRLIB_UNIT_TESTS_EQUALITY(line3.Support(), intersection); 
     140      RRLIB_UNIT_TESTS_EQUALITY(tIntersectionType::SINGLE, line3.GetIntersection(intersection, line_segment1)); 
     141      RRLIB_UNIT_TESTS_EQUALITY(line3.Support(), intersection); 
     142      RRLIB_UNIT_TESTS_EQUALITY(tIntersectionType::SINGLE, line_segment1.GetIntersection(intersection, line_segment3)); 
     143      RRLIB_UNIT_TESTS_EQUALITY(line_segment3.Support(), intersection); 
     144      RRLIB_UNIT_TESTS_EQUALITY(tIntersectionType::SINGLE, line_segment3.GetIntersection(intersection, line_segment1)); 
     145      RRLIB_UNIT_TESTS_EQUALITY(line_segment3.Support(), intersection); 
     146    } 
    111147    { 
    112148      tBoundingBox<2, double> box; 
     
    143179    } 
    144180  } 
     181 
     182  void OverlappingLineIntersections() 
     183  { 
     184    tLine2D line1(tPoint2D(0, 0), tPoint2D(0, 1)); 
     185    tLine2D line2(tPoint2D(0, 0.5), tPoint2D(0, 0.6)); 
     186    tLineSegment2D line_segment1(tPoint2D(0, 0), tPoint2D(0, 1)); 
     187    tLineSegment2D line_segment2(tPoint2D(0, 0.5), tPoint2D(0, 0.6)); 
     188    tPoint2D intersection; 
     189 
     190    RRLIB_UNIT_TESTS_EQUALITY(tIntersectionType::INFINITE, line1.GetIntersection(intersection, line2)); 
     191    RRLIB_UNIT_TESTS_ASSERT(intersection.X() == 0); 
     192    RRLIB_UNIT_TESTS_EQUALITY(tIntersectionType::INFINITE, line2.GetIntersection(intersection, line1)); 
     193    RRLIB_UNIT_TESTS_ASSERT(intersection.X() == 0); 
     194    RRLIB_UNIT_TESTS_EQUALITY(tIntersectionType::INFINITE, line1.GetIntersection(intersection, line_segment2)); 
     195    RRLIB_UNIT_TESTS_ASSERT(intersection.X() == 0 && intersection.Y() >= 0.5 && intersection.Y() <= 0.6); 
     196    RRLIB_UNIT_TESTS_EQUALITY(tIntersectionType::INFINITE, line_segment2.GetIntersection(intersection, line1)); 
     197    RRLIB_UNIT_TESTS_ASSERT(intersection.X() == 0 && intersection.Y() >= 0.5 && intersection.Y() <= 0.6); 
     198    RRLIB_UNIT_TESTS_EQUALITY(tIntersectionType::INFINITE, line_segment1.GetIntersection(intersection, line2)); 
     199    RRLIB_UNIT_TESTS_ASSERT(intersection.X() == 0 && intersection.Y() >= 0 && intersection.Y() <= 1); 
     200    RRLIB_UNIT_TESTS_EQUALITY(tIntersectionType::INFINITE, line2.GetIntersection(intersection, line_segment1)); 
     201    RRLIB_UNIT_TESTS_ASSERT(intersection.X() == 0 && intersection.Y() >= 0 && intersection.Y() <= 1); 
     202    RRLIB_UNIT_TESTS_EQUALITY(tIntersectionType::INFINITE, line_segment1.GetIntersection(intersection, line_segment2)); 
     203    RRLIB_UNIT_TESTS_ASSERT(intersection.X() == 0 && intersection.Y() >= 0.5 && intersection.Y() <= 0.6); 
     204    RRLIB_UNIT_TESTS_EQUALITY(tIntersectionType::INFINITE, line_segment2.GetIntersection(intersection, line_segment1)); 
     205    RRLIB_UNIT_TESTS_ASSERT(intersection.X() == 0 && intersection.Y() >= 0.5 && intersection.Y() <= 0.6); 
     206  } 
     207 
     208  void DegradedLineIntersections() 
     209  { 
     210    tLine2D line1(tPoint2D(0, 0), tPoint2D(0, 1)); 
     211    tLine2D line2(tPoint2D(0, 0.5), tPoint2D(0, 0.5)); 
     212    tLineSegment2D line_segment1(tPoint2D(0, 0), tPoint2D(0, 1)); 
     213    tLineSegment2D line_segment2(tPoint2D(0, 0.5), tPoint2D(0, 0.5)); 
     214    tPoint2D intersection; 
     215 
     216    RRLIB_UNIT_TESTS_EQUALITY(tIntersectionType::SINGLE, line1.GetIntersection(intersection, line2)); 
     217    RRLIB_UNIT_TESTS_EQUALITY(line2.Support(), intersection); 
     218    RRLIB_UNIT_TESTS_EQUALITY(tIntersectionType::SINGLE, line2.GetIntersection(intersection, line1)); 
     219    RRLIB_UNIT_TESTS_EQUALITY(line2.Support(), intersection); 
     220    RRLIB_UNIT_TESTS_EQUALITY(tIntersectionType::SINGLE, line1.GetIntersection(intersection, line_segment2)); 
     221    RRLIB_UNIT_TESTS_EQUALITY(line_segment2.Support(), intersection); 
     222    RRLIB_UNIT_TESTS_EQUALITY(tIntersectionType::SINGLE, line_segment2.GetIntersection(intersection, line1)); 
     223    RRLIB_UNIT_TESTS_EQUALITY(line_segment2.Support(), intersection); 
     224    RRLIB_UNIT_TESTS_EQUALITY(tIntersectionType::SINGLE, line_segment1.GetIntersection(intersection, line2)); 
     225    RRLIB_UNIT_TESTS_EQUALITY(line2.Support(), intersection); 
     226    RRLIB_UNIT_TESTS_EQUALITY(tIntersectionType::SINGLE, line2.GetIntersection(intersection, line_segment1)); 
     227    RRLIB_UNIT_TESTS_EQUALITY(line2.Support(), intersection); 
     228    RRLIB_UNIT_TESTS_EQUALITY(tIntersectionType::SINGLE, line_segment1.GetIntersection(intersection, line_segment2)); 
     229    RRLIB_UNIT_TESTS_EQUALITY(line_segment2.Support(), intersection); 
     230    RRLIB_UNIT_TESTS_EQUALITY(tIntersectionType::SINGLE, line_segment2.GetIntersection(intersection, line_segment1)); 
     231    RRLIB_UNIT_TESTS_EQUALITY(line_segment2.Support(), intersection); 
     232  } 
     233 
    145234}; 
    146235 
Note: See TracChangeset for help on using the changeset viewer.