wholecell.utils.voronoi_plot_main

Plot voronoi diagram

Algorithm Reference: A. Nocaj and U. Brandes, “Computing voronoi Treemaps: Faster, Simpler, and Resolution-independent, Computer Graphics Forum, vol. 31, no. 31, pp. 855-864, 2012. Available: 10.1111/j.1467-8659.2012.03078.x.

This program generate a voronoi diagram, in which the canvas of a plot is divided in to n polygons. Each data point (or “Points” in this program) corresponds to one polygon, and the centroid of each polygon is called a “site”. The area of each polygon is proportional to the value each point wants to represent. For example, it can be the mass compositions of a cell, the relative abundance of different proteins, or the energy cost of different cellular processes.

Dividing a canvas (in this program we use np.array([[0,0],[4,0],[4,4],[0,4]])) into multiple polygons is a complicated computational geometry problem. The main working horse of this task is the function “_voronoi_treemap”. In “_voronoi_treemap”, we did the following things: (1) initialize random sites within the canvas (using “random_points_in_canvas”) and assign an initial weight to each site. The initial weights of each site are set equal so that it will be easier to compute a draft. (2) compute the draft of our voronoi diagram, which is called “Power Diagram” following the notation of our algorithm reference. (using “_compute_power_diagram”) (3) adjust the positions of each site and the weights of each site until the program reaches the maximum iterations (i_max = 75) or until error < err_thres. (4) return the final error of the whole voronoi diagram.

In voronoi diagram, certain amount of error in area representation is expected. According to the analysis in our algorithm reference, an error between 5~23% is expected. However, an error up to 20% can severely distort the diagram. We therefore set a stricter limit (15%) on our error in the function “_voronoi_main_function”. If the newly computed voronoi diagram has a lower error compared to the previous one, it will continuously increase the number of iterations until the error falls below 15%. However, if the error of a newly computed diagram is greater than the previous one, the program will plot the diagram all over again. Generally, a final error <=10% will give you a nice representation.

Using this algorithm, the program is capable of dividing 32 polygons in 10 seconds, and the program scales with O(n*log(n)). As a result, it would be preferable to introduce layered structure if the number of polygons are more than 50.

If you want to implement the functions that are created here and make a new voronoi plot with your own data, please read the following instructions: (1)Place this in the heading, or other ways that can import every function in this file. from wholecell.utils.voronoiPlotMain import VoronoiMaster

(2)Copy the following code and modify it appropriately: vm = VoronoiMaster() vm.plot(“YOUR DICTIONARY”, title = “YOUR TITLE”) exportFigure(plt, plotOutDir, plotOutFileName, metadata) plt.close(“all”)

class wholecell.utils.voronoi_plot_main.LineClass(x_col, y_col, weights)

Bases: object

A line object store the information of a line in this format of “dx + ey = f”, using formula: 2(x1-x2)x + 2(y1-y2)y = (x1^2+y1^2-w1) - (x2^2+y2^2-w2)

find_intersect_with_canvas(canvas_obj)

This function finds the intersection points of a bisector with a canvas.

class wholecell.utils.voronoi_plot_main.PolygonClass(xy)

Bases: object

A polygon object stores the coordinates of the corners, the edges, and the area of the polygon.

_polygon_area(corners)

Calculate polygon area using shoelace formula. Please make sure that the corners are reordered before calling _polygon_area function!

find_min_dist_to_border(site)

find the minimum distance of the site to the borders of its polygon.

point_is_within_canvas(p)

Check if a point is within canvas by computing the sum of the angle formed by adjacent corners and the point. If a point is within canvas, the sum of the angle should be 2*pi.

random_points_in_canvas(n_points)

This function assigns n random points within the canvas. The algorithm is as followed: (1) divide the canvas into multiple triangels (2) weight each triangle according to the area (3) randomly placed points within the triangles Please make sure that the points have been reordered properly!

class wholecell.utils.voronoi_plot_main.RayClass(origin, tangent, main_sites, adjunct_site)

Bases: object

A ray object stores the origin and the tangent vector of a ray, and the site it represents. It is store in this format: ~ origin + a*tangent, a>=0 ~ a_r*x + b_r*y + c_r = 0 ~ t_y*x - t_x*y + (t_x*y_int - t_y*x_int) = 0

find_ray_intersect_with_canvas(canvas_obj)

This function finc the point where a ray object is intersected with canvas by checking the intersection with every edge of the canvas.

find_ray_intersect_with_canvas_and_ipoints(canvas_obj, ipoints, simplices_prune)

This function finds the terminal of each ray object.

is_on_ray(p)

Determine whether a point is on a ray by checking if Ax+By-C == 0 and its relative position with respect to the origin is on the same direction as the tangent vector of the ray.

keep_nearest_point_on_ray(intersect_coordinates)

If a ray is intersect with multiple ipoints, only keep the one that is closest to the origin of the ray.

ray_intersect_with_edge(edge_canvas)

This function determines if a ray is intersected with an edge.

class wholecell.utils.voronoi_plot_main.VoronoiClass(polygons, sites, weights, values, canvas_obj)

Bases: object

A voronoi object stores all the polygons of a voronoi diagram, the coordinates/weights/values of each site, and the canvas of the whole plot.

adapt_positions_weights()

Adapt the positions and weights of each site within an existing voronoi diagram. This algorithm also considers the point with largest Area_{target}/Area_{current} ratio and displace its neighbor in order to speed up the optimization process.

adapt_weights()

Adapt the weight of each site. increase the weight if current area is different from the targeted area of each site. However, if the weight is too big such that the site is encroaching its neighbor, the weight should be decreased.

compute_error()

compute the error of the voronoi plot. The error is defined as sum(abs(Area_current - Area_target))/(2*Area_canvas)

find_sites_causing_displacement()

If a site need to expand its area greatly in the next round, the other sites surrounding it should be displaced a little bit in order to facilitate the process of optimizing the voronoi diagram. This is part of the speed-up heuristic.

class wholecell.utils.voronoi_plot_main.VoronoiMaster(i_max=75, err_thres=1e-06)

Bases: object

_add_labels(label_site_list, font_size, ax)

Create the label of the Voronoi plot.

_compute_boundaries(dic, side_length=(4, 4), custom_shape_vertices=None, voronoi_list_old=None)

Main function used for computing layered voronoi diagram based on existing voronoi diagram to ensure the location of each block stays the same.

Parameters:

• dic (dict)

• side_length (tuple[int, int])

_compute_error(polygon_value_list, total_value, total_area)

compute the gross error of the Voronoi plot.

_compute_power_diagram(canvas_obj, sites, weights, values)

Compute the draft of the voronoi diagram, or the power diagram following the nomeclature of our code reference. This function seperate the cases for n = 2, 3, 4 and above. For n = 2, since there should always be a solution, the function will rescue itself by resetting the initial sites until a solution is found.

_divide_polygons(sites, canvas_obj, args)

Parameters:

canvas_obj (PolygonClass)

_find_bisector_positive_ray(sites, weights, site_label, canvas_obj)

This function is designed for n=3. This function compute the 3 bisectors among 3 sites, find the intersect point (ipoint) of these 3 bisectors, and define the positive direction of each ray.

_find_multiple_positive_ray(sites, ipoints, simplices_prune)

This function is designed for n>=4. This function define the positive direction of each ray in a way that is the same as _find_bisector_positive_ray.

_find_total(val)

Find the total value within a number or nestable dictionary.

Parameters:

val (int | float | dict)

Return type:

float

_generate_plot(voronoi_list, ax, counter=0)

Generate the layered voronoi diagram.

_point_is_within_triangle(p, triangle)

Check if a point is within a triangle. The algorithm used is the same as point_is_within_canvas. However, this function does not require the input to be a POLYGON object.

_prune_and_convert_to_ipoints(dual_sites, simplices, canvas_obj)

This function determines which ipoints should be kept. Only the ipoints that (1) belong to the lower convex hull and (2) locate within canvas will be kept.

_recompute_power_diagram(voronoi)

the same function as _compute_power_diagram but accept an existing voronoi object as input.

_voronoi_main_function(points, values, canvas_obj, voronoi_old=None)

Call voronoi_treemap to compute the voronoi diagram, with baseline number of iterations = 75. If the computed voronoi diagram has error >= 0.15, increase the iterations to 150 and so on until the error < 0.15. If the error increases after increasing the number of iterations , recompute the whole voronoi diagram all over again.

Please be careful when interpreting the error output. An error between 0.5~0.15 is expected. If the error = 0, that means the whole voronoi diagram is not properly generated.

_voronoi_treemap(canvas_obj, points, values)

The main working horse of the whole function. This function compute the initial voronoi diagram, adapt the location of each site and the weight of each site, re-compute the voronoi diagram, and compute the error of the voronoi diagram. If the error is too high, repeat this process until the error falls below error threshold or the number of iteration exceeds i_max(= 75).

Certain amount of error is intrinsic to this plot. Therefore, blindly increasing the number of maximum iteration does not guarantee a decrease in error.

_voronoi_treemap_recal(voronoi)

Basically the same function as _voronoi_treemap but skip the initialization part. This ensures the new plot is built on previous results and the previous iterations are not wasted.

plot(dic, side_length=(4, 4), custom_shape_vertices=None, font_size=8, title=None, ax_shape=None, chained=None, verbose=False)

Master function of generating layered or non-layered voronoi plot from a dictionary. gross_error = sum_{i} |Area(i) - Expected Area(i)| error_all = sum_{i} |Area(i) - Expected Area(i)|/(2 * total area) The factor 2 in the error formula is to correct the repeated calculation in area error. :param dic: Layered dictionary which contains the labels and the values you

intend to represent in a voronoi diagram. This can be a single dictionary or multiple dictionaries in a nested list. The shape of the list should be the same as the layout of the subplots.

Parameters:

• side_length – The side length of whole voronoi diagram. The whole diagram is defaulted to be rectangular.

• custom_shape_vertices – If you want a custom shaped voronoi diagram, enter the vertices of the voronoi diagram in a nested np array like this: np.array([[0, 0], [4, 0], [4, 1], [1.5, 3], [0, 2]]) The shape of the whole voronoi diagram will then become a pentagon with vertices [0, 0], [4, 0], [4, 1], [1.5, 3], [0, 2].

• font_size – The font size of the labeling on the voronoi diagram.

• title – The title of the plot. This can be a single title or a nested list of titles.

• ax_shape – the shape of the subplot, in (nrows, ncols)

• chained – whether the new subplot should be based on the previous subplot or not.

• verbose – If true, print the magnitude of the error in the areas represented by the plot

Returns:

The error in total area representation.

wholecell.utils.voronoi_plot_main.angle(v1, v2)

wholecell.utils.voronoi_plot_main.is_on_segment(p, edge)

Determine whether a point is on a segment by checking if Ax+By-C == 0 and falls between the two corners which define the edge.