
February 28th, 2013, 04:45 AM
#1
2D line segment handling with data structures
I have huge list of 2d line segments. I want to find nearest line segments for a given segment and then to store in a vector. So, I want to do this for each and every line segment. therefore, I know nearest line segments for any line segments at the end (This is what I need). All my line segments are in vector form that is, I know both end point coordinates. So in my data linenumber, begin (x,y,z), end(x,y,z) are there.
For obtaining the line segments, I want to check the distance between the line segment and end point of another line segment (this).
I think there might be some data structures that all of these things happen and give a vector of vector line segment numbers or some other way to recognize proximity line segments. I know kdtree (knearest) can do the similar thing. But it is for point data.
I was trying to figure out this with opencv rtree function. But as I do not have any experience of using rtree I was not able and I am confused now because it says about a classifier and also something about a training phase. But for my case, I feel I don’t want such things to follow.
If anyone knows any function or codes or library to do this thing, please let me know. thanks in advance.

March 1st, 2013, 04:16 AM
#2
Re: 2D line segment handling with data structures
So in my data linenumber, begin (x,y,z), end(x,y,z) are there.
If this is a 2D problem, then the points are (x, y). Anyway ...
The shortest distance between a line, defined by points (x_{1}, y_{1}) and (x_{2}, y_{2}), and a third point (x_{3}, y_{3}) is:
Shortest Distance = (x_{3}  x_{1})(y_{2}  y_{1}) + (x_{1}  x_{2})(y_{3}  y_{1}) / (Distance between points (x_{1}, y_{1}) and (x_{2}, y_{2}))
For the case of a line segment, the third point could lie in one of three regions. The three regions are separated by two parallel lines which are perpendicular to the line segment. One line passes through (x_{1}, y_{1}) and the other line passes through (x_{2}, y_{2}). If the third point lies in the middle region between these two parallel lines, then the above equation is used to calculate the shortest distance. If the third point lies in the other two regions, then the shortest distance is the distance between the closest endpoint and the third point.

March 2nd, 2013, 04:15 PM
#3
Re: 2D line segment handling with data structures
@Coder Dave: thank you for the response. I think I confused you.. (non native english speaker.. sorry). I already done that function. What I am looking is any data structures which can work with line segments. I know rtree can. But in opencv, all built in rtree function are developed doing something like classification as classifier, training phases are there. What I am looking for is, any rtree function which gives proximity line segments (that mean, based on the above distance check function) neigbours should be selected and give a vec of vec line segments.
Tags for this Thread
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Click Here to Expand Forum to Full Width
This a Codeguru.com survey!
