# Limiting search space for efficient line matching [closed]

I have 2D line segments extracted from an image. So i know end point coordinates of them. also, i have some reference 2d line segments. Both line segments are now in vector form. comparing to reference and extracted lines,I have huge amount of extracted lines segments.

What i want to do is to find conjugate line segment for each reference line from my extraction. that is I want to match line segments. But, to reduce the search area i wish to limit it in such a way that by defining a buffer zone around a reference line segment.

(1) My first question is how can i implement this buffer case with c++ as i am lacking with geometric theories.

Note: I dont want to use a bounding box and looking for a rectangular buffer which orient along the reference line.

(2) my second question is, if i know the rectangular buffer limits, then which type of concept should i use to avoid unnecessary searches of line segments.

Actually, I am looking a geometric base method

please do not think this as home work and i am really struggling because of my poor mathematics. thanks in advance.

Please look at the example. if i take bounding box (blue box) unnecessary lines come, if it is a buffer rectangle (red), which is oriented to main reference line (dark black) few lines come.

black line is - reference line and dashed lines are image based extracted lines

-

## closed as off topic by joriki, Austin Mohr, rschwieb, VelvetThunder, amWhyJan 18 '13 at 2:09

Questions on Mathematics Stack Exchange are expected to relate to math within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here.If this question can be reworded to fit the rules in the help center, please edit the question.

This belongs on one of the sites for computer science. There's a lot of work on algorithms and data structures for dealing with geometric objects like this so as to reduce the search effort, and people on those sites will likely know a lot more about that than people here. – joriki Jan 17 '13 at 11:53
@joriki: I think it is some math which is needed here, not any special data structures. I don't think this would benefit from migration. – robjohn Jan 17 '13 at 13:47

Given a reference line $\left(\begin{bmatrix}x_1\\y_1\end{bmatrix},\begin{bmatrix}x_2\\y_2\end{bmatrix}\right)$, note that the matrix $$M=\begin{bmatrix}x_2-x_1&y_2-y_1\\[9pt]y_1-y_2&x_2-x_1\end{bmatrix}$$ rotates and uniformly scales the reference line to a horizontal line since $$\begin{bmatrix}x_2-x_1&y_2-y_1\\[9pt]y_1-y_2&x_2-x_1\end{bmatrix}\left(\begin{bmatrix}x_2\\[9pt]y_2\end{bmatrix}-\begin{bmatrix}x_1\\[9pt]y_1\end{bmatrix}\right)=\begin{bmatrix}(x_2-x_1)^2+(y_2-y_1)^2\\[9pt]0\end{bmatrix}$$ Once rotated to a horizontal line, the bounding box would be exactly what you want for the red rectangle above. Matching inside the red rectangle should now be a simple matter of bounds checking. That is, simply apply $M$ to all the image lines and reject those that do not fall within the bounds based on the rotated (horizontal) reference line.