CODEWITHSUNDEEP
c++algorithmimage-processinggeometrycomputational-geometry
niro
niro

Reputation: 977

How to limit search space using 2D rectangular buffer along a 2d line segment

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

Upvotes: 2

Views: 391

Answers (1)

masoud
masoud

Reputation: 56479

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

Upvotes: 1

Related Questions