In Fortune's algorithm, how can I determine the arc of the beach line that intersects a given vertical line?

Question

I'm trying to implement Fortune's algorithm to construct a Voronoi diagram. I'm having trouble finding the parabola right above a seed point. How can I know which parabola will a vertical line (from the seed point) intersect? I'm using in DeBerg's "Algorithms and Applications" as reference.

Answer 1

This answer provides an answer to part of the OP's inquiry, regarding the implementation of the algorithm.

I'm trying to implement Fortune's algorithm to construct a Voronoi diagram.

The OP wants to know how to make the calculations to make the implementation, so at least with this answer will be able to visualize the diagram and then verify that the calculations (if they are made manually) are correct.

This is a question also suitable for Stack overflow, but I have done a similar question in the past (see here) regarding the properties of the Voronoi diagram, so I am familiar with the methods to implement the algorithm you want.

Basically, nobody codes the calculations manually, you have a lot of programming languages already providing functions to make the process of the algorithm automatically.

In this case you have an example of a easy Python template, feel free to use it and modify it. If you are not familiar with Python, I strongly suggest you to learn it, at least the basic points. It is very helpful! If you are using other programming languages, at least the code will give you an idea of the way you need to write the implementation.

def Voronoi():
    import numpy as np
    import matplotlib.pyplot as plt
    from scipy.spatial import Voronoi, voronoi_plot_2d

    # example of point
    p1x = 0
    p1y = 0
    # This vector will include all the points of your Voronoi diagram
    fullvec = []
    fullvec.append([p1x,p1y])

    # add here as many points as you wish as above

    # convert the list to an numpy array 
    points = np.array(fullvec)

    # use the Voronoi library 
    vor=Voronoi(points)
    voronoi_plot_2d(vor)
    plt.show()

Voronoi()