I am trying to make a subnetwork to connect points into paths when they are close to eachother given a certain maximum distance, without connecting the separate shapes. So far, I’ve tried two approaches, which can be found in the attached file (I’ve ungrouped them).
The first one, to the left, calculates the distances between the closest points and separates them into connected paths when it goes above a specified value. The problem is, one would need to duplicate the bottom part of the subnetwork for every discerned shape (which is not known beforehand). In addition, it supposed that the points are logically sorted, but that’s not always the case. I’ve tried to sort points according to different parameters, but sorting doesn’t adopt earlier sorting methods. Problem here is that points can’t be grouped. Any workaround to this, would be helpful.
The second one, to the right, calculates the distances between all points and connects the points with shortest distances. It’s possible to make a certain amount of connections between connections. Ideally, it would only draw one line per point, and when that one is already drawn, would go the second distance. I can’t conceptually grasp how and where in the network one would have to implement this.
So I’m stuck with both approaches. Any help would be appreciated.
|?||Show this help|
|ESC||Blurs the current field|
|r||Focus the comment reply box|
|^ + ↩||Submit the comment|
You can use
Command ⌘ instead of
Control ^ on Mac
Support Staff 1 Posted by john on 13 May, 2021 06:34 PM
You always come up with interesting challenges!
Attached is a first cut at a solution. The link_closest node returns two line segments for each point in the list, linking that point to its two nearest neighbors. The segments are always drawn starting with the upper left point (this makes the duplicate segments easier to spot). The distinct_links node then removes those duplicate line segments.
The screenshot shows the case with the point list you provided. I added some additional nodes to try out different variations; you can change the wiring to wiggle your original points or add a few distant outliers.
You can also just change the amount of shapes and seed in the scatter node to try different arrangements. You will notice that things are not as tidy when shapes overlap or are very close. For close but non-overlapping shapes you can reduce the resample length until all the points in each shape are closer to each other than they are to any points on the nearest shape.
This is a very inefficient method, so it bogs down if you throw more than a few thousand points at it. I added a slice node set to a max of 2000 points to ensure you don't accidentally cause a freeze.
Lone outliers (individual points beyond the max limit from any other point) will produce 0-length segments (a line from the point to itself). If that's a problem you could easily spot and remove them.
Although the segments are nicely ordered in this case (because the original points were generated in a coherent order), in general they may not be, which might cause your plotter to jump around a lot. If that happened I'm guessing that your plotting software would optimize the plotting order for you. If not, it should be possible to optimize the order in NodeBox - let me know if that's an issue and if you need help doing that.
Reducing the segments of each cluster to a single path is a harder problem but might be doable. I wasn't sure whether you really need that or if the individual segments forming the path around each cluster would be good enough for your purposes.
Give this a spin and let me know how it works. There may be some corner cases to chase down.
2 Posted by florisdejonge on 14 May, 2021 07:10 AM
Thanks for your quick reply and solution. It’s very educational to see how you use certain nodes, in this case the filter-data and indices nodes. This works quite a bit better than my earlier attempt. In the first screenshot you see the points I want to connect into separate shapes (it’s part of my attempt to generate landscapes which I’ve shared on my Instagram). As you can see the ordering is a bit random. The second screenshot is the result of my own subnetwork. The third one is with your solution. However, there are indeed some corner cases. Especially when more distance between points exists. Any ideas how to account for these?
It would be nice if the segments of each cluster would be connected into a single path since it would result in less up and down movements of the pen and therefore less artifacts. In my first example in the previous post I’ve tried to do this. This could work when all duplicate points are removed and the program would cycle through every point and connect them, except when the next point is too far away. Do you have suggestions how to approach this?
Support Staff 3 Posted by john on 14 May, 2021 08:48 AM
It never fails to amaze me how utterly effortless it is for the human visual system to perceive these shapes, and how hard it is for computers. I am willing to take another run at this, but my hunch going in is that this is a hard problem, especially to solve in a generic way.
One big question: in this case is it your desire to come up with two continuous paths, one for the big shape on the left, the other for the shape on the right - with all the gaps in both shapes filled in? Or do you just want to reduce the hundred odd tiny segments to about a dozen longer connected paths leaving the gaps in place?
In other words, are you trying to create fillable, closed shapes or smooth, open strokes? Should the algorithm assume that it needs to keep crunching until it has closed paths?
Then, could you please send me a CSV with the points in your data set? I can then feed that into my algorithm and play with it to see what improvements I can make.
4 Posted by florisdejonge on 14 May, 2021 12:38 PM
Thanks for you reaction. Please see the attached file for what I am trying to do regarding these generated landscapes. So no dataset is involved, just a noise-node. There could be several bodies of water, maybe 2, maybe 10, depending on the scale of the noise-node and the value for determining the waterline. I thought about accentuating that waterline with a line. Which is ideally a single continuous path with no gaps for every body of water. They don't have to be closed necessarily, smooth strokes (fit_curve) is preferable above fillable, closed shapes. I hope this makes it a bit clearer.
Support Staff 5 Posted by john on 15 May, 2021 04:53 AM
This is a hard problem!
I have not yet managed to make a generic node to perfectly isolate the shorelines. But I did manage to isolate the shorelines manually. See screenshot and attached files.
One insight is that we need to work with the full set of curves - not just their endpoints - to isolate the shoreline. The curves, and their top to bottom ordering, contain vital information that is lost once you toss all but the endpoints.
To manually define the shore I used delete nodes and hand-positioned rectangles to isolate different subsets of the curves. Once this was done he smaller lake was easy to distill down to a single closed path. But the bigger sea, because of it's complex shape with both convex and concave sections, was harder. I had to divide it into 5 subsets and then string their east and west endpoints together in a complicated way.
So this is just a proof of concept for the particular landscape you generated. Change the noise pattern and you would have to isolate the shorelines by hand again.
Just for fun I rendered it with blue translucent water and green hills. For plotting purposes you would want to only use the shore outlines without filling them.
So this is a step forward, but a generic solution continues to elude me. I will keep thinking about it.
6 Posted by florisdejonge on 16 May, 2021 01:00 PM
Thanks for exploring the possibilities for isolating the shorelines. Since I want to generate different landscapes when the seed is changed, everything else would preferebly be automatically correct. So, I've been trying another direction to come up with a generic solution as well and it is indeed harder than it sounds.
So far I was able to come close to a similar accuracy as your earlier solution. I've attached an update of the earlier test file. In red is my most recent attempt, in green one of my earlier ones, and in blue yours. I've also applied this to my main landscape file with the same corresponding colours. For now, those solutions both work good enough. I've found that when experimenting with different textures the little mistakes it generates are hardly visible. Thanks again for you help.