3

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

All point numbers in one circle should be sorted in a list. and then point numbers of next circle should follow. Say each circle is formed by 6 points. They should be first and then next 6 points of the adjacent circle should follow.

I identified that Convex Hull is a way of identifying closed polygons. This is similar but I want it to identify multiple convex hulls in the same plane. I think this should be possible in python. Can anyone help on this please?

Edit:

  1. the circles don't overlap
  2. the circles are all the same size, i.e. same radius
  3. every circle has the same number of points.
  4. they are evenly spaced holes. the hole radius is very specific - 10mm and the entire array is rectangular shaped. a Plate with an array of evenly spaced holes - albeit - row of holes are staggered.

Schematic: Circles on a plate. Each circle is defined by 10 points. We have the (x,y) co-ordinates of these points

Pushkar Sheth
  • 99
  • 6
  • Why is a circle formed by 6 points and not 2 (two points cutting the circle in half)? – Munchhausen Aug 08 '16 at 18:23
  • Look into Hough circles Transform. It would be a much better solution. – UltraInstinct Aug 08 '16 at 18:25
  • well these are points with co-ordinates and not an image - will Hough circle work on circles defined by co-ordinates? – Pushkar Sheth Aug 08 '16 at 18:26
  • i didn't understand your question @Munchhausen – Pushkar Sheth Aug 08 '16 at 18:29
  • 1
    Yes, transform every `(x,y)` to `(r,theta)` (polar coordinates). And then use an accumulator (imagine every (r, theta) point is a bucket). Buckets with relatively high items will correspond to circles in your original space. – UltraInstinct Aug 08 '16 at 18:32
  • will try that in some time. Any other suggestion @SuperSaiyan? Please note that all my r are going to be same. – Pushkar Sheth Aug 08 '16 at 18:36
  • Where is your data coming from? Are the points guaranteed to be in a circle? Can the circles overlap? If you're generating the data (or can discuss with whoever is), can you get center points as well and then check to see what points fall at a common radius? – brichins Aug 08 '16 at 18:39
  • Thanks for the questions @brichins. data comes from a finite element model (https://en.wikipedia.org/wiki/Finite_element_method). Yes - they are guaranteed to be circles. The circles don't overlap. I know they are of common radius because I have generated them. but they are not generated within the python environment - they come from an FE Model (https://en.wikipedia.org/wiki/Finite_element_method). The point numbers are also from the same model - but they cannot be sorted in the model and hence I need to write this code. – Pushkar Sheth Aug 08 '16 at 18:42
  • Ah - I did some FEA stuff in material science classes (former civil engineer). Depending on your needs, you might consider moving your entire model into a [Python FEA](http://stackoverflow.com/q/7375130/957950) library. Otherwise, there is probably some patterns in your model that could be taken advantage of for sorting. Can you edit to include a screenshot of your model, or typical output? Re-reading your question with FEA in mind, is this model perchance a plate with an array of evenly holes - gusset or something similar? If so some x,y bucketing might do the trick. – brichins Aug 08 '16 at 19:10
  • @phs I think the information from your last comment needs to be in the question itself. Specifically, if I understand correctly: (1) the circles don't overlap (2) the circles are all the same size, i.e. same radius (3) every circle has the same number of points. And if the radius and number of points are inputs to the program, then that makes the problem much easier. – user3386109 Aug 08 '16 at 19:33
  • @brinchins - Yes they are evenly spaced holes.the hole radius is very specific - 10mm and the entire array is rectangular shaped. a Plate with an array of evenly spaced holes - albeit staggered - is exactly what I have. – Pushkar Sheth Aug 09 '16 at 03:49
  • @user3386109 Sure - will edit the question. – Pushkar Sheth Aug 09 '16 at 03:49
  • This sounds like a clustering problem to me so you might want to try something similar to [this](http://robinlovelace.net/r/2014/03/21/clustering-points-R.html) in Python or even better [this](http://geoffboeing.com/2014/08/clustering-to-reduce-spatial-data-set-size/) using scikit-learn. – Mahdi Aug 09 '16 at 05:01
  • 1
    Clustering algorithms usually do *not* allow such radius limitations. Because they want to infer the structure from the data. Your problem is more of a **set cover** type: you want to cover your data set with as few circles as possible? (plus, they are not allowed to overlap? clustering will also not ensure that either). – Has QUIT--Anony-Mousse Aug 09 '16 at 06:03
  • @Anony-Mousse Clarification: They "do not" overlap - thats a sure thing. Can you please elaborate more on your "set cover type" because I couldn't find anything relevant on it...? – Pushkar Sheth Aug 10 '16 at 04:51
  • @Mahdi Thanks - the method shown on [this](http://geoffboeing.com/2014/08/clustering-to-reduce-spatial-data-set-size/) page deals with GPS Co-ordinates - I understand that it can be modified for my problem. but can you point to an example that is more "component" based (with millimeters as units) and not "gps" based if possible? – Pushkar Sheth Aug 10 '16 at 04:54
  • @brichins included schematic of circles on plate. – Pushkar Sheth Aug 10 '16 at 05:43
  • Google for "set cover problem" again. It's on Wikipedia. Also, I do not get what you write about "holes". – Has QUIT--Anony-Mousse Aug 10 '16 at 07:00
  • @Anony-Mousse holes = circles. Please see schematic in updated question. – Pushkar Sheth Aug 10 '16 at 07:12
  • Since they are evenly spaced, use the Hough transform as suggested by @SuperSaiyan – Has QUIT--Anony-Mousse Aug 10 '16 at 07:15
  • @Anony-Mousse well I have my reservations about Hough Transform because I already have co-ordinates of the points and not an Image. HT seems to be well suited for an image. – Pushkar Sheth Aug 10 '16 at 07:21
  • Hough transform has also been used for clustering, and is a very nice technique for finding *aligned* patterns in 2d. – Has QUIT--Anony-Mousse Aug 10 '16 at 07:22
  • It would seem from your drawing that the 10 top/left-most points would form the top/left-most circle. Any three of those points will give you the center of the circle. Sorting the points from left to right will tell you how many points are in each column, and this will tell you how many holes there are, etc... Geometrically this seems like a very straightforward problem, so I don't understand how this is difficult to code. – m69's been on strike for years Aug 10 '16 at 15:32
  • 1
    @phs: Again, the way hough transform is used in image processing, is by considering every pixel as a (x,y) coordinate. If you have algorithms on the web that say iterate over rows and then iterate over every pixel in the row -- what you'd do is iterate over all points you have. Everything else stays the same. – UltraInstinct Aug 10 '16 at 16:45
  • 1
    Also, can you please attach a sample data to the question? – UltraInstinct Aug 10 '16 at 16:49

1 Answers1

0

Knowing the specifics from your edit allows for taking some shortcuts. Allow me to restate / infer a couple things:

  1. Holes are in rows/columns that are vertical/horizontal and do not overlap
  2. Holes are all a standard width/height (identical diameters)
  3. The x or y value for the 'first' point of each hole in a given row/column will be the same (assuming your FEM uses a consistent hole orientation)

With those observations in mind, I would try something naive like the following (psuedocode outline) before implementing the algorithms already mentioned in comments. This obviously isn't running code, but hopefully gets the concept across - generally, creating column 'bins' of points (col 1, col 2) and split those into row bins (which then represent all points in a given hole).

## sort points into an array by x, then y
# while unmapped_points.count > 0
    ## Determine the lowest 'x' value (far left)
    ## Create a column 'bin' of all points with x <= (x_min + diameter)
    # while column_bin.count > 0
        # Determine lowest 'y' value (bottom edge of hole)
        # Create a row (hole) 'bin' of all points with y <= (y_min + diameter)
        # Update y_curr to minimum y from remaining points in column
    # Update x_curr to minimum x from all remaining points

If we take an even less general case and add another condition:

  1. Initial offsets and column/row spacing are known

Then you could skip finding starting column/row limits and just window the points directly:

# Hole1 = points where (p.x >= x1_offset and p.x <= x1_offset + diameter) and (p.y >= y1_offset and p.y <= y1_offset + diameter)

Although, if the layout is already known, you could also just compute centerpoints and loop through finding points within the known radius:

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

But I'm assuming the spacing isn't known - otherwise you could just generate the points without knowing anything about the FEA model by looping through each center point and computing offsets with the known radius and evenly-incremented angles.

brichins
  • 3,825
  • 2
  • 39
  • 60