Can Pandas find all the lines that join any pair of **dots** and don't intersect any of the given **lines** without iteration?

Question

Given a properly defined list of dots, and a list of lines:

Can Pandas find all the lines that join any pair of dots and don't intersect any of the given lines without iteration?

Im currently reaching to the solution, as you can see in the image, but I must iterate in the process, and that iteration makes everything painfully slow.

In the image, the list of dots are the drawn color dots, and the list of lines would be the candlesticks. The desired outcome are the black lines.

Although the question aims for a theoretical solution, or conceptual confirmation if its possible or there is no other way than iterations, here is the code Im currently using, in case it helps: http://pastebin.com/4DiKVy26

Answer 1

I don't know Pandas, but I can see what you're trying to do, and yes it can be done faster. I'm going to call the black lines rays for reasons I hope will become clear; in your algorithm, with m dots and n lines, you are finding all m(m-1)/2 rays, then doing 2n comparisons in order to filter them: m*(m-1)*n => cubic in the size of the input. There is a way to make this quadratic in the input.

What you're describing can be solved by a form of raycasting (though simpler because it's in 2d): think of the dots as lights; a source dot can only cast a ray to a target dot if the target is not in the shadow of a line. So we start with a dot, and move to the right over a list of lines and dots that you might illuminate. As we pass by lines, there will be an expanding region of shadow; but at any x value, we only need to know the 2 gradients of the shadow's edge to know if a y value is in shadow. As we pass each line going right, update the gradients of the shadow. As we pass each dot, we check if it lies outside the shadow; if it does we have a ray. Repeat this process for each dot, and you are done. This works out as roughly m*(m-1)/2+m*n calculations, which scales a lot better.