# Fragemented linear feature alignment technique

I am having set of linear features lie on a plane (it does not a matter whether the pane is vertical or horizontal). all linear features are either parallel or othogonal to the vertical axis or to horizontal axis (see figure). I want to align vertical line segments which are collinear. As I am having many fragmented lines at every where i want some specific theory / concept to follow to build a technique.

Note: I know end point coordinates of each line segment.

can any one suggest a way.

i am not sure to which field, i should post this.

-
I'm a bit confused. Could you clarify, or bring an example? –  gt6989b Apr 5 '13 at 19:27
@gt6989b: added an example. –  gnp Apr 5 '13 at 19:54
so in the input you will provide the coordinates of the endpoints I presume? An on the output, you want the list of items which are collinear (or parallel) grouped together? –  gt6989b Apr 5 '13 at 20:03
@gt6989b: yes, i want to know what are collinear (or approximately align), then, all approximately align line segments should be aligned.. need to do this in a way to applying some theory or some "grammar" or.... –  gnp Apr 5 '13 at 22:07

1. Accept the list of line segments with coordinates $\left\{(x_{ij},y_{ij})\right\}_{i=1}^N$ with $j \in \{1,2\}$.
2. Compute their slopes $m_i$ and offsets $b_i$ as follows. The line through two points $(x_1,y_1),(x_2,y_2)$ has the equation $y = mx+b$ for $$m = \frac{y_2-y_1}{x_2-x_1}, \quad b = y_1 - m\cdot x_1$$ At this point, for each line segment, you will have calculated slope and offset.
So I would sort the sequence by slope, and then by the intercept. All slopes within a predefined small tolerance $\epsilon_m$ will be considered the same, and all intercepts within some (possibly larger) tolerance $\epsilon_b$ will be considered the same. Based on that, go through the sorted list, checking if consecutive elements are within the allowed tolerance of each other, and output the groups once you find them.