algorithm - Identify and sort multiple circles on 2d plane using python -


i have multiple points forming many circles on 2d plane , need identify , sort them further calculation. have [x, y] co-ordinates of each point , number representing each point.

all point numbers in 1 circle should sorted in list. , point numbers of next circle should follow. each circle formed 6 points. should first , next 6 points of adjacent circle should follow.

i identified convex hull way of identifying closed polygons. similar want identify multiple convex hulls in same plane. think should possible in python. can on please?

edit:

  1. the circles don't overlap
  2. the circles same size, i.e. same radius
  3. every circle has same number of points.
  4. they evenly spaced holes. hole radius specific - 10mm , entire array rectangular shaped. plate array of evenly spaced holes - albeit - row of holes staggered.

schematic: circles on plate. each circle defined 10 points. have (x,y) co-ordinates of these points

knowing specifics edit allows taking shortcuts. allow me restate / infer couple things:

  1. holes in rows/columns that vertical/horizontal , do not overlap
  2. holes standard width/height (identical diameters)
  3. the x or y value 'first' point of each hole in given row/column same (assuming fem uses consistent hole orientation)

with observations in mind, try naive following (psuedocode outline) before implementing algorithms mentioned in comments. isn't running code, gets concept across - generally, creating column 'bins' of points (col 1, col 2) , split row bins (which represent points in given hole).

## sort points array x, y # while unmapped_points.count > 0     ## determine lowest 'x' value (far left)     ## create column 'bin' of points x <= (x_min + diameter)     # while column_bin.count > 0         # determine lowest 'y' value (bottom edge of hole)         # create row (hole) 'bin' of points y <= (y_min + diameter)         # update y_curr minimum y remaining points in column     # update x_curr minimum x remaining points

if take less general case , add condition:

  1. initial offsets , column/row spacing known

then skip finding starting column/row limits , window points directly:

# hole1 = points (p.x >= x1_offset , p.x <= x1_offset + diameter) , (p.y >= y1_offset , p.y <= y1_offset + diameter)

although, if layout known, compute centerpoints , loop through finding points within known radius:

# points sqrt( (p.x - c.x)^2 + (p.y - c.y)^2) < radius

but i'm assuming spacing isn't known - otherwise generate points without knowing fea model looping through each center point , computing offsets known radius , evenly-incremented angles.


Comments

Post a Comment