Ordering components by distance from each other?


#1

Continuing the discussion from Ruby API - to which layer a component belongs:

Hi @slbaumgartner:

Can you tell me if this is too hard a calculation or how to start to solve it?

I have a set of around 150 cubes in a model. I want to select a starting point and then calculate the closest one from there (to the center of the bottom face is OK) and then do it from that found point, and so on. What I need to do is to assign an order to those cubes and I’d like to avoid manually doing it. If I can store the component name and an order in any array I will be really happy.

Thanks a lot


#2

I’m currently looking at the boundingbox object and what I’d do is load all the boxes for all the cubes in an array, pick the first one and calculate the distance to each others’ and pick up the smallest found to be the next starting point, and so on.

This is my pseudocode, nothing a newbie like me could achieve in a week!

Thanks indeed


#3

You will likely be using the block form of the sort or sort! method.

Example to sort groups in an array by their distance from the ORIGIN:

# box_array is an array of references to your box objects
box_array.sort! {|a,b|
 a.bounds.center.distance(ORIGIN) <=> b.bounds.center.distance(ORIGIN)
}

Given this example, you should be able to write a method that removes one of the groups out of the array, and uses it to sort the array, instead of using the ORIGIN point.

ADD: And having done that, you can then write another method with a control loop, that successively shift members out of the array, and uses them to call the sort method.


#4

@DanRathbun wouldn’t #min be better than #sort? He wants to use the point in the first found cube as the reference to find the next one, so the ordering of the rest with respect to the first reference point is irrelevant. Unless it is badly written, shouldn’t min be order(n) vs sort order(n*log n)?

@leantricity if you can work with the centers of the cubes rather than a corner or a point on a face, using the bounding box is a clever way to avoid all the transformation and geometry calculations I mentioned in the previous topic because the center of the bounding box of a cube is also the center of the cube no matter how the cube is rotated. However, unless your cubes are all oriented so that their axes are parallel to the model’s axes, the same is not true about the corners.

Rather than load the bounding boxes into an Array, I’d create a new class that has a reference to a cube and its center point as attributes. That would avoid repeatedly accessing the bounding box and determining its center - just calculate distances between the already calculated centers.

The basic sketch Dan describes (aside from using min vs sort) seems like the way to go. Create instances of the class I described for all your cubes and put them in an Array. Define a method that takes a reference point and uses min to find the closest cube center by means of a <=> test like Dan showed. Slice that cube out of the Array and append it to a results Array. Then repeat, using the center of the last result as your new reference point. Be advised, though, that this may be a slow operation since a lot of distance calculations and comparisons will be required.


#5

I don’t know, perhaps. Both of them have to go through the entire array doing basically the same comparison.
I thought that once it was sorted it might be faster from then on.

Don’t let the ORIGIN example confuse issues. (It was just an example of using the sort method.)

So imagine that he has already chosen his starting group.
He gets the bounds.center of that group.
He use that in place of the ORIGIN in my example.
The starting group should afterward be in position 0, since the distance from it’s center to it’s center is 0.
So at least the array is in some kind of order, and he has the first two starting groups at positions 0 and 1.
He can shift them both out of the array, and process them.

From then on, he can shift or slice! which ever group comes up as min_by.
closest = box_array.min_by {|g| g.bounds.center.distance(last.bounds.center) }
But min_by is SU2014+.


#6

That sounds like a better job for an ostruct.


#7

For designing an algorithmic solution it is important to know what the higher-level goal is. I have not yet an idea what you want to achieve once you have an ordered list of components. Only knowing a rough technical goal leaves still room for interpretation.

For example using bounding boxes, you are aware that you only get an approximative, not an optimal solution (unless you know components will only contain boxes oriented along the component’s bounding box).
When you find for a box A the nearest box B, it is possible that the nearest box to B is not a box C, but again A. So you would get several cycles, but not one big chain containing all. An interpretation would be: For box B you just want to find nearest one from all remaining (all minus visited).

How does the ordered list you want differ from an arbitrary order, what is the criterium to optimize for? Do you need an optimal solution or just an approximative (maybe heuristic) solution? Is it possible you want something similar to this?


#8

Thanks a lot for you all. Instead of dealing with Ruby (in what I’m a newbie) I’ve been calculating it in my database (in what I’m an insolent but practical ignorant). Instead of solving the problem inside Sketchup I’m looking for a solution outside and when I’m happy I will delve into Ruby code.
Regarding the goal:
This image belongs to 2 of 5 floors in an office. The red cubes represent active desks at 2PM. Active means that the computer has been actively used more than 5 minutes in each 15 minutes segments. So, what I’m trying to calculate is the positive impact in energy reduction for the office by shuffling people around based on metered activity.


My distance calculations where aimed at ordering the locations (like 1,2,3,etc) starting from an arbitrary corner and then numbering spots by closeness. I’ve solved the problem but it is not optimal. Why? Because the closest points between 2 cubes can transport the numbering process step by step to an incoherent numbering result as, for example, I can have like a “snake shaped” area of numbers and close places will be left for the end of the process. So @Aerilius was right, I could solve my problem but not arrive to my goal. This is a task I’ve been doing manually but I’d like to speed it up, that’s why I want to calculate it. The way I do it manually, that maybe can raise ideas on how to compute it, is working on “patches” in the same way of an imaginary wave entering the office from the rightest corner. In that way, I pick the first spot and then I select the closest one and I work in bands (as an inkjet printer paints the paper).
I’m not engineer nor programmer nor graduated in anything so some subjects go beyond my immediate grasp but I can solve them with a little patience and time. I Imagine that the way to do it would be to locate the closest ones limiting the range to cubes located in “BandA”, then “BandB” and so on so closeness will be decided on a lateral fashion or similar.
Maybe the most reasonable thing to do would be to select the cubes belonging to a suitable patch and then grouping or creating a bounding box per group and limit the search of closest cubes by patches.
I don’t need too much precision and I can work with the center of the cubes without problems.
I attach here an image from our website where I explain the work I do. The image shows the previous location and the suggested optimal one: you can see the difference in area required to be serviced in the office with the optimised distribution. The plot shows real activity but in swapped locations, the dots ordered by affinity in time and intensity of activity by the users.