2
$\begingroup$

This question is related to my earlier question, but on rethinking the problem I have come up with another solution that would be also acceptable.

I have three broken lines. Each has a constant gap of length $a$, a constant fill of length $b$ between them, and an offset $c$. Each line is something like $\lbrace t \mid a k < t+c < (a+b)k, k \in \mathbb{Z} \rbrace$ In the diagram below, I have plotted three example lines with respect to $t$.

In the diagram below, the areas where all three lines overlap is highlighted. I am interested in the first $t\ge0$ where this happens (perhaps that can be found from a general form of the lines' intersection). The lines plotted (top to bottom) have constants $a,b,c$ in pixels: $(60,72,-51)$, $(36,12,-4)$, and $(41,17,-18)$. The first $t$ satisfying all three lines is 196, so that would be the answer.

enter image description here

Basically, I'd be looking for the set intersection of the lines, as expressed above. I haven't been able to figure out how to do this. Another way might be to convolve three rectangle waves, and look at the result. Thoughts?

  • 0
    Yes; the lines' $a$, $b$, and $c$ values remain constant. By add, I assume you mean add some equivalent rectangle waves, and find where their sum is first three.2012-08-05

1 Answers 1

0

If the first complete overlap usually comes as early as in your example, you don't have to worry about efficiency. Then you can use a sweep line algorithm: Keep three states with a Boolean value and a time in a priority queue ordered by the times; in each step take the upcoming item from the queue and flip its Boolean value; if all three Boolean values are true, terminate; else add either the gap or the fill length to the item, depending on its Boolean value, and insert it back into the queue.

  • 0
    I'd like the idea, but unfortunately the first complete overlap could be very distant--in fact infinite, so efficiency is pretty important.2012-08-05