1

I have huge list of 2d line segments. I want to find nearest line segments for a given segments and then to store in a vector. So, I want to do this for each and every line segment so that I know nearest line segments for any line segments. All my line segments are in vector form that is, I know both end point coordinates. So in my data line-number, 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 these things happen and give a vector of vector line segment numbers or some other way to recognize proximity line segments. I know kd-tree (k-nearest) can do the similar thing. But it is for point data.

I was trying to figure out this with opencv r-tree function. But as I do not have any experience of using r-tree I was not able and I am confused now because it says about a classifier and has 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 type of thing, please let me know.

Community
  • 1
  • 1
niro
  • 947
  • 3
  • 13
  • 30
  • How big is "huge"? What sort of system do you have to solve the problem on? [Might make a difference if it's a mobile phone or a 1000-machine cluster with 64GB and 16 cores per system] – Mats Petersson Feb 24 '13 at 19:21
  • @Mats Petersson: in my data, nearly 40,000 line segments are wit me. its 1gb ram with 1.4 ghz dual core machine. – niro Feb 24 '13 at 20:51
  • And do you have a time-limit (e.g. needs to do this every 1/50th of a second or some such)? – Mats Petersson Feb 24 '13 at 21:18
  • What about a KD-Tree? http://stackoverflow.com/questions/1498949/data-structure-for-fast-line-queries – Justin Feb 24 '13 at 22:04
  • @Mats Petersson: Not that much. but i wish to do this data structures as handling data might be much easier when doing codes as I know sepeteate proximity line seg. lists – niro Feb 24 '13 at 23:41
  • @Justin: Actually, I mentioned kd-tree in my post (as k-nearest), But as far as i know it is defined for point data. (even the above link also said the same)... so I was struggling to do this with kd-tree as it was too hard for me, then i am now looking for some other options – niro Feb 24 '13 at 23:45
  • @niro OK, you never mentioned KD-Trees by name, so I didn't know. You can use a KD-Tree with line segments which is part of the link I sent. Here is the direct link to the comment stackoverflow.com/a/1498995/950252 but it is non-trivial. – Justin Feb 24 '13 at 23:57
  • @Justin: true, i tried with that way..(the kd-tree) it is hard and not the best option. from that page also they mentioned r-tree. – niro Feb 25 '13 at 00:46

1 Answers1

0

While OpenCV doesn't have a data structure for line segments, the following works well enough. 

struct LineSegment{
  Point2f a,b;
};
bbrame
  • 18,031
  • 10
  • 35
  • 52
  • @UlrichEckhardt , Why? Is there a C++ convention I'm ignoring? I copied and pasted this out of my C++ program. Thanks! – bbrame Feb 14 '15 at 19:47