2

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

enter image description here

niro
  • 947
  • 3
  • 13
  • 30
  • It is very nice if you draw your problem and show us. – masoud Jan 16 '13 at 16:20
  • *if i know the rectangular buffer limits, then which type of concept should i use to avoid unnecessary searches of line segments.* Bounding boxes are the obvious answer, so why don't you want to use them? – David Hammen Jan 16 '13 at 16:25
  • @David Hammen: for slant lines, bounding box contains many unnecessary lines so i want to avoid them. so the best one is the rectangle oriented along reference line. – niro Jan 16 '13 at 16:33
  • @M M: i have added an example image. thanks – niro Jan 16 '13 at 16:43

1 Answers1

1

First suggestion

Take a look at KD-Tree and R-Tree. They are for partitioning space to reduce some calculations. And there is many implementations as class library for them, same as libkdtree. I personally used KD-Tree before to reduce comparisons of finding nearest neighborhoods in a 2D space, it wasn't simple but it was effective.

Second suggestion

Instead of thinking about oriented rectangle (To testing if a point is inside of it or not), you can think about distance of a point from line segment.

enter image description here

Check if two start-point and end-point of an extracted segment are near enough to reference segment or not, gray area is a good approximate of your oriented rectangle.

Those segments in the gray capsule are suitable to match to reference segment, and you can ignore other segments. (If two points of an extracted segment are in gray area it can be good candidate to match to the reference segment. Otherwise you can ignore that segment.)

A segment has two points as start-point and end-point, and each point has two components as X and Y.

Segment ref(r.start, r.end);

foreach(seg : extracted segments)
{
  if (DistancePointSegment(seg.start, ref)<D &&
      DistancePointSegment(seg.end  , ref)<D )
  {
    // Mark seg as a search candidate
  }
}

To check distance of a point from a segment read this Shortest distance between a point and a line segment

Community
  • 1
  • 1
masoud
  • 55,379
  • 16
  • 141
  • 208
  • @M M.: thanks for the response. mm, my idea is to use simple geometry and to apply something like rectangle buffer. As i am poor in mathematics, i dont know clear idea how it would be and think, testing of point within polygon like way to check whether one end is inside or not... the think is I dont have clear idea to figure out this. – niro Jan 16 '13 at 16:47
  • @M M.: in case of kd-tree, how it would be?, what would be the inputs?... does it midpoint of each line or 2 ends of each line? – niro Jan 16 '13 at 17:10
  • 1
    @niro: I think my second suggestion is simpler – masoud Jan 16 '13 at 17:13
  • @M M:Seems i got little bit. but still confusing about this "two beginning and ending of a detected segment is enough near* to the black line (reference segment) or not" which mean, for example AB reference and CD dashed line, should i check AC, AD and BC, BD all possible distances or only the shortest distance from either A or B to C or D? – niro Jan 16 '13 at 17:20
  • @M M.: Yes..it is clear now. many thanks for your suggestion. I think I could do this with the kd-tree to increase the search speed. I also have little knowledge about working with kd-tree for point data. So, do you think can i take this as point handling problem and get all the near lines to a certain reference line. For that, i think i should take mid points of all line segments (including ref. line segments). do you think would this be the way to adopt kd-tree for obtaining nearby lines to a certain reference? after that, as we have now few lines to a certain ref, can check ur distance rule – niro Jan 16 '13 at 21:39
  • @M M.: I am soory for disturbing you again and again. i really donot have any idea how to represent line segments in kd-tree. i know only the point representing in kd-tree. so, please give some idea and suggestions on this too sir. thanks – niro Jan 16 '13 at 21:50
  • @niro: No problem. My first suggestion needs many study. If you have not enough time. Try to use my second suggestion. – masoud Jan 16 '13 at 22:22
  • @M M.: ok thank you. i thought to, first, apply kd-tree to limit the candidate line segments, then for those lines, i wish to apply second way to get more accurate result. if you donot mind, could you please let me know how can line segments be represented by kd-tree. should it convert to point list? – niro Jan 16 '13 at 22:28
  • @niro: I myself used KD-Tree for points not line segments. It's a litter harder. But I updated the answer and put some links in first section – masoud Jan 16 '13 at 22:31