Far out intersection points for lines which are almost parallel

Denor

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));
  }
}
MvG

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.

Collected from the Internet

Please contact [email protected] to delete if infringement.

edited at
0

Comments

0 comments
Login to comment

Related

From Dev

Find if lines are parallel, coincident or they intersect. If they intersect, find point of intersection

From Dev

How to find out the intersection of two coplanar lines in C

From Dev

How to find the intersection of two lines given a point on each line and a parallel vector

From Dev

Plot data points with connecting lines but which leave gaps

From Dev

scanline: finding intersection points

From Dev

Points of intersection of vector with cone

From Dev

scanline: finding intersection points

From Dev

Intersection points of series

From Dev

Calculate intersection of points on graph

From Dev

How to find out which remote branch remote HEAD points to?

From Dev

How to find out which changeset introduced the particular code (lines, block)

From Dev

Finding out character 'a' from a file then count the lines in which the character is appeared

From Dev

Getting the intersection points of 2 circles

From Dev

Find the intersection points of 2 segments

From Dev

Find the intersection point of lines drawn

From Dev

Java find intersection of two lines

From Dev

Intersection between two geographic lines

From Dev

Identification of the intersection point of two lines

From Dev

Find intersection of lines in two files

From Dev

Ignore points far away from mean gnuplot

From Dev

Ignore points far away from mean gnuplot

From Dev

Fill UIBezierPath with parallel lines

From Dev

Parallel diagonal lines on background

From Dev

How to make a parallel lines

From Dev

How in google maps v3 set polyline with points which link lines with bold dots

From Dev

tcl - write out new lines/values between specified points (modification to Brad Lanam's code)

From Dev

Intersection of lists which are values in a dictionary

From Dev

Finding two most far away points in plot with many points in Python

From Dev

Matching elements of two lists which are almost the same

Related Related

  1. 1

    Find if lines are parallel, coincident or they intersect. If they intersect, find point of intersection

  2. 2

    How to find out the intersection of two coplanar lines in C

  3. 3

    How to find the intersection of two lines given a point on each line and a parallel vector

  4. 4

    Plot data points with connecting lines but which leave gaps

  5. 5

    scanline: finding intersection points

  6. 6

    Points of intersection of vector with cone

  7. 7

    scanline: finding intersection points

  8. 8

    Intersection points of series

  9. 9

    Calculate intersection of points on graph

  10. 10

    How to find out which remote branch remote HEAD points to?

  11. 11

    How to find out which changeset introduced the particular code (lines, block)

  12. 12

    Finding out character 'a' from a file then count the lines in which the character is appeared

  13. 13

    Getting the intersection points of 2 circles

  14. 14

    Find the intersection points of 2 segments

  15. 15

    Find the intersection point of lines drawn

  16. 16

    Java find intersection of two lines

  17. 17

    Intersection between two geographic lines

  18. 18

    Identification of the intersection point of two lines

  19. 19

    Find intersection of lines in two files

  20. 20

    Ignore points far away from mean gnuplot

  21. 21

    Ignore points far away from mean gnuplot

  22. 22

    Fill UIBezierPath with parallel lines

  23. 23

    Parallel diagonal lines on background

  24. 24

    How to make a parallel lines

  25. 25

    How in google maps v3 set polyline with points which link lines with bold dots

  26. 26

    tcl - write out new lines/values between specified points (modification to Brad Lanam's code)

  27. 27

    Intersection of lists which are values in a dictionary

  28. 28

    Finding two most far away points in plot with many points in Python

  29. 29

    Matching elements of two lists which are almost the same

HotTag

Archive