How to return the point of intersection of lines? Lines do not always intersect

Question

Let's say we want to make a function that calculates the intersection point of two lines. The intersection point is always defined or unique. How to reflect this in the function signature?

I came up with the following options:

• bool getIntersectionPoint ( Line& a, Line& b , Point& result );

  Returns false if the lines are parallel. Otherwise, returns true and writes the result to a variable.

• Point getIntersectionPoint ( Line& a, Line& b );

  Throws an exception if the lines are parallel.

[update]
If we make 2 functions bool doLinesIntersect(const Line&, const Line&); and Point twoLinesIntersection(const Line&, const Line&); , the second can be called after the first return false.

Answer 1

IMHO, crossing the lines gives an object, so it would be fair to have

boost::variant<Empty, Point, Line> intersect(Line const & l1, Line const & l2)

and helper functions like

boost::optional<Point> getIntersectionPoint(Line const & l1, Line const & l2)

bool isParallel(Line const & l1, Line const & l2)

Edit: If you do not want to use the boost library, you can easily create simple analogs:

 struct intersection_result_t { enum isec_t { isec_empty, isec_point, isec_line } intersection_result_t() : type_(isec_empty) { new (storage_) Empty(); } intersection_result_t(Empty const & e) : type_(isec_empty) { new (storage_) Empty(e); } intersection_result_t(Point const & p) : type_(isec_point) { new (storage_) Point(p); } ... intersection_result_t(intersection_result_t & ir) : type_(ir.type_) { switch(ir.type_) { case isec_empty: new (storage_) Empty(*static_cast<Empty*>(ir.storage_)); case .... } } private: void destroy() { switch(type_) { case isec_empty: operator delete (static_cast<Empty*>(storage_), storage_); case .... } } private: char storage_[MAX(sizeof(Empty), sizeof(Point), sizeof(Line))]; isec_t type_; }; 

etc. etc. A few more switches are required. Or you can use patterns. For additional use, use initialized_ instead of type_ to track the state of the construct.

Answer 2

As suggested by ulidtko , it would be nice to return an object that "might be a point". In C ++ you can use boost::optional

 boost::optional<Point> getIntersectionPoint(const Line& a, const Line& b) { // ... if (there_is_zero_or_inifinty_points_of_intersection) return boost::optional<Point>(); else return boost::optional<Point>(the_point_of_intersection); } 

You can think of boost::optional<Point> as Point* . In particular, the client may request if the return intersection is the proper point or not in this way:

 boost::optional<Point> point = getIntersectionPoint(a, b); if (point) // point "points to" a proper Point which can be retrieved as *point else // point is "NULL", that is, there no unique point of intersection 

Oddly enough, the motivating example of boost::optional also a geometric problem. This is not a coincidence, as the author of boost::optional , I believe, writes geometric software .; -)

It is worth noting that there is a proposal to include optional in the STL in the next version of the C ++ standard.

Answer 3

Parallel lines are not an error or surprise. Therefore, throwing an exception is not suitable.

BTW is preferred as a function signature.

 bool getIntersectionPoint(const Line& a, const Line& b, Point& result); 

Defining const allows you to understand that the function does not change the first two arguments, and also allows you to call the function with temporary ones.

Answer 4

In terms of abstraction (API), you have two unrelated functions:

 bool doLinesIntersect(const Line&, const Line&); 

and

 Point twoLinesIntersection(const Line&, const Line&); 

The second function is to assume that the lines actually intersect (and are not collinear). If you do not trust your subscribers, you may need an exception indicating that the preconditions are not met.

Answer 5

Your second function probably should not return Point & but the value of Point (to whom does it belong?)

Alternatively, there is a third option:

 Point getIntersectionPoint ( Line& a, Line& b, bool* ok ); 

If you specified a NULL pointer for "ok", drop it if there is no intersection, otherwise return false to "ok".

I would suggest that for such a function it is better to avoid exceptions. Non-intersection is not really exceptional, and exceptions really should be reserved for unforeseen circumstances. You can expect disjoint lines.

Use the version that returns bool, or the version with the bool argument, but don't drop it.

EDIT The fourth option, which is often used:

 std::pair<bool, Point> getIntersectionPoint ( Line& a, Line& b ); 

Answer 6

This question is a very good motivation for simpler sum types in C ++.

In a language like Haskell, your function would have the following signature:

 getIntersectionPoint :: Line -> Line -> Maybe Point 

where Maybe Point (function return type) essentially means a type that can have two values: Nothing or Just p , where p is Point .

The presence of such simple types of sums would actually make the question undetectable at all, because all approaches would merge into one.

---

Edit: This answer demonstrates neatly that Boost offers simple sum types. There is boost::optional and boost::variant . Sweet.

Answer 7

Without a context, people will discuss endlessly.

Suppose you want to use a function inside some

 fillWithColor(color c, set_of lines& figure); 

and somehow you use getLinesIntersection for this. If you need to check every call, your code will be useless, but you do not know what to do with the error. Just use this function and let the other person catch the exception.

In another context, you can implement:

 bool doLinesIntersect(const Line&, const Line2&, Point &p); Point getLinesIntersection(const Line&, const Line2&) { Point p; If (! doLinesIntersect(Line, Line2,p) throw …; return p; } 

Both aproach are very relevant !!!