Re: [Boost-users] [Polygon] using polygon for linesegment intersection

Subject: Re: [Boost-users] [Polygon] using polygon for linesegment intersection
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2011-04-26 14:13:14

gast128 wrote:
> I was trying to use the Boost.Polygon library to test for line segment
> intersection. I define 2 polygons (lines) and use the Boolean
> operators of the polygon_set. However it gives an empty result:

A line segment does not a polygon make.  There is an implied edge between the first and last point in a polygon (you can also make it explicit so that the first and last point are the same and the library will accept that also).  In the case of two point the implied edge is the reverse of the edge you specified.  The result is a figure that encloses no area.  A polygon that encloses no area dissapears when it passes through a boolean operation.  That is why your output is empty.  The definition of a polygon is the area inside the boundary.  The boundary itself is neither inside or outside, it is the boundary.  That is why polygons that touch at the boundary are merged because their interiors touch along the common boundary.

> Also the documentation states that the size function gives the number
> of edges, but a line has only 1 edge:
> 
> assert(boost::polygon::size(line1) == 2); //not 1?

The size function actually returns the number of points stored in the polygon.  This may or may not be the number of edges of the polygon.  It would be quite a bit more complicated to answer the question "given the points stored in the polygon currently, how many edges would the enclosed area have?"  In your case it would be zero.

Internally Boost.Polygon has an implementation of line segment intersection, but its interface is an implementation detail and not a documented API.  I want (and need) the ability to change the interface of this algorithm in the future.  As it happens we are about to start a Google Summer of Code project to add line_segment and line_segment_set concepts to the Polygon API.  This will allow you do directly get the line segment intersections by calling intersect on a set of line segments and getting the result back as pairs of intersecting segments populating a vector, for example.  However, it will be at least three months before we can let people start using a beta version of the new API.

To directly do what you want with the current library you can access implementation details used by the Booleans algorithm for general polygons.

If you look in the file details/scan_arbitrary.hpp you will find a function definition:

template <typename iT>
    static inline void validate_scan_divide_and_conquer(std::vector<std::set<Point> >& intersection_points,
                                                        iT begin, iT end)

Inside the class: 

  template <typename Unit>
  class line_intersection : public scanline_base<Unit> 

This function expects an iterator range of:

std::pair<half_edge, segment_id>

Where half_edge is:

typedef std::pair<Point, Point> half_edge;

And segment_id is int and is expected to be the index of the edge into the vector of sets of points intersection_points, which is populated with intersection points found for each edge.

The validate_scan_divide_and_conquer algorithm reports intersection points.  It is used by the function:

template <typename iT>
static inline void validate_scan(std::vector<std::pair<half_edge, int> >& output_segments,
                                     iT begin, iT end)

Which segments the input iterator range into and output vector of non-intersecting line segments with index of the original line segment associated with each.  For coincident input line segments duplicate output line segments with different indices are computed.

The validate_scan function is tested by the built in self test code in the same file:

static inline bool test_validate_scan(stream_type& stdcout) {
      std::vector<std::pair<half_edge, segment_id> > input, edges;
      input.push_back(std::make_pair(half_edge(Point(0, 0), Point(0, 10)), 0));
      input.push_back(std::make_pair(half_edge(Point(0, 0), Point(10, 10)), 1));
      std::pair<segment_id, segment_id> result;
      validate_scan(edges, input.begin(), input.end());
      if(!verify_scan(result, edges.begin(), edges.end())) {
        stdcout << "s fail1 " << result.first << " " << result.second << "\n";
        return false;
      }
        ...

This function is a member of the enclosing class, but shows how to use the functions described above.

These interfaces are not documented and are implementation details.  I may change them in the future, but not before I provide a documented interface to do what you want.

The alternative to accessing implementation details of the library is to use the documented interface for polygon clipping with a trick.  Scale up input line segments by 100 and then bloat them by 10.  Now they are polygons and not line segments.  If you intersect these polygons you get polygons the center of which is your line segment intersection point.  Divide by 100 to get back to original coordinate space.  Since the intersection points will be off the integer grid at that point it is up to you how to handle the scaling, rounding or snapping.

I'm copying the prospective GSOC2011 student on this mail so that he can see how the current interface of the line segment intersection algorithm works.  It is this that he would be wrapping with documented interfaces that are based on new line segment concepts.  He'll also be interested to know that users of the library are asking for the interfaces he will be writing.

I hope this helps.

Thanks,
Luke