CODEWITHSUNDEEP
pythonnumpyvoronoikdtree
Adam Krawczyk
Adam Krawczyk

Reputation: 193

How to merge close points in 2d list python

I'm having troubles to merge close points for Voronoi diagram, here is the case:

  1. I load a map from image
  2. The map is converted to an array containing only points meaning obstacles
  3. Voronoi diagram is computed from this array

Then is the problem that I have vertices inside "obstacles" as shown in imageenter image description here

My idea is to convert obstacles containing many points to one point.

List of points look similar to this:

map = [[11, 29], [11, 30], [11, 31], [12, 28], [12, 29], [12, 30]]

I want to take a group of points and merge these points into one.

I've found this Fast fuse of close points in a numpy-2d (vectorized)

I Don't have any idea how to fuse these points taking into account obstacles which are not "point-shaped"

Upvotes: 1

Views: 1237

Answers (1)

Finn
Finn

Reputation: 2343

I would recommend you not to map as variable name, as there is a function with the same name. Your issue in genreal is to find clusters which is similiar to the issue in your link, but based on the data k-Dtree might not be great. I would recommend an other clustering algorithm from scikit:

  • KMeans, if you know the amount of obstacles
  • DBSCAN, if you know the maximal size of the obstacles

from sklearn.cluster import KMeans, DBSCAN import numpy as np

obstacle_list = [[0, 0], [0, 1], [1, 0], [1, 1], [3, 3], [4, 3],[3,4]]
obstacle_array = np.array(obstacle_list) # for easier handling

#if you know the number of obstacles
number_of_obstacles=2
cluster_values = KMeans(n_clusters=number_of_obstacles).fit_predict(obstacle_array)
print(cluster_values) # those are the cluster MeanShift found

#if you know the maximal size of an obstacle
max_size_of_obstacle = 3
db_values = DBSCAN(eps=max_size_of_obstacle).fit_predict(obstacle_array)
print(cluster_values)# those are the cluster DBSCAN found

If you want it to be represented only by 1 point probably somewhere in the center) you can loop over the cluster_values to calcualte it. I would take mean of x and y values, but your data seems to be only integers so you might want to take something else.

Upvotes: 0

Related Questions