How to find cell IDs attached to points

If I have a set of inputs for the Voronoi function, and use the convex hull function to obtain a connectivity list for each Voronoi cell (and its associated center ID), how can I obtain a list for each vertex, and its associated cell IDs?

EX:

clc
clear all
close all

% n= 10;                    % # of elements
% x=10*rand(n,1);
% y=10*rand(n,1);
x=[ 0 1 2 3 4 5 6 7 8 9 10 9 8 7 6 5 4 3 2 1  0];
y=[ 0 0 7 0 9 0 1 0 2 0 1  2 4 2 3 3 2 6 1 10 1];

voronoi(x,y,'-k');        % Voronoi function/plot
axis equal;

X_Final = [x' y'];
[V,C] = voronoin(X_Final);

C gives a set of Cell connectivity IDs indexed with respect to their centers (i.e. (x(1),y(1)) is the center for the cell C{1}). I want to sort of reverse this process, and for each vertex in V find all cells that it is an element of. I plan to do this for thousands of elements, and am struggling with an efficient way to do it.

Answer 1

[Chris Turnes]

One way to solve this problem is to construct a sparse matrix S such that the element S(i,j) is logical true if the vertex V(i,:) is contained in the cell C{j}. Then, to see to which cells a vertex V(i,:) belongs, you could simply type S(i,:) to display the indices. This will also use minimal memory, given that the data size may be very large.

To construct the sparse matrix, as discussed in the documentation, you will need to supply the row and column indices of the elements you wish to set to true, as well as the matrix sizes. The call will then look something like this:

S = sparse(ix, jx, true, size(V, 1), size(C, 1));

The first argument ix is a list of indices of vertices, and the second argument jx is a list of the indices of cells containing those vertices. The last two input arguments give the matrix size.

Using the example you provided, I get:

>> C{1}
ans =
     1     3
>> C{2}
ans =
     8     1     3     4

In this case, the first 6 elements of your arrays ix and jy would be

ix(1:6) == [1 3 8 1 3 4]
jy(1:6) == [1 1 2 2 2 2]

You can construct these two arrays efficiently. First, by making use of comma-separated lists, you can generate the ix array:

ix = [C{:}]';

This concatenates the contents of each cell in C into a single column vector. It is a little trickier to create the jy array, but it is still possible to do so efficiently using the functions cellfun, cumsum, nnz, and arrayfun:

cellLengths = cellfun(@length, C);
cs = cumsum(cellLengths);
jy = arrayfun(@(k) nnz(cs < k), (1:cs(end))) + 1;

These three lines are equivalent to computing jy by

jy = [ones(length(C{1}), 1); ones(length(C{2}), 1); ...]

Once you have these two index arrays, you can create the sparse matrix S and thus determine which cells use which vertices.