I have a file that contains the coordinates of two points that make up a line. When I plot these lines, I notice that there are areas where the lines intersect more often. These points are identified as the areas where the yellow patterns are the thinnest on the plot. To make it easier to locate these points accurately, I plot them as a 2D histogram.

However, even with the 2D histogram, it's still a bit challenging to identify these points precisely. Therefore, I am wondering if anyone knows of an algorithm that can be used to find these points where the lines intersect most frequently. Any suggestions or ideas would be greatly appreciated.

Thank you!

enter image description here

  • 3
    $\begingroup$ As far as I understand the question, you are in 2D and you can calculate the point of intersection of each pair of lines (and also identify parallel and lines (no intersection) or identical lines (infinite number of intersections)) and plot those intersections points. Then typical clustering algorithms will give you what you want. E.g. see k-means clustering. $\endgroup$
    – Bort
    Mar 3 at 16:35
  • 1
    $\begingroup$ If you need to rerun this algorithm frequently and have many line segments, you might want to consider something different than the brute force algo stated above for finding all the intersection points. If we say that the number of line segments is $n$ and you think the number of intersections is sufficiently small (ie not proportional to $n^2$) then you could also use the Bentley-Ottmann algorithm which is designed to solve this problem more efficiently in general. Here's a link: en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm $\endgroup$
    – spektr
    Mar 3 at 18:53


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.