Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

Diagram 1

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)

Diagram 2

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

Diagram 3

so I know the algorithm I used such simple approach like one presented by Victor Liu

  return Atan((B.y-A.y) / (B.x-A.x)) // use atan2 if possible, but needs wrapping

   NearlyParallel(angle1, angle2)
  delta = Abs(angle1-angle2)
  return (delta < threshold) or (delta > Pi-threshold)

   Collinear(A,B, C,D)
   // Assume NearlyParallel(Angle(A,B), Angle(C,D)) == true
   return NearlyParallel(Angle(A,C), Angle(B,D)) and NearlyParallel(Angle(A,D), Angle(B,C))

but its Pusedo solution code and what I need is problem formulation.

argmin(B, A) [Atan((B.y-A.y) / (B.x-A.x))]" btw that line i just write looks like math... but I do not kow how to give to determine in such math model my arrays of A's and B's...

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|improve this question

closed as off-topic by Ricardo Andrade, Yemon Choi, Steven Sam, quid, Felipe Voloch Jun 8 at 18:30

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "MathOverflow is for mathematicians to ask each other questions about their research. See Math.StackExchange to ask general questions in mathematics." – Ricardo Andrade, Yemon Choi, Steven Sam, quid, Felipe Voloch
If this question can be reworded to fit the rules in the help center, please edit the question.

Also posted at math.stackexchange.com/questions/5216/… –  Robin Chapman Sep 22 '10 at 17:10
And on SO... and nowhere got answers... –  Ole J Sep 22 '10 at 17:12
I don't understand the problem, and I suspect this might be the reason for others too. Perhaps you could try to formulate it more clearly. First step: distinguish between "line" and "segment"! –  Laurent Moret-Bailly Sep 23 '10 at 5:42

1 Answer 1

up vote 1 down vote accepted

Let $K_\eta(v)$ denote the vector cone in $\mathbb{R}^n$ around vector $v$ of angle $\eta$. More precisely:

$K_\eta(v) = \{u\in\mathbb{R}^n: \angle(u,v)<\eta\}$

Given a line segment $l = (p_1,p_2)$ (here $p_1,p_2$ denote its endpoints), let $v(l) = p_2 - p_1$. Let $\pi_1(l) = p_1$ and $\pi_2(l) = p_2$. Given a sequence $l_1,l_2,\dots,l_n$ of line segments in $\mathbb{R}^n$, we say that the sequence forms a line relative to angle $\eta$ with displacement sequence $d_1,\dots,d_{n-1}$, provided that the following is satisfied:

For any $j = 2,\dots, n$, we have:

1) $v(l_j)\in K_\eta(v(l_{j-1}))$

2) $\|\pi_1(v_j) - \pi_2(v_{j-1})\| = d_{j-1}$

where $\|\cdot\|$ denotes the chosen norm on $\mathbb{R}^n$. I suppose in your case this would be the standard norm: $\|(a_1,\dots,a_n)\| = \left(\sum_{j=1}^n a_j^2\right)^{1/2}$.

Of course, if you wish to work in the more general context, then it would make sense to choose an inner product first, then obtain both the angles and the norm from this common inner product.

Now the problem is formulated as follows:

Given a (non-empty) set $S$ of line segments in $\mathbb{R}^n$, and an angle $\eta$, find all subsequences of $S$ that form a line relative to angle $\eta$. For each such sequence also compute the displacement sequence (as defined above).

share|improve this answer

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