Create Composite Line

[KeithSandell]

Does anyone know of an out-of-the-box tool or ArcScript that takes completely dissimilar lines (at least two or more) and creates a composite line that's length and geometry is based on a statistical (average, mean, etc.) measurement of the input line values?

Similar to a best-fit line for a group of points, but this output would be a best fit for lines and not necessarily be a straight-line, i.e. if the inputs had many vertices then the output would have a similar number of vertices.

I've attached a crude picture of what I am trying to accomplish. The Red lines are the inputs and the Black line is the hypothetical output.

This seems like it could be a very complicated undertaking and I don't want to reinvent the wheel if someone has already thought through this, or any thoughts about how I could best go about accomplishing this, thanks?

(I posted this in Spatial Statistics, but there is very little traffic there. Hope no one gets upset about me reposting here.)

[DonovanCameron]

I wonder if Collapse Dual Lines to Centerline would work for this? Requires arcinfo.

How Collapse Dual Lines To Centerline works

Collapse Dual Lines To Centerline (Coverage)

Collapse Dual Lines To Centerline (Cartography)

[DanLee]

I have heard a similar request for creating an "average" or "best fit" line from multiple similar GPS tracks and thought about potential ways of solving the problem. Your case sounds similar to that. Could you send me (dlee@esri.com) some sample data? I would like to test some ideas or if necessary propose a new tool.

Thanks.

[ChrisSnyder]

Don't know of a pre-built script, but a possible algorithm that would be easy to do via Python:

1. Convert the line features to their constituent vertices - taking it a step further, maybe densifying the lines 1st would be a good idea and give you better results. Dan Patterson wrote a great Python script to do this (densify a feature) a while back.

2. Assign one of the line features (now also in point/vertex format) as the "starting points". The other line feature (and it's constituent vertices) would be the "end points".

3. For each "start" vertex, find the closest "end" vertex (maybe the out of the box "near" tool or your own algorithm).

4. Compute the midpont between the start vertex and end vertex.

5. Each midpoint would be a vertex in the "composite" line feature.

Since you are looping through the vertices in the "start" line in their connect-the-dot order, the composite line would be oriented the same way/direction as the "start" line.

This would be a fun tool to to code via Python! Dan Lee will probably come up with something better/cooler than my idea, but maybe if I get some time next week (and he hasn't already done it)I can write some code next week.

[KeithSandell]

Hey all,

Thanks for the suggestions. I've uploaded, here, a zip file with a couple of dissimilar lines for anyone to play with at their leisure.

Chris,

Your ideas were similar to what I had in mind initially with the exception, and my fault for not mentioning, that it appears that it would only work with two lines (I guess you could connect all the start points by a line and find that lines midpoint). I want the final solution to be able to take multiple lines, 2 or more unknown lines (meaning the tool could not expect anything), and create a composite.

My initial/ongoing thoughts were this:

(Which all depends on knowing where or determining were or defining where the lines begin and end based on geometry and/or its geographic location or some other parameter(s).)

1) Normalize the input lines, perhaps Densify or other process, to get rid of any loops that are present. In theory, the exit and reentry points of a loop would be coincident and by cutting off the appendages to the line it would leave a more clean geometry that is most like a true line rather than an association of a line and psuedo polygon.

1a) But getting rid of a loop and then creating a composite from the modified line would not technically be a composite of the original inputs, but a composite of some derivations thereof (kind of a copy of a copy issue)...something to think about. Perhaps a user defined option to "Keep Loops/Self-Intersections"

2) Find the length of eash input feature and create new points (not vertices) along the length of the line at equal intervals, i.e. user defined "20" intervals, the beginning point being indexed as "0" and then each successive point +1 until we reach the user defined limit.

3) Average the X and Y values of each similarly indexed set of points to arrive at a average point for all index 0s, for all index 1s, etc.

4) Take the resulting averaged points and do "Points to Line"

5) Viola, composite line.

Or at least I wish it was that easy.

Thanks for any thoughts everybody.

[KeithSandell]

Here is some code and sample data.

This is cool Chris. Thanks a lot for putting your time towards this.

[ChrisSnyder]

My pleasure. This is actually something I had been meaning to do on my own for a while... Note of course that this is the very basic algorithm. As you suggested, there are a lot of ways to make it better and more full featured. But adding bells a whistles to anything tends to add significant build time, so I just chose to take the simplest route possible.

For my purposes, I want to compare GPS-derived line features, and using the actual vertices (rather than densified vertices or measures) lend themselves to a better solution since the vertices more often than not represent points of inflection that the field person thought were important to record. Seems best to be comparing these inflection points rather than artificial points that would be created if using densified or measured points.

One very simple enhancement that I almost put in the codse would be a distance threshold. Basically, as traversing through the vertices in orientFC, if there were no vertices from the other FCs within a given distance (500ft for example), that vertex would be skipped (or a > threshold point from the other FC would just be ignored?), as there were no "valid" locations to compare it to.

[DanLee]

I still owe everyone a summary of my investigation on this.

Thanks, Chris, for sharing the data and for the email discussion. After examining the hurricane tracks, I realized how dissimilar (in location, shape, direction, etc.) any two or more of the tracks can be. So the idea I had in mind for rather similar tracks/lines won't work at all. I am glad you have solved the problem in coding.