Node:Intersections, Next:, Previous:Pictures, Up:Top



Intersections

There are no functions for finding the intersection points of two (or more) arbitrary Paths. This is impossible, so long as 3DLDF outputs MetaPost code. 3DLDF only "knows" about the Points on a Path; it doesn't actually generate the curve or other figure that passes through the Points, and consequently doesn't "know" how it does this.

In addition, an arbitrary Path can contain connectors. In 3DLDF, the connectors are merely strings and are written verbatim to the output file, however, in MetaPost they influence the form of a Path.

3DLDF can, however, find the intersection points of some non-arbitrary Paths. So far, it can find the intersection point of the following combinations of Paths:

  1. Two linear Paths, i.e., Paths for which Path::is_linear() returns true (see Path Reference; Querying). In addition, the static Point member function Point::intersection_points() can be called with four Point arguments. The first and second arguments are treated as the end points of one line, and the third and fourth arguments as the end points of the other.
  2. A line and a Polygon. Currently, Reg_Polygon and Rectangle are the only classes derived from Polygon.
  3. Two Polygons.
  4. A line and a Regular Closed Plane Curve (Reg_Cl_Plane_Curve, see Regular Closed Plane Curve Reference; Intersections). Currently, Ellipse and Circle are the only classes derived from Reg_Cl_Plane_Curve.
  5. Two Ellipses. Since a Circle is also an Ellipse, one or both of the Ellipses may be a Circle. See Ellipse Reference; Intersections.

Adding more functions for finding the intersections of various geometric figures is one of my main priorities with respect to extending 3DLDF.

There are currently no special functions for finding the intersection points of a line and a Circle or two Circles. Since the class Circle is derived from class Ellipse, Circle::intersection_points() resolves to Ellipse::intersection_points(), which, in turn, calls Reg_Cl_Plane_Curve::intersection_points(). This does the trick, but it's much easier to find the intersections for Circles that it is for Ellipses. In particular, the intersections of two coplanar Circles can be found algebraically, whereas I've had to implement a numerical solution for the case of two coplanar Ellipses with different centers and/or axis orientation. It may also be worthwhile to write a specialization for finding the intersection points of a Circle and an Ellipse.

The theory of intersections is a fascinating and non-trivial branch of mathematics.1 As I learn more about it, I plan to define more classes to represent various curves (two-dimensional ones to start with) and functions for finding their intersection points.


Footnotes

  1. The books on computer graphics and the fairly elementary mathematics books that I own or have referred to don't go into intersections very deeply. One that does is Fischer, Gerd. Ebene Algebraische Kurven, which is a bit over my head.