This project was started while sampling images based on the RGB colour it has. I just intended to pick up the red lines of the input image. However, the task turned out to be more challenging. The reason was that my red colour picker algorithm gave me back multiple points following the RGB data. As a result, I got numerous points. See the picture above.
The points were generated on the red lines of the picture accurately, but the problem was that I needed more to make these points into curves. First of all, there were too many unstructured - random - points. However, whenever I tried to make the input grid bigger to manage the number of points, the accuracy of the passage faded. To deal with this situation, my first goal was to simplify the points while conserving the shape of paths as much as possible. In addition, my second objective was to group the points by the main streamline they are positioned on. By doing so, I wanted to define curves based on these organized points. However, to help intuitive understanding, I started with a simpler model.
The upper image represents a similar condition to the first picture. A bunch of points consists of curve passages. Imagine we only have purple-coloured points. Under this condition, how can we derive average curves from points? As mentioned earlier, my first step was to simplify the points that could represent the curve outline as much as possible.
1. Simplifying multiple points while maintaining its passage
The method I used to simplify points was simple. First, I made a virtual 3x3 grid which is bigger than the original one (grid cells made of blue lines). Then, I only left the common centre point of 1x1 cell and 3x3 cell and culled the rest of the points. By doing so, I could maintain the overall scheme but reduce the number of points dramatically.
(Blue grid: 1x1 original cell, Orange grid: 3x3 virtual cell to cull points, Red star: actual points generated, Blue cell: Selected points)
2. Grouping points based on their geometry
However, the biggest challenge was that the data had no structure. As you can find on the left image, the point index number is random. This is because the initial grid and curve geometry have no relationship. However, I aim to group these random points in accordance with the curve shape. In other words, I want to make a tree structure of relevant shape groups like the picture on the right. Creating a group algorithm is far more complicated than simplifying one. I concluded I needed some steps to define whether the point was in the same geometry group.
Step #1. Testing proximity
The proximity between points is the most notable characteristic to define its association. Therefore, I first decided to sort all the points based on the distance with the reference point. In this case, the reference point is #14, which has the smallest x+y value. As it was necessary to use a loop statement to design a proximity sorting algorithm, I used the GH Python component.
import rhinoscriptsyntax as rs
newarray = []
def mindis(x, y):
while len(y) != 0:
criteria = rs.Distance(x,y[0])
index = 0
for i in range(len(y)-1):
compare = rs.Distance(x,y[i+1])
if criteria < compare:
index = index
criteria = criteria
else:
index = i + 1
criteria = compare
closestpt = y[index]
x = closestpt
newarray.append(closestpt)
y.pop(index)
mindis(x,y)
result = newarray
input value: x = reference point, y = unsorted point list
The structure of the code is simple. Per every loop, the code will compare the distance between the reference point and each point in the list; when it finds the shortest, it will put the target point into the new array and make the point to the next reference point. This loop continues until the algorithm gets to the last member of the list.
Step #2. Testing gradient direction and rate of change
Not so surprisingly, proximity has a limitation in making a reliable, relevant group. Especially this simple concept skips several points which should be in the same group. For example, points #25~#32 and #42~#44 should be located adjacent to the new array list, but actually, they are separated. Therefore, I must apply an additional algorithm when deciding the next reference point to compensate for this issue.
The idea is to compute the gradient direction and its rate of change. To elaborate, not just selecting a point which is near, the gradient algorithm will give weights to near 3 to 4 points from the reference point based on their gradient calculation data. Then point with the most weight will be selected, which will have more probability of sharing the same curve shape with the reference point. For example, in case 1, points will be sorted by the orange route because the algorithm will put more weight on the points with the same gradient direction. Also, in case 2, points on the orange way will be selected prior to the ones on the blue line because its gradient change rate is lower than route B. Although, the idea is not verified yet, I will cover a detailed application and corner case solving process in part 2/2.