0
$\begingroup$

Suppose I knew the endpoints of various different lines within a 2D plane. For example, A = (1,1) B = (2,1) C = (3,4) D = (1,1)

Now, there are lines AB and CD, with a common point of (1,1).

However, I would like to determine whether they intersect, excluding the point (1,1).

Is there a way to do this?

$\endgroup$
  • $\begingroup$ I don't understand what you're asking. If two different lines intersect, they intersect at a single point, so what do you mean by asking if they intersect once you exclude the point where they intersect? $\endgroup$ – D.W. Sep 23 at 6:44
  • $\begingroup$ en.wikipedia.org/wiki/Line%E2%80%93line_intersection $\endgroup$ – D.W. Sep 23 at 6:44
  • $\begingroup$ Suppose there are 2 lines whose endpoints intersect, but don't intersect anywhere else. I want to be able to create an algorithm that detects whether an intersection has occurred, excluding the endpoints $\endgroup$ – flutterbug98 Sep 23 at 7:43
  • $\begingroup$ If the endpoints intersect, then either (a) the two lines are identical, or (b) they have at most one point of intersection -- so once you exclude the common point, there is no other point of intersection. $\endgroup$ – D.W. Sep 23 at 15:23
  • $\begingroup$ @D.W. I think OP only wants to exclude the given endpoints. For example, if given A=(0,0),B=(1,1),C=(1,0),D=(0,1), OP may want to output (0.5,0.5). Of course, all is my guess. $\endgroup$ – xskxzr Sep 24 at 3:18
0
$\begingroup$

This is an answer copied from StackOverflow. It is wrote by Gareth Rees.

There’s a nice approach to this problem that uses vector cross products. Define the 2-dimensional vector cross product v × w to be vx wyvy wx.

Suppose the two line segments run from p to p + r and from q to q + s. Then any point on the first line is representable as p + t r (for a scalar parameter t) and any point on the second line as q + u s (for a scalar parameter u).

Two line segments intersecting

The two lines intersect if we can find t and u such that:

p + t r = q + u s

Formulae for the point of intersection

Cross both sides with s, getting

(p + t r) × s = (q + u s) × s

And since s × s = 0, this means

t (r × s) = (qp) × s

And therefore, solving for t:

t = (qp) × s / (r × s)

In the same way, we can solve for u:

(p + t r) × r = (q + u s) × r

u (s × r) = (pq) × r

u = (pq) × r / (s × r)

To reduce the number of computation steps, it's convenient to rewrite this as follows (remembering that s × r = − r × s):

u = (qp) × r / (r × s)

Now there are four cases:

  1. If r × s = 0 and (qp) × r = 0, then the two lines are collinear.

    In this case, express the endpoints of the second segment (q and q + s) in terms of the equation of the first line segment (p + t r):

    t0 = (qp) · r / (r · r)

    t1 = (q + sp) · r / (r · r) = t0 + s · r / (r · r)

    If the interval between t0 and t1 intersects the interval [0, 1] then the line segments are collinear and overlapping; otherwise they are collinear and disjoint.

    Note that if s and r point in opposite directions, then s · r < 0 and so the interval to be checked is [t1, t0] rather than [t0, t1].

  2. If r × s = 0 and (qp) × r ≠ 0, then the two lines are parallel and non-intersecting.

  3. If r × s ≠ 0 and 0 ≤ t ≤ 1 and 0 ≤ u ≤ 1, the two line segments meet at the point p + t r = q + u s.

  4. Otherwise, the two line segments are not parallel but do not intersect.

Credit: this method is the 2-dimensional specialization of the 3D line intersection algorithm from the article "Intersection of two lines in three-space" by Ronald Goldman, published in Graphics Gems, page 304. In three dimensions, the usual case is that the lines are skew (neither parallel nor intersecting) in which case the method gives the points of closest approach of the two lines.

$\endgroup$
  • $\begingroup$ I don't think this answers the question that was asked, since the question that was asked talks about excluding a particular point. $\endgroup$ – D.W. Sep 23 at 15:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.