intersection of voronoi diagram with a line

Question

Is there a computationally efficient way to determine the points of intersection of a straight line with all the edges of a given Voronoi tessellation in a rectangular plane area?

Thanks

Answer 1

Once you have your first intersection point, the rest is easy.

Prepare a database of edges: for each edge, list both polygons it belongs to, or say it is the outer edge (and so belongs to one polygon only). In your picture, the lower side of the rectangle would contain 4 edges of 4 different polygons.

Draw your line, find your first intersection point ([0, 0.25] in your picture, not circled). Say it's polygon A. Then the next intersection point (the lowest one circled in your picture) also belongs to A. You find the relevant edge with a binary search through the list of edges of A.

Now you have found the second edge of A, find out which other polygon it belongs to. Then use binary search to find which other edge of that other polygon the line intersects. And so on until you exit your rectangle.