Algorithm for getting consecutive line segment edge points from midpoints

Question

So I have a rectilinear grid that can be described with 2 vectors. 1 for the x-coordinates of the cell centres and one for the y-coordinates. These are just points with spacing like x spacing is 50 scaled to 10 scaled to 20 (55..45..30..10,10,10..10,12..20,20,20) and y spacing is 60 scaled to 40 scaled to 60 (60,60,60,55..42,40,40,40..40,42..60,60) and the grid is made like this

e.g. x = 1 2 3, gridx = 1 2 3, y = 10 11 12, gridy = 10 10 10 
                        1 2 3                        11 11 11
                        1 2 3                        12 12 12

so then cell centre 1 is 1,10 cc2 is 2,10 etc.

Now Im trying to formulate an algorithm to calculate the positions of the cell edges in the x and y direction. So like my first idea was to first get the first edge using x(1)-[x(2)-x(1)]/2, in the real case x(2)-x(1) is equal to 60 and x(1) = 16348.95 so celledge1 = x(1)-30 = 16318.95. Then after calculating the first one I go through a loop and calculate the rest like this:

for aa = 2:length(x)+1
    celledge1(aa) = x(aa-1) + [x(aa-1)-celledge(aa-1)]
end

And I did the same for y. This however does not work and my y vector in the area where the edge spacing should be should be 40 is 35,45,35,45... approx.

Anyone have any idea why this doesnt work and can point me in the right direction. This has been killing my mind. Cheers

Tried to find a solution using geometric alebra:

We are trying to find the points A,B,C,....H. From basic geometry we know:

c1 (centre 1) = [A+B]/2 and c2 = [B+C]/2 etc. etc.

So we have 7 equations and 8 variables. We also know the the first few distances between centres are equal (60,60,60,60) therefore the first segment is 60 too.

B - A = 60 

So now we have 8 equations and 8 variables so I made this algorithm in Matlab:

edgex = zeros(length(DATA2.x)+1,1);
edgey = zeros(length(DATA2.y)+1,1);

edgex(1) = (DATA2.x(1)*2-diffx(1))/2;
edgey(1) = (DATA2.y(1)*2-diffy(1))/2;

for aa = 2:length(DATA2.x)+1
    edgex(aa) = DATA2.x(aa-1)*2-edgex(aa-1);
end

for aa = 2:length(DATA2.y)+1
    edgey(aa) = DATA2.y(aa-1)*2-edgey(aa-1);
end

And I still got the same answer as before with the y spacing going 35,45,35,45 where it should be 40,40,40... Could it be an accuracy error?? The method seems to be reasonable, why the hell is it not correct??

Edit: for those interested, excel sheet with same working out as second attempt and real numbers Im using: http://www.filedropper.com/workoutedges

Answer 1

We have cell centers $c_i$ (along one coordinate axis), with $c_i \lt c_{i+1}$. For $N$ cells, there are $N+1$ cell edges, so one cell edge (or the width of a specific cell) needs to be known in order for us to find the coordinates for the rest of the cell edges.

Let's label the left edge of cell $i$ as $b_{i-1}$, and right edge $b_{i}$, $1 \le i \le N$.

Because $b_{i-1}$ is the left edge of cell $i$, and $b_{i}$ is the right edge, and $c_{i}$ is at the center, we know that the half-width of cell $i$ is $c_i - b_{i-1} = b_i - c_i$ (the left side being the lower half, the right side the upper half). The full width is twice the half-width, $2(c_i - b_{i-1}) = 2(b_i - c_i) = b_{i} - b_{i-1}$, as required.

Because the left edge is half-width less than its center, the left edge of cell $i$ is $$b_{i-1} = c_{i} - (b_{i} - c_{i}) = 2 c_{i} - b_{i}$$

Similarly, because the right edge of a cell is half-width more than its center, the right edge of cell $i$ is $$b_{i} = c_{i} + (c_i - b_{i-1}) = 2 c_{i} - b_{i-1}$$

If we know that one cell edge should be at $x$, we can find the index $k$ for which $b_k = x$: $$\begin{cases} k = 0, & x \lt c_1 \\ k = N, & c_N \lt x \\ 1 \le k \le N-1, & c_{k} \lt x \lt c_{k+1} \end{cases}$$

Fixing the cell $k$ width to $w$ defines the edges of that cell: $$\begin{align} b_{k-1} &= c_k - \frac{w}{2} \\ b_{k} &= c_k + \frac{w}{2}\end{align}$$ although only the latter is actually used (similar to the one known edge case). When the one edge is known, we can directly define the rest of the edge coordinates recursively: $$\begin{array}{rcll} b_{i-1} &=& 2 c_{i} - b_{i}, & 1 \le i \le k \\ b_{i} &=& 2 c_{i} - b_{i-1}, & k+1 \le i \le N \end{array}$$

Note that in a computer program, you only need two loops, one from $k$ to $1$ (setting $b_{k-1}$ to $b_0$), and another from $k+1$ to $N$ (setting $b_{k+1}$ to $b_N$).

In pseudocode:

function cell_bounds_edge(N, c, x):
    # - N       is the number of cells
    # - c[1..N] is the center of each cell
    # - x       is the coordinate for one desired cell boundary
    # Return value is an array b[0..N],
    #   cell i edges being b[i-1] and b[i], b[i] > b[i-1]
    #   if successful, FAILED otherwise.

    # Determine the index k for b[k] = one.
    if (x < c[1]) then:
        k = 0
    else if (x > c[N]) then:
        k = N
    else:
        k = -1
        for i = 1 to N-1:
            if (c[i] < x) && (c[i+1] > x) then:
                k = i
                break
            end if
        end for
        if (k == -1) then:
            return FAILED
        end if
    end if

    return do_cell_bounds(N, c, k, x)


function cell_bounds_width(N, c, k, w):
    # - N       is the number of cells
    # - c[1..N] is the center of each cell
    # - k       is a cell number, 1 to N, inclusive
    # - w       is the width of cell k
    # Return value is an array b[0..N],
    #   cell i edges being b[i-1] and b[i], b[i] > b[i-1]
    #   if successful, FAILED otherwise.
    if (k < 1) or (k > N) then:
        return FAILED
    end if
    return do_cell_bounds(N, c, k, c[k] + w/2)


function do_cell_bounds(N, c, k, x):

    # N, k not valid?
    if (N < 1) or (k < 0) or (k > N) then:
        return FAILED
    end if

    # x not valid?
    if (k > 0) and (x <= c[k]) then:
        return FAILED
    end if
    if (k < N) and (x >= c[k+1]) then:
        return FAILED
    end if

    # Verify all cell centers are in increasing order
    for i = 2 to N:
        if (c[i-1] >= c[i]) then:
            return FAILED
        end if
    end for

    # Assign the known edge
    b[k] = x

    # Fill in edges below k
    for i = k down to 1:
        b[i-1] = 2*c[i] - b[i]
        if (b[i-1] >= b[i]) then:
            return FAILURE
        end if
    end for

    # Fill in edges above k
    for i = k+1 to N:
        b[i] = 2*c[i] - b[i-1]
        if (b[i-1] >= b[i]) then:
            return FAILURE
        end if
    end for

    return b

I have not verified whether negative-width cells actually occur, but there is nothing in the algorithm that would reject them. (Mathematically there is nothing wrong, as the centers are at the midpoint of the two edges. It is only the physical/logical interpretation of the edges that make it impossible.) Fortunately, such a case is easy to detect, and that is why I have the above pseudocode detect that case.

The above (edited) pseudocode caters for the two possible use cases: cell_bounds_edge() takes the coordinate for one edge, and cell_bounds_width() takes a cell number and the width for that cell. Both functions determine the index $k$ and the (upper) edge for that cell, $b_k$, and calls the helper function do_cell_bounds(). The helper function implements sanity and validity checks, and fills the cell edge array (based on the centers of the cells, and that one known cell (upper) edge.

I would not try to "guess" or automatize the choice of the one edge to be fixed! (That includes choosing a cell and its width.)

If I absolutely had to "guess" a good $k$ and $w$, I'd first complain, loudly with injective, and probably rant quite a while before I'd actually do it. It would be a lot of work. It would have to be a heuristic based on the distribution of cell widths for each possible value of $k$, with varying $0 \lt w \lt c_{k+1}-c_{k-1}$ for each. That is a lot of calculation, especially for larger $N$. Even then, an user could choose better. There may -- and I bet, usually are -- other rules that cannot be sanely conveyed to the program; for example, some kind of symmetries desired, or maybe piecewise monotonically increasing/decreasing cell sizes, and so on.

The best distribution of cell widths may require the user a few tries, so having a simple utility to show them (so that the user can make a few choices, according to their desires/unconveyed restrictions, and pick the one that works best for them) with little effort.

The OP saw the results of their implicit choice: they defined the width of the first cell, assuming it would not affect the results. That assumption was wrong. The initial choice, the choice of where one of the cell edges is, is an initial value, and affects all the results, because all the rest of the cell edges depend on it (nearest ones directly, further ones indirectly). Oscillation between two values when the centers are at a constant distance is a typical result.

(I'm not certain if this problem can be classified as an ill-posed problem in the Hadamard sense, or an ill-conditioned one, but definitely the selection of the one boundary affects all the results, in a way that is probably unintuitive.)