Far out intersection points for lines which are almost parallel

Question

I am plotting a large number of connected edges on a canvas, all of which are arranged in a way that some specific extension to these edges always gives an intersection point with another extended edge. This point is needed for further calculations - it is not relevant in the context of what appears on the canvas. My code works great for the general case, but if the edge's respective extensions go far out, the intersections do not always exist (however, the lines are not parallel) - at least not within the scope of this program. Does anyone have any ideas to improve the precision of this code? I am actually working with BigDecimals later, but for the plotting steps I initially thought it would suffice to use double.

This one extends the edge to both sides:

public Line2D.Double ExteLine(Point2D p, Point2D q){
   double slope, y3, y4;
   slope = (q.getY() - p.getY())/(q.getX() - p.getX());
   y3 = (slope * (100000 - p.getX())) + p.getY();
   y4 = (slope * (-100000 - p.getX())) + p.getY();
   Point2D out1 = new Point2D.Double(100000, y3);
   Point2D out2 = new Point2D.Double(-100000, y4);
   Line2D.Double line = new Line2D.Double(out1, out2);
   return line; }

This one finds the intersection:

public Point2D.Double getIntersectionPoint(Line2D.Double line1, Line2D.Double line2) {
if (! line1.intersectsLine(line2)) { 
  System.out.println("No intersection"); 
  return null;} 
  double s1 = line1.getX1(),
        sp2 = line1.getY1(),
        rx = line1.getX2()-s1,
        ry = line1.getY2()-sp2;
  double qx = line2.getX1(),
        qy = line2.getY1(),
        sx = line2.getX2()-qx,
        sy = line2.getY2()-qy;
  double det = sx*ry - sy*rx;
  if (det == 0) { System.out.println("Det = 0");
    return null;} 
  else {
    double z = (sx*(qy-sp2)+sy*(s1-qx))/det;
    if (z==0 ||  z==1) return null;  
    return new Point2D.Double(
      (double)(s1+z*rx), (double)(sp2+z*ry));
  }
}

Answer 1

Projective geometry using homogeneous coordinates is a nice approach to handle lines which are almost parallel or even completely parallel. Here is a crash course:

• A point (x,y) in the plane will be homogenized to (x,y,1).
• Multiples of that represent the same point, so you might as well write that as (2x,2y,2).
• A line ax+by+c=0 gets represented as (a,b,c).
• A point with homogeneous coordinates p=(x,y,z) lies on the line g=(a,b,c) if and only if their dot product p·g=ax+by+cz is zero. (You probably don't need this, since comparison for equality with doubles is always tricky, but it explains why the other steps work as they do.)
• The line joining two points can be computed as the cross product of their homogeneous coordinates.
• The point of intersection between two lines can also be computed as the cross porduct of the coordinates of these lines.
• Since the above steps always multiply, your double numbers might overflow if you combine several of these. So rescale your vectors from time to time, e.g. multiplying them with some scalar such that their entry with largest absolute value becomes 1 or whatever.
• If you want to draw a point (x,y,z) on the canvas, you compute (x/z,y/z) and draw that.
• If z=0 then the previous step is not possible. This represents a point “at infinity”.
• If x=y=z=0 or a=b=c=0 then the vector does not represent a point resp. a line but instead a degenerate situation. E.g. you tried to compute the line joining a point with itself.

As you can see, this is fairly simple to implement, and what's even better: you don't need any case distinctions, anywhere! For actual drawing stuff, you might want to intersect lines with the boundaries of your canvas, and then use the lines joining these intersections as definition of your graphics primitives.