Question

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

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)

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

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

 Angle(A,B)
  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=)

Answer 1

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).