1

I deal with plots of data on the order of half a million points in Octave. I am trying to find the center of empty spaces that are in the data (on purpose).

I know how many points to look for and I was thinking of feeding in starter locations and then try to expand a circle in one direction until you hit valid data point locations and keep doing that in a few directions until you have a circle that is filled with no data but touches valid data points. The center of that circle would be the center of the void space. I'm not entirely sure how to write that since I'm very green in coding.

Obviously a graphical solution probably isn't the best method, but I don't know how to find big x and y gaps in a huge matrix of x y locations.

A section of the data I deal with. Trying to write a program to automatically find the center of that hole.

A sample of the data I'm working with. Each data point is an x and y location with a z height that isn't really valuable to what I'm trying to solve here. The values do not line up in consistent intervals

Here is a large sample of what I'm working with

mhotkow
  • 11
  • 2
  • (is this actually a scatter plot or a sparse matrix?) – Tasos Papastylianou May 28 '21 at 11:43
  • I believe a sparse matrix would imply I have x y locations that are valued empty which I do not. My data does not line up in straight lines in either x or y. I'm going to attempt to add another image with a sample of the data. – mhotkow May 28 '21 at 20:14
  • 1
    Does this answer your question? [Fitting largest circle in free area in image with distributed particle](https://stackoverflow.com/questions/42806059/fitting-largest-circle-in-free-area-in-image-with-distributed-particle) (I'm not sure if Octave has all the same functionality as MATLAB for this purpose.) – Cris Luengo Jun 01 '21 at 22:12
  • This is very helpful @CrisLuengo! Sadly, it looks like matlab's circumcenter is more robust than Octave's, but I think I'm nearing a solution. Thank you. – mhotkow Jun 03 '21 at 15:14
  • I have written more functions and done some checks and I'm very close to a permanent solution. I think I have a solution good enough for now. I may attempt to post it later. For now, I end with a n X 3 matrix of circle coordinates and radii that fill inside of my data holes fairly nicely. I need to find out how to get a unique circle for each local region, and the best positioned circle at that. Thank you @CrisLuengo and Tasos! – mhotkow Jun 03 '21 at 20:24

1 Answers1

1

I know you said your data does not line-up in x or y, but it still seems suspiciously grid-like.

In this case, you can probably express each gridpoint as a 'pixel' in an image; this gives you access to excellent functions you can use from the image package, such as the imregionalmin function. This will give you connected components of 'holes', in your case. For each component you can find their centres of mass easily by finding the 'average coordinate' over the pixels within that component. You can then perform a distance transform (e.g. using bwdist) to find the exact radius for the circle you describe, as the distance from that centre of mass to the nearest pixel. Alternatively, you can start with bwdist and then use immaximas to detect the centres of mass directly. If you have multiple such regions, you can use bwconncomp to find connected components first (or over the output of imregionalmin).

If your data is not specifically grid-like, then you could probably interpolate your data to make them fit such a grid.

Example:

pkg load image
t = 0 : 0.1 : 2 * pi;   % for use when plotting circles later

[X0, Y0] = ndgrid( 1:100, 1:100 );               % Create 'index' grid    
X = X0 - 0.25 * Y0;   Y = 0.25 * X0 + Y0;        % Create transformed grid
Z = 0.5 * (X0 - 50) .^ 2 + (Y0 - 50) .^ 2 > 250; % Assign a logical value to each 'index' point on grid

M = imregionalmin ( Z );                        % Find 'hole' as mask
C = { round(mean(X0(M))), round(mean(Y0(M))) }; % Find centre of mass (as index)

R = bwdist( ~M )(C{:});    % Find distance from centre of mass to nearest pixel
R = min( abs( X(C{1}+R, C{2}) - X(C{:}) ), abs( Y(C{1}, C{2}+R) - Y(C{:}) ) ); % Adjust for transformed grid

figure(1); hold on
plot( X(Z), Y(Z), '.', 'markerfacecolor', 'b' )          % Draw original transformed grid data
plot( X(C{:}), Y(C{:}), 'o', 'markerfacecolor', 'r' );   % Draw centre of mass in transformed grid
plot( X(C{:}) + R * cos(t), Y(C{:}) + R * sin(t), 'r-' ) % Draw optimal circle on top
axis equal; hold off
Tasos Papastylianou
  • 21,371
  • 2
  • 28
  • 57
  • Tasos, thank you for the response, but I'm having trouble following your solution with my data. It looks like your starting with a matrix that has 0's at the "holes". I don't have that with my base data. I think I'd have to interpolate my data, make it a matrix table, and insert my z values as place holders. I fear I'd have many very small regional minima that way. I also fear the computation time could be longer than necessary. I'll try to attach an entire .ascii file of my data. – mhotkow Jun 01 '21 at 21:32
  • @mhotkow a large number of small regional minima is not a problem, since you can reject connected components on the basis of size before proceeding to further calculations. If your data isn't particularly grid-like, however, then Cris' link in the comments above has other nice solutions too which may work better for you. – Tasos Papastylianou Jun 02 '21 at 10:08