Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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 have an array of "lines" each defined by 2 points. I am working with only the line segments lying between those points. I need to search lines that could continue one another (relative to some angle) and lie on the same line (with some offset)

I mean I had something like 3 lines

alt text

I solved some mathematical problem (formulation of which is my question) and got understanding that there are lines that could be called relatively one line (with some angle K and offset J)

alt text

And of course by math formulation I meant some kind of math formula like

alt text

so I know the algorithm I used such simple approach like one presented by Victor Liu but its Pusedo solution code and what I need is problem formulation.

My problem is its formalisation into math using some Matrix and other math words (to write into some paper=)

guys - I am a programmer - sorry=)

share|cite|improve this question
Rather unclear to me; you want to find the unbroken line that is the nearest approximation to those two green lines in your second diagram? – J. M. Sep 22 '10 at 14:52
I want to find out that with some K and J green lines are on the same line – Kabumbus Sep 22 '10 at 14:54
When you say, "I know the algorithm, my problem is its formalisation into math", it seems you mean that you already have an algorithm, and you want to know how to express it mathematically to make the paper look better. If so, (a) how did you formulate the algorithm without knowing the mathematics? (b) we can't really help you unless you tell us what the algorithm is. – Rahul Sep 22 '10 at 15:15
In short: could you give an example of your algorithm in action? – J. M. Sep 22 '10 at 15:33
If you say “n line segments are given on the Euclidean plane,” it starts to sound like mathematics! The lame joke aside, mathematical words are for conveying a precise meaning. You have not specified what you mean, so I do not think it possible to formulate it in mathematical terms. For example, one way to formulate the problem might be to find a line $\ell$ such that the number of line segments contained in the distance-d region centered at $\ell$ is maximized, but I do not know if that is what you really want to find. – Tsuyoshi Ito Sep 22 '10 at 17:14
up vote 2 down vote accepted

Write one procedure that takes seg1 and seg2 as input, and returns how close their closest endpoints are. Write another procedure that computes the minimum angle between the lines containing seg1 and seg2. Finally, mix the two with some weights to determine a continuation score: how good seg2 serves as a continuation of seg1. Then select the seg2 that has the best continuation score for seg1.

(If you have, say, $10^5$ segments, then you will need to make it more efficient, which is an entirely different topic.)

share|cite|improve this answer

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.