When Two Segments Intersect?

Problem

Given two segments in the plane, $P_{1}P_{2}$ and $Q_{1}Q_{2}.$ Specify a condition that insures that the two segments intersect.

Solution

The two segments define two lines, say, $xa_{i}+yb_{i}+c_{i}=0,\space i=1,2.$ The lines may or may not intersect. If they do not, neither do the segments. However, the segments may not intersect even when the lines do:

segments do not intersect

So finding the intersection of two lines would not solve the problem at hand. Nonetheless, the diagram may point us in the right direction. Let's first consider what might be a simpler problem. It should be simpler to check when a segment intersects a line:

segment intersects line

Given a line $xa+yb+c=0$ and a segment in the plane, $P_{1}P_{2}.$ Specify a condition that insures that the segment intersects the line.

The answer to this question is rather obvious: a segment intersects a line provided its end points lie on different sides of the line. (I ignore the possibility that the segment lies on the line.) How do we know when this happens?

A line $L(x,y)=xa+yb+c=0$ separates the plane into two half-planes: $\{(x,y):\space L(x,y)\gt 0\}$ and $\{(x,y):\space L(x,y)\lt 0\}$. It separates two points $P_{1}$ and $P_{2}$ if they lie in different half-planes defined by the line: for one $L(x,y)$ is positive, for the other, it's negative, i.e., when

$L(P_{1})L(P_{2})\lt 0.$

Returning to the initial problem, let $L_{p}(x,y)=0$ and $L_{q}(x,y)=0$ be the equation of the lines which carry segments $P_{1}P_{2}$ and $Q_{1}Q_{2},$ respectively. For the segments to intersect, one's end points need to be separated by the line defined by the other.

segments intersect

This happens when

$L_{q}(P_{1})L_{q}(P_{2})\lt 0$ and $L_{p}(Q_{1})L_{p}(Q_{2})\lt 0.$

Note: thes condition has been used on the Voronoi Diagram page to determine whether the edges of the Voronoi diagram and those of its dual intersect or not.

Related material
Read more...

  • What Is Line?
  • Functions, what are they?
  • Cartesian Coordinate System
  • Addition and Subtraction of Functions
  • Function, Derivative and Integral
  • Graph of a Polynomial of arbitrary degree
  • Graph of a Polynomial Defined by Its Roots
  • Inflection Points of Fourth Degree Polynomials
  • Lagrange Interpolation (an Interactive Gizmo)
  • Equations of a Straight Line
  • Taylor Series Approximation to Cosine
  • Taylor Series Approximation to Cosine
  • Linear Function with Coefficients in Arithmetic Progression
  • Sine And Cosine Are Continuous Functions
  • |Contact| |Front page| |Contents| |Algebra|

    Copyright © 1996-2018 Alexander Bogomolny

     65095029