Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

enter image description here

share|cite|improve this question
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
up vote 1 down vote accepted

I would do the following.

  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.
  3. Two line segments are parallel if they have the same slope. They are collinear if they have the same slope and the same intercept.

    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.

share|cite|improve this answer
really thanking for your clear process. But, still I have a problem, If i follow your process, then what is the main concept that this process rely on. For example "grammar" like shape grammar, context free grammar .... or any other basic concept would be obey your suggested approach. – gnp Apr 9 '13 at 20:37

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.