Efficient maths algorithm to calculate intersections

by

Most of the answers already here seem to follow the general idea that:

  1. find the intersection of two straight lines passing the given points.
  2. determine if the intersection belong to both line segments.

But when intersection does not occur often, a better way probably is to reverse these steps:

  1. express the straight lines in the form of y = ax + b (line passing A,B) and y = cx + d (line passing C,D)
  2. see if C and D are on the same side of y = ax+b
  3. see if A and B are on the same side of y = cx+d
  4. if the answer to the above are both no, then there is an intersection. otherwise there is no intersection.
  5. find the intersection if there is one.

Note: to do step 2, just check if (C.y – a(C.x) – b) and (D.y – a(D.x) – b) have the same sign. Step 3 is similar. Step 5 is just standard math from the two equations.

Furthermore, if you need to compare each line segment with (n-1) other line segments, precomputing step 1 for all lines saves you time.

More Related Contents:

  1. Circle-circle intersection points
  2. How to calculate the index (lexicographical order) when the combination is given
  3. Calculate distance between two latitude-longitude points? (Haversine formula)
  4. Unique (non-repeating) random numbers in O(1)?
  5. How to determine if a point is in a 2D triangle? [closed]
  6. How do I calculate a point on a circle’s circumference?
  7. Algorithm to find Largest prime factor of a number
  8. Fast permutation -> number -> permutation mapping algorithms
  9. nth fibonacci number in sublinear time
  10. How to make rounded percentages add up to 100%
  11. Writing your own square root function
  12. Sort points in clockwise order?
  13. How do you calculate the average of a set of circular data? [closed]
  14. Efficiency of purely functional programming
  15. Finding out nth fibonacci number for very large ‘n’
  16. Algorithm for finding similar images
  17. Why does this simple shuffle algorithm produce biased results?
  18. Computing set intersection in linear time?
  19. Floating Point Divider Hardware Implementation Details
  20. Time complexity of Sieve of Eratosthenes algorithm
  21. Unsupervised clustering with unknown number of clusters
  22. How do I find a factorial? [closed]
  23. Calculating the position of points in a circle
  24. Strategies for simplifying math expressions
  25. How to express tetration function, for complex numbers
  26. An inverse Fibonacci algorithm?
  27. How to check if an integer is a power of 3?
  28. Optimized low-accuracy approximation to `rootn(x, n)`
  29. How can I perform Collision Detection on rotated rectangles? [closed]
  30. Fastest way to get the integer part of sqrt(n)?

Leave a Comment