CODEWITHSUNDEEP
algorithmmathgeometryformula
Rella
Rella

Reputation: 66935

How to formulate such problem mathematicaly? (line continuation search)

I have an array of "lines" each defined by 2 points. I am working with only the line segments lying between those points. I need to search lines that could continue one another (relative to some angle) and lie on the same line (with some offset)

I mean I had something like 3 lines

alt text

I solved some mathematical problem (formulation of which is my question) and got understanding that there are lines that could be called relatively one line (with some angle K and offset J)

alt text

And of course by math formulation I meant some kind of math formula like

alt text

Upvotes: 2

Views: 562

Answers (3)

pcantin
pcantin

Reputation: 554

Starting with: A = a2 – a1 where a1 and a2 are the angle of the two lines.

We can do this:

tan(A) = tan(a1 – a2) = (tan(a2) – tan(a1)) / (1 + tan(a1) tan(a2))

If tan(a2) is bigger than tan(a1) then tan(A) will be the acute angle between the two lines. You can then check tan(A) against your tolerance.

So I guess the formula would be:

tan(A) = (tan(a2) – tan(a1)) / (1 + tan(a1) tan(a2)) when tan(a2) > tan(a1)

But I'm no mathematician

Upvotes: 1

Victor Liu
Victor Liu

Reputation: 3643

  1. Sort all your segments based on angle (in range 0 to Pi), and build a sorted map of angle-to-segment.
  2. Decide on some angle difference threshold below which two segments can be considered parallel. Iterate through your map and for each mapping, consider adjacent mappings on either side of the angle (needs wrap around) which are considered parallel.
  3. Within each set of nearly-parallel segments, see if they are "continuations" of each other.

Two segments (A,B) and (C,D) are roughly collinear if all possible pairings of the 4 points are roughly parallel. You can use the same test as above.

Pseudo-code:

Angle(A,B)
    return Atan((B.y-A.y) / (B.x-A.x)) // use atan2 if possible, but needs wrapping

NearlyParallel(angle1, angle2)
    delta = Abs(angle1-angle2)
    return (delta < threshold) or (delta > Pi-threshold)

Collinear(A,B, C,D)
    // Assume NearlyParallel(Angle(A,B), Angle(C,D)) == true
    return NearlyParallel(Angle(A,C), Angle(B,D)) and NearlyParallel(Angle(A,D), Angle(B,C))

Upvotes: 1

second
second

Reputation: 28637

What have you tried so far?

I guess one way is to look for pairs of lines where:

  1. the directions are similar |theta_1 - theta_2| < eps for some eps
  2. there is at least one pair of end points where the points are close

Depending on the size of your problem you may be able to just check all pairs of lines for the conditions

Upvotes: 1

Related Questions