How can I find the centre co-ordinates of an array of connected lines?

Question

I have an array that defines an unbroken path as follows;

var path = new [] { 
    new Vector2(0.4f, 0.2f), 
    new Vector2(1f, 1.1f), 
    new Vector2(2f, 1f), 
    new Vector2(2.5, 0.6f)
}

Which results in the following visualisation;

The number of points in the path is variable. How can I determine the co-ordinate that represents the centre of this path? Centre in this case is defined as a co-ordinate on one of the lines where splitting the path at that point would result in two paths of equal length.

Summing the points and averaging is not a solution, considering this would result in a co-ordinate not on the path.

Is there something in c# or unity3d that can provide this value, or do I need to whip out some funky math stuff?

score 3 · Answer 1 · edited Apr 13 '17 at 12:19

3

For each segment, calculate (and store) the segment's length. Add up all lengths and divide total by 2.

Iterate over all the segments in path order, subtracting the length of each segment from this halved total until the current segment length is greater than the remaining total.

Then compute the point at that length along that line segment.

https://math.stackexchange.com/questions/409689/how-do-i-find-a-point-a-given-distance-from-another-point-along-a-line

https://math.stackexchange.com/questions/175896/finding-a-point-along-a-line-a-certain-distance-away-from-another-point

edited Apr 13 '17 at 12:19

Community

1
1

answered Jan 05 '16 at 01:21

Mitch Wheat

295,962
43
465
541

Possibly not optimally performant, but functionally correct is where to start. – Pieter Geerkens Jan 05 '16 at 03:50
"Possibly not optimally performant," - would you like to explain why. I don't believe your statement is correct. – Mitch Wheat Jan 05 '16 at 04:02
Depends on the available trade-offs of time for space. Perhaps one can perform a single pass at the cost of requiring more space, which may be slightly more efficient on some architectures. Only a second- or third-order effect, and intended not as a criticism but as a thought stimulator. This is clearly the right place to start. – Pieter Geerkens Jan 05 '16 at 04:08
it can be done in a single pass. Notice my comment in parentheses "(and store)" . I should have said store the cumulative length – Mitch Wheat Jan 05 '16 at 04:10
You also need to store the trailing path back to the most recently calculated midpoint, which is linear in the total number of segments, in order to run in a single pass. – Pieter Geerkens Jan 05 '16 at 04:14

score 2 · Accepted Answer · answered Jan 05 '16 at 01:58

Here's a quick code example to grab the mid point:

Vector2 GetMidPoint(Vector2[] path)
{
    var totalLength = 0d;
    for(var i = 0; i < path.Length - 1; i++)
        totalLength += GetDistanceBetween(path[i], path[i + 1]);

    var halfLength = totalLength / 2;
    var currLength = 0d;
    for(var i = 0; i < path.Length - 1; i++)
    {
        var currentNode = path[i];
        var nextNode = path[i+1];

        var nextStepLength = GetDistanceBetween(currentNode, nextNode);

        if (halfLength < currLength + nextStepLength)
        {
            var distanceLeft = halfLength - currLength;

            var ratio = distanceLeft / nextStepLength;
            return new Vector2(currentNode.x + (nextNode.x - currentNode.x) * ratio, currentNode.y + (nextNode.y - currentNode.y) * ratio);
        }
        else 
            currLength += nextStepLength;
    }
    throw new Exception("Couldn't get the mid point");
}

public double GetDistanceBetween(Vector2 a, Vector2 b) 
{
    var x = Math.Abs(a.x - b.x);
    var y = Math.Abs(a.y - b.y);
    return (Math.Sqrt(Math.Pow(x,2) + Math.Pow(y, 2)));
}

How can I find the centre co-ordinates of an array of connected lines?

2 Answers2