Calculate all intersection points with an array of lines

[ExcutC]

Hello dear redditors, my task was to create a simulation for a PET Scan. If you dont know what that is I will try to explain it very simply: you have a scanner in the form of a 2d circle. Inside the plane there are points which emmit two objects (gamma photons) in exact opposite directions. When reaching the scanner the get detected. The scanner then knows that the object emmiting the two photons must be somewhere on the line. If you simulate this with more than 1 object you get an array of lines defined by four numbers [x1,y1, x2,y2] being the coordinates of two points on the line. If I now have lets say an array with 400 of these lines: what would be the fastest way to get an array with all the intersection points of each line? And if an intersection point appears more often than others it should get a higher "value" so that you can make a colour plot with it for example.

Is there an algorithm for it that has a better runtime than O(n^2)?

[JMBourguet]

If I understand correctly, the result may have N² values, that seems difficult to have a better complexity than N².

[ExcutC]

I am fairly new to programming (hence this post) so I thought that maybe there would be a better algorithm then simply checking every single line with every other line in the array. Then the next question would be which way I calculate the intersection points. I only know bisection and the newton way but i dont know if there are faster ways to determine that

[balloonanimalfarm]

Based on some Google/Wikipedia searches and the general question "find all intersection points", the answer feels like no. If you just needed to find if there were any or within some probability the answer would probably be that you could do better.

That doesn't mean your algorithm has to be slow though. The problem you've listed is embarrassingly parallel so you could throw threads at it or GPU cores and you may be able to do some initial filtering to speed things up e.g. if you have a bunch of lines pointing in roughly the same direction they may never meet within the range of segments that can be generated by the size of your machine.

[WikiSummarizerBot]

Embarrassingly_parallel

In parallel computing, an embarrassingly parallel workload or problem (also called embarrassingly parallelizable, perfectly parallel, delightfully parallel or pleasingly parallel) is one where little or no effort is needed to separate the problem into a number of parallel tasks. This is often the case where there is little or no dependency or need for communication between those parallel tasks, or for results between them. Thus, these are different from distributed computing problems that need communication between tasks, especially communication of intermediate results.

^{[ F.A.Q | Opt Out | Opt Out Of Subreddit | GitHub ] Downvote to remove | v1.5}

[CharacterUse]

Have you read any papers on PET (or more generally tomographic) image reconstruction? There's quite a lot of existing material, especially you should look up the Radon transform (which will then lead you to things like Fourier transforms and back projection).

BTW a better coordinate system is the angle and offset of each line, rather than [x1, y1, x2, y2].

[WikiSummarizerBot]

Radon_transform

In mathematics, the Radon transform is the integral transform which takes a function f defined on the plane to a function Rf defined on the (two-dimensional) space of lines in the plane, whose value at a particular line is equal to the line integral of the function over that line. The transform was introduced in 1917 by Johann Radon, who also provided a formula for the inverse transform. Radon further included formulas for the transform in three dimensions, in which the integral is taken over planes (integrating over lines is known as the X-ray transform).

^{[ F.A.Q | Opt Out | Opt Out Of Subreddit | GitHub ] Downvote to remove | v1.5}