CODEWITHSUNDEEP
javamathgeometry2d
CodeBunny
CodeBunny

Reputation: 2031

How do I stop one line segment from intersecting another?

Geometry code gets tiresome after a while, but I want to finish this library, so here goes.

Basically, what's the most efficient way to move one line segment, A, so that it no longer intersects with another, B?

Both line segments are defined with a start point (x, y) and a vector describing how the segment extends from that point (eX, eY). An example of how the line segment is described is below:

enter image description here

The solution I'm looking for is where the line segment is moved (its extent is not modified in any way) to the nearest location where it does not intersect. An example:

enter image description here

What is the most efficient way to get this result?

EDIT: People have asked what I mean by "move" - I mean change the (x, y) coordinate of the line segment start point. This will translate the entire segment.

And the line segments exist on the Cartesian plane, and any x/y movement is allowed.

Upvotes: 3

Views: 303

Answers (2)

Marko Topolnik
Marko Topolnik

Reputation: 200296

How about this: find the four vectors: two from red line's endpoints going perpendicularly to the black line, and two going perpendicularly from the red line to the black line's endpoints. Take the shortest of these vectors and move the red line along it.

Upvotes: 4

j13r
j13r

Reputation: 2671

Since you don't specify in which dimension you are free to move, I will assume that any are fine.

I assume your red line is characterized by a starting point (x,y), and a vector from there to the endpoint (eX,eY). Any point on the line is thus [0,1]*(eX,eY)+(x,y).

Lets find the point where lines cross. That's where a*(eX1,eY1)+(x1,y1) = (eX2,eY2)+(x2,y2) with a in [0,1].

If this crossing exists, you can just move the line so that it ends at this crosspoint, with a being the length you have to move.

(x1',y1') = (x1,y1) - a*(eX1,eY1)

This way, you move the starting point away until the crossing point you found before is the touching point of the two lines.

Upvotes: 0

Related Questions