1

I have some points which illustrates heads of pedestrians during an experiment in each frame. I need to calculate which Voronoi Cells are in specific area - measurement square:

x_range = (-0.4, 0.4)
y_range = (0.5, 1.3)

So I've adapted a sample of generating Voronoi cells from points + I've added measurement area (blue lines) and walls (black), here is result for frame 0:

Frame 0 of drawn Voronoi cells

And here is part of code (adapted from the sample):

entries_for_frame = get_entries_at_frame(entries, frame)
points = points_from_entries(entries_for_frame)

vor = scipy.spatial.Voronoi(points)
scipy.spatial.voronoi_plot_2d(vor)

plt.show()

As I know in order to calculate which cells are inside the measurement area I need to check which lines of cells are crossing with the measurement square or are inside its. So according to the documentation of scipy.spatial.Voronoi the interesting attributes are: vertices, which is returning those orange vertices. I need also to have edges of vertices inside the measurement area, the attribute according to the documentation of scipy.spatial.Voronoi is ridge_vertices, but unfortunately it is returning something strange:

[[0, 19], [0, 2], [1, 17], [1, 3], [2, 3], [17, 19], [-1, 22], [-1, 15], [15, 16], [16, 21], [21, 22], [-1, 0], [2, 23], [22, 23], [28, 32], [28, 29], [29, 30], [30, 31], [31, 32], [12, 13], [12, 28], [13, 25], [25, 29], [-1, 24], [-1, 31], [24, 30], [-1, 26], [26, 27], [27, 32], [-1, 33], [19, 20], [20, 34], [33, 34], [35, 36], [-1, 35], [36, 37], [-1, 37], [-1, 4], [4, 5], [5, 35], [6, 37], [6, 7], [7, 36], [38, 39], [38, 40], [39, 41], [40, 41], [-1, 40], [-1, 8], [8, 38], [-1, 9], [9, 10], [10, 41], [10, 43], [39, 42], [42, 43], [52, 53], [52, 57], [53, 54], [54, 55], [55, 56], [56, 57], [13, 52], [25, 57], [48, 49], [48, 54], [49, 55], [9, 50], [24, 56], [49, 50], [17, 59], [18, 61], [18, 20], [59, 61], [11, 46], [11, 60], [18, 47], [46, 47], [60, 61], [58, 63], [58, 60], [59, 62], [62, 63], [26, 64], [27, 65], [64, 65], [21, 67], [23, 68], [67, 68], [42, 45], [43, 69], [44, 45], [44, 72], [69, 72], [50, 70], [69, 70], [48, 71], [70, 71], [4, 76], [5, 75], [75, 76], [33, 77], [76, 77], [34, 78], [77, 78], [47, 79], [78, 79], [80, 82], [80, 81], [81, 83], [82, 84], [83, 84], [14, 53], [14, 80], [71, 82], [72, 84], [14, 51], [51, 87], [81, 85], [85, 87], [88, 90], [88, 89], [89, 93], [90, 91], [91, 92], [92, 93], [44, 88], [83, 89], [85, 86], [86, 93], [11, 91], [58, 92], [94, 95], [94, 97], [95, 96], [96, 98], [97, 99], [98, 99], [12, 94], [51, 95], [65, 97], [101, 104], [101, 102], [102, 103], [103, 105], [104, 105], [15, 101], [16, 104], [64, 102], [99, 103], [66, 67], [66, 105], [1, 106], [3, 107], [106, 107], [68, 108], [107, 108], [8, 73], [45, 109], [73, 110], [109, 110], [111, 115], [111, 113], [112, 113], [112, 114], [114, 115], [46, 74], [74, 111], [79, 113], [75, 112], [7, 114], [116, 117], [116, 118], [117, 120], [118, 119], [119, 121], [120, 121], [96, 118], [98, 100], [100, 116], [87, 119], [86, 121], [63, 120], [122, 127], [122, 123], [123, 124], [124, 125], [125, 126], [126, 127], [100, 127], [117, 122], [62, 123], [106, 124], [108, 125], [66, 126], [128, 129], [128, 130], [129, 132], [130, 131], [131, 133], [132, 134], [133, 134], [90, 128], [109, 129], [74, 130], [110, 132], [115, 131], [6, 133], [73, 134]]

In documentation I don't see how to understand returned numbers. Also in tutorials in explaining how to solve my problem. So my question is: how to calculate which Voronoi cells are inside the measurement area with at least single point?

baziorek
  • 2,502
  • 2
  • 29
  • 43
  • Have you looked at [the source for voronoi_plot_2d](https://github.com/scipy/scipy/blob/master/scipy/spatial/_plotutils.py#L231-L261)? It looks like the `ridge_vertices` with negative indices denote infinite cells. – AKX Dec 05 '21 at 19:44

1 Answers1

2

I believe that your best bet is to use some kind of multiple polygon intersection algorithm using the cell vertices to describe the polygons.

You can whittle down the number of polygons by discarding those whose rightmost vertex is left of the blue rectangle, those whose leftmost vertex is to the right, and so on for up and down. This leaves you with the yellow polygons only.

You can also quickly eliminate (only, in this case you mark them as "intersecting") all those whose center or vertex lies inside the rectangle. This also is very quick.

In this example this is enough to locate all cells.

In other cases (for example, in the figure below, if the bottom-left yellow cell was shifted slightly upwards) you will have cells that have all vertices and the Delaunay center outside the rectangle, and yet one edge crosses it, so there is an intersection. To recognize those, you can exploit the fact that a rectangle is a convex figure, and check whether, among the cells you've left, there is one that contains at least one of the rectangle's corners. This is a slightly more complex check ("whether a point lies inside a convex polygon"), but not too complex since the cell is also convex and can be trivially decomposed in triangles.

enter image description here

The pseudo algorithm would be:

  • for all Voronoi cells:
    • get list of vertices.
    • are they all left/below/above/right of the rectangle?
    • YES: this cell does not intersect. Continue.
    • for all the vertices plus the cell center:
      • is this point inside the rectangle?
      • YES: we have intersection. Report this cell and continue.
    • decompose the cell in a list of triangles with vertex in the Delaunay center, taking ordered vertex pairs.
    • for each triangle
    • this cell does not intersect the rectangle.
LSerni
  • 55,617
  • 10
  • 65
  • 107