Add lines to star with fixed coordinates maximizing smallest angle

I have the following problem:

There are existing stars (as in graph-theory stars) with a fixed representation in a 2D coordinate space, meaning that angles between the edges are not allowed to change.

Now I want to add additional edges from the star center. Both the amount of existing edges and the amount of edges to add can vary.

How can the new edges be added in a way that maximizes the smallest angle between edges in the resulting star? For this minimization, the angles between newly added edges, as well as the angles between newly added and existing edges are relevant.

Here are two trivial examples, the black edges are the existing ones, the blue ones the newly added:

However, there could also be more complex examples, consider adding a different amount of edges(1,2,3,..) to this star:

Ideally, the algorithm is fast and easy to implement in object-oriented programming languages.

Background:

The underlying use case is drawing of Hydrogens for 2D Molecule depictions. In a software, a 2D molecule depiction might be loaded from a file or even drawn by a user, then, the user can trigger an action, adding missing Hydrogen atoms to all existing atoms.

For each atom (star), a varying number of hydrogens depending on the atom type and charge (usually 1-3), should be added and drawn in a visually pleasing way.

The existing edges and angles can not be modified, because they are given by the user. Small angles tend to look bad, therefore, the goal is to maximize the smallest angle.

Currently, this is done by choosing the largest angle, then adding an edge in the middle. Then repeating this until no more edges are to be added. This is very fast and looks reasonably well, but obviously doesn't always find the best solution.

I'll describe an efficient algorithm for this problem.

Suppose we have an angle $\theta$, and we want to find out how many new edges we can add, with the constraint that the minimum angle between all pairs of edges must be at least $\theta$. Then it's not too hard to compute this. Pick any adjacent pair of existing edges; suppose they are at angle $\gamma$ from each other. Then you can add $\lfloor \gamma/\theta \rfloor - 1$ new edges between them, while ensuring the minimum angle remains at least $\theta$. So, sort all of the existing edges by angle, iterate through each pair of adjacent existing angles, count how many new edges you can add between them (using the formula in the previous sentence), and add them up. That tells you how many new edges you can add, if you want the minimum angle between edges to be at least $\theta$.

Great. But in your situation, we don't know $\theta$; we just know that we want to add at least $n$ new edges. So, use binary search on $\theta$ to find the largest $\theta$ such that you can add at least $n$ new edges while preserving a minimum angle of at least $\theta$. You can do this by choosing a value of $\theta$, computing how many new edges you can add (using the algorithm of the previous paragraph), then increasing or decreasing $\theta$ according to the rules of binary search based on whether the number of new edges you could add was above or below $n$.

StackExchange Computer Science Q#103941, answer score: 4