Node: Polygon Intersections, Previous: Affine Transformations for Polygons, Up: Polygon Reference


bool_point_pair intersection_points (const Point& p0, const Point& p1) const function
bool_point_pair intersection_points (const Path& p) const function
These functions find the intersections of the Polygon and a line. In the first version, the Point arguments are the end points of the line. The argument to the second version must be a linear Path.

A line and a regular polygon or rectangle1 can intersect at two points at most. Let b be a bool_point_pair returned by intersection_points(). If no intersection points are found, and will be INVALID_POINT, and b.first.b and b.second.b will be false. If a single intersection point is found, the corresponding Point will be stored in If the Point is on the line segment p_0p_1 , b.first.b will be true, otherwise false. If a second intersection point is found, it will be stored in, and b.second.b is set analogously to b.first.b.

When the Point arguments and the Reg_Polygon are coplanar, as in [next figure] , two intersection points are possible. In this case, only intersection points of the line with an edge of the Reg_Polygon are returned in the bool_point_pair.

          Point A(1, 1, 1);
          Reg_Polygon r(origin, 5, 3);
          Transform t;
          t.rotate(15, 12, 11);
          Point P(-2, 0, -1);
          Point Q(2, 0, 1);
          P *= Q *= r *= t;
          bool_point_pair bpp = r.intersection_points(P, Q);
"$f$", "rt");

[Figure 139. Not displayed.]

Fig. 139.

In [next figure] , the lines BC and PQ

are not coplanar with the Reg_Polygon r. In each case, only one intersection point is possible, and it can be either an intersection with an edge of the Reg_Polygon, or lie within its perimeter.

          Point B(r.get_point(3).mediate(r.get_point(4)));
          Point C(B);
          B.shift(0, 2, .5);
          C.shift(0, -2, -.5);
          Point P(-1, -2, -1);
          Point Q(0, 2, 1);
          B *= C *= P *= Q *= r *= t;
          bool_point_pair bpp = r.intersection_points(B, C);
"$i_0$", "rt");
          bpp = r.intersection_points(P, Q);
"$i_1$", "rt");

[Figure 140. Not displayed.]

Fig. 140.

In [next figure] , the intersection point of r with the line PQ

does not lie on the line segment PQ.

          bpp = r.intersection_points(P, Q);
"$i$", "rt");
          cout << "bpp.first.b == " << bpp.first.b << endl << flush;
          -| bpp.first.b == 0

[Figure 141. Not displayed.]

Fig. 141.

vector<Point> intersection_points (const Polygon& r) const function
Finds the intersection points of two Polygons. Let v be the vector<Point> returned by intersection_points(). If the Polygons are coplanar, v will contain the intersection points of the edges of the Polygons, as in [next figure] .
          Rectangle r(origin, 4, 4);
          Reg_Polygon rp(origin, 5, 5, 0, 36);
          rp.shift(0, 0, .25);
          vector <Point> v = r.intersection_points(rp);

[Figure 142. Not displayed.]

Fig. 142.

If the Polygons lie in parallel planes, there can be no intersection points. If they lie in non-parallel, non-coplanar planes, intersection_points() first finds the intersection line of the two planes. Then it finds the intersection points of this line with the two Polygons, if they exist. There can no more than four intersection points, in this case. v[0] and v[1] will be the intersection points of the line with *this, while v[2] and v[3] will be the intersection points of the line with r. If one or more of the intersection points doesn't exist, the corresponding member of v will contain INVALID_POINT as a placeholder.

          Point A(1, 1, 1);
          Rectangle r(A, 4, 4);
          Reg_Polygon p(A, 5, 5);
          p.rotate(90, 30);
          p.shift(2, 0, 3);
          vector <Point> v = r.intersection_points(p);

[Figure 143. Not displayed.]

Fig. 143.

In [next figure] , the Rectangle r and the Reg_Polygon p don't overlap at all, nor does the intersection line of the two planes intersect with p. However, it does intersect with p at the labelled Points.

          Point A(1, 1, 1);
          Rectangle r(A, 4, 4);
          Reg_Polygon p(A, 5, 5);
          p.rotate(90, 30);
          p.shift(4, 3, 3);
          vector <Point> v = r.intersection_points(p);
          int i = 0;
          for (vector<Point>::iterator iter = v.begin();
           iter != v.end(); ++iter)
           iter->dotlabel(i++, "bot");

[Figure 144. Not displayed.]

Fig. 144.


  1. Reg_Polygon and Rectangle are currently the only classes derived from Polygon.