epsilon-neighborhood for polar coordinates

Hi,

I am having a density-based radar database that I try to cluster with a grid-based DBSCAN algorithm.

The part of the algorithm my question focuses on is "the core point condition". Which is basically the following. To determine if a point is a core point, it needs to have more than a certain number of neighbours (MinPoints) in its epsilon-neighbourhood.

The epsilon neighbourhood can be determined as follows:

1. Calculate the distance from a point P to all the other points in the database.
2. Determine the epsilon-neighbourhood: All the points that are within a max. distance of eps are part of the neighbourhood. Meaning epsilon is the search radius.
3. The core point condition: A point is a core point if in its epsilon-neighbourhood at least MinPoints are.

My question is now, how to determine the epsilon-neighbourhood for polar points with azimuth (azi) and range (r). I do not completely know how to calculate the distance and then from there how to determine the epsilon neighbourhood.

---------------------------------------------------

I use among others the "Phased-Array Toolbox" and the "clusterDBSCAN" algorithm has to possiblity to also use a 1-by-P row vector. Where P is the number of features in the input data. Does someone know how this neighborhood search works with a vector?

Because in the end I want to have a range dependend epsilon(x,y)-vector that varients in azimuth direction with the range.

-------------------------------------------------------

Edit:

I implemented my own algorithm. My problem is that I do not know how to implement the ellipse equation to determine the size of the epsilon-neighbourhood. To basically how to implement the regionQuery function for an ellipse search radius. Below you find my temporary implementation were I only look at the points on the same range or azimuth angle. So it is basically a cross, but not a circual search area. P is the temporary point which has to be checked for the core point criterion.

function Neighbors=RegionQuery(P)           %Determine range/DeltaR to know which 
                                                %Element of the w(c) vector
                                                %should be used and then
                                                %also determine the range.                                        
        RANGEPOINT = Data(P,2)-min(Data(:,2))/Q_range+1;
        
        % Find all the points with the same Range:
        All_Azi =  find(Data(:,2) == Data(P,2));
        % Find all the points in the Eps neighborhood
        Neighbors_azi = All_Azi(find(D_azi(P,All_Azi) <= epsilon_azi(RANGEPOINT)));
        
         % Find all the points with the same Azi:
        All_Range =  find(Data(:,1) == Data(P,1));
        % Find all the points in the Eps neighborhood
        Neighbors_range = All_Range(find(D_range(P,All_Range) <= epsilon_range));
        
        Neighbors = [Neighbors_azi; Neighbors_range];
        Neighbors = sort(unique(Neighbors)); % delete dublicates and sort it in raising order
       
    end

The implementation above is as said only looking linear but not elliptical. Can you help me with that? I created a short data set of points in polar coordinates in degree and meter:

polar_corepoint = [0,6];
polar_borderpoints = [10,6;5,6.5;-5,5.5; 0,8; 0,4 ];
polar_noise = [25,6;-15,4;15,9;45,8.5;-25,8];

eps_azi = 10;      % epsilon radius in azi direction in degree
eps_range = 2;      % epsilon radius in range direction in meter

I want to get the neighbourhood of the corepoint that only includes the boarderpoints and not the noise. So basically the size of the neighborhood should be in the end = 6 (core point + borderpoints).

Do you know how to implement that epsilon search? It does not matter which distance metric is used, I personally have used the Euclidean until now (pdist2(data,data)).

Thanks for you help

Answer 1

[Honglei Chen]

I'll explain how clusterDBSCAN works in this situation.

In your case, range and angle will be two features so you can specify epsilon independently for the two features. The based on these two epsilon values, the algorithm will draw a ellipse to see if a point is within the neighborhood.

HTH

[Christian Metz]

Yes, I understand what the method is but not how it works. Do you know how to implement that? My problem is that I do not know how to draw the ellipse when I have two features.

[Honglei Chen]

Are you trying to implement your own? You can think of the ellipse equation, like (x1/epsilon1)^2+(x2/epsilon2)^2=1.

HTH

[Christian Metz]

Yes, I implemented my own. My problem is that I do not know how to implement the ellipse equation to determine the size of the epsilon-neighbourhood. Can you help me with that? I created a short data set of points in cartesian coordinates:

corepoint       = [5 4];
borderpoints    = [5 3; 6 4.5; 4 4.5; 7 4; 3 4];
noise           = [1 6; 2 2; 5 2; 8 3];

eps_x = 2;      % epsilon radius in x direction
eps_y = 1;      % epsilon radius in y direction

I want to get the neighbourhood of the corepoint that only includes the boarderpoints and not the noise. So basically the size of the neighborhood should be in the end = 6 (core point + borderpoints).

Do you know how to implement that epsilon search? It does not matter which distance metric is used, I personally have used the Euclidean until now (pdist2(data,data)).