merge collection of overlapping co-linear lines

Hi folks,

This is a problem I've been unable to come up with a solution for.

given a set of line segments that go in arbitrary directions (in my case, they are all aligned to either x,y,or z axis, forming a cubic lattice of sorts), some of which are co-linear, and of those co-linear lines, some are overlapping or share an end point. I need to be able to take any lines within the set that are co-linear and overlapping or share an endpoint and merge them into a single line. there are cases where some of the lines are co-linear but not overlapping, and these should not be merged.

a simple example: a line that runs from 0,0,0 to 5,0,0 and a line that runs from 3,0,0 to 7,0,0 should merge to a single line that has end points 0,0,0 and 7,0,0. similarly if I had 0,0,0-5,0,0 and 5,0,0-7,0,0 then these two would be merged

if there was also a line that had end points 8,0,0 and 10,0,0 then this would not be merged. (ie is co-linear but not touching or overlapping)

in my specific case, all of the lines run parallel to one of the three unit axes, but it would be cool to have this work for arbitrary directions.

the merge aside, are there even any components that will identify sets of co-linear lines? or even tell you if two lines are co-linear or not (and whether they overlap)? seems to me that this would be a useful component.

any help/ideas much appreciated.

Ben

Replies to This Discussion

Permalink Reply by Laurent DELRIEU on May 24, 2016 at 1:52am

A line equation is
P=P0+dV
P0 is a fixed point in space
V is a vector, say a unit one
d is a distance
So for each segment calculate the equation of line
Sort all lines with P0 and V similar
Calculate for each segment d range merge all range for coincident lines
Output the new segments

If nobody does code it I surely can provide one tomorrow

Permalink Reply by AJ on May 24, 2016 at 7:55am

hey there

i kinda have something similar that im struggling with

i have bunch of planar curves that are overlapping.

i cant find a way to "Boolean them" to recreate one clean curve

Permalink Reply by taz on May 24, 2016 at 8:51am

Multiple options from back-in-the-day depending on your collection of lines. See Danny's link in the thread for another thread.

http://www.grasshopper3d.com/forum/topics/intersecting-overlapping-...

Permalink Reply by Ben Dixon on May 24, 2016 at 4:31pm

I had a look at all those posts before I asked my question - the solutions in those dont handle non-overlapping line segments. I have played with the topologizer plugin, which kinda does part of the job - it trims the overlaps, but doesnt join the colinear segments. a solution might be to run toloplogizer then some gh code that identifies any lines with a common endpoint, then check to see if they are colinear (ie are their vectors in the same direction) but i think a complete solution without resorting to topologizer would be interesting to see.

I do need this practically for something I'm working on, but I'd also like to understand how it works in GH to further my own skills (I'm a programmer, but my GH experience is limited)

so if someone can demonstrate a way of doing this without resorting to something like topologizer, that would be super awesome.

cheers

ben

Permalink Reply by Vongsawat Wongkijjalerd on May 25, 2016 at 2:50am

tried cobbling something together.. it seems to work with limited 2d sample so far maybe(?) and didn't take any time at all with a 1000 curve sample so.. if I have time later might look it over more. (would've probably been way easier coded traditionally, what with iteration =_=)

Basically the definition does the following:
-Flip curves so they (and vectors) generally orient the same way
-Group curves by vector direction (currently an absolute distinction which hopefully doesn't mess up)
-Subgroup by co-linearity (by projecting on to planes based on said vector group and subgrouping the result)
-Figure out overlap of the now co-linear lines by extracting endpoints, sorting them, drawing lines dot-to-dot, finding midpoint, Curve Closest Point with initial curves to cull surplus lines (and handily separating curves in to overlapping groups), join curves, flatten.

Should work, hopefully didn't mess up any of the steps, just.. take a look and try to straighten it out if a part of it doesn't actually work? :P
(my god, wish there was a simple component for creating tree structures through indexing so I didn't have to wrap my head around Sets and nested trees >_<)

Attachments:

merge colinear.gh, 24 KB

Permalink Reply by Ben Dixon on May 26, 2016 at 5:50am

Thanks for doing that, but it still seems to have some problems.

I have attached an example, and a modification of your code to show what I am doing to get it to fail.

I start with a number of stacked solid cubes in a regular pattern, get the edges, remove any duplicates, leaving a simple cubic lattice of line segments, which gets fed to your code. it joins some of the line segments, but misses many of them.

cheers

Ben

Attachments:

Merge Colinear 2.3dm, 350 KB
mergecolinear 2.gh, 16 KB

Permalink Reply by Vongsawat Wongkijjalerd on May 26, 2016 at 11:18am

Yea, I did a dirty branch replacement and messed up (it was only working if there were less than 10 colinear lines in a group, possibly f-ing things up further down the line too) its fixed now.

vector grouping should really have some tolerance if its going to be working for any vector, but for your usage (only x/y/z-axis) it should be fine.

Hope it works now :)

Attachments:

mergecolinear3.gh, 17 KB

Permalink Reply by Pieter Segeren on May 27, 2016 at 12:07pm

Hi Ben, if your current challenge is really about an 3d array of boxes, you could count and meassure the boxes in each direction and create new lines, and just ignore the edge-bits you have.

RSS