Voronoi diagram based on midpoints of lines

Question

I have 9 unmovable nodes (green). Between these nodes there is a network of lines. There could be three lines between the same two nodes, 2 of them could be straight lines going from Node 1 to Node 2, while some have a control point which is a middle point where the line changes the slope.

I want to create a Voronoi diagram such that the lines have equal distances to the nearest node and the Voronoi edges have to be perpendicular to the nodes.

Black lines show the voronoi cells from using from scipy.spatial import Voronoi, voronoi_plot_2d.

All orange markers are middle points of a specific line.

If you go from the top left, there are two orange markers that have a Voronoi edge going through them. But the next one is in the middle of Cell 2 (labeled with question marks), and I am not sure how to treat it.

In the next image I added perpendicular bisectors (purple):

I have tried using script.spatial library by inputing nodes_positions or midpoints but I got complete nonsense. Is there a library that would help me solve this or do I need to do it manually? How do I achieve all of this?

I would appreciate any help.