How to determine if a segment passes through the positive X axis?

Question

A segment is defined by two endpoints $(x_1, y_1)$ and $(x_2, y_2)$.

The positive X axis for simplicity can be defined as the segment going from $(0, 0)$ to $(10^9, 0)$ (I'm working on a program where the maximum $X$ value is $10^6$ therefore this is good enough). Although a formula that doesn't rely on endpoints (for the axis) is also acceptable (and probably even better).

What I currently have is an algorithm that detects segment intersections, so I use the segment from $(0, 0)$ to $(10^9, 0)$ explained above. The algorithm I'm using is a $O(1)$ check that uses cross product for getting the orientation of points (code below).

But I'm wondering if there's a more elegant way to do this. I just want to refactor the code since this is the only intersection I need to do, and it looks a bit ugly to have all this code just for this. I suspect even a more elegant way would need some cross product stuff, but any idea is appreciated!

C++ code of my current algorithm.

struct Segment {
  Point p, q;

  int orientation(Point p, Point q, Point r) {
    ll val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
    if (val == 0) return 0;
    return (val > 0) ? 1 : 2;
  }

  bool intersect(const Segment& s) {
    Point p1 = p;
    Point q1 = q;
    Point p2 = s.p;
    Point q2 = s.q;
    int o1 = orientation(p1, q1, p2);
    int o2 = orientation(p1, q1, q2);
    int o3 = orientation(p2, q2, p1);
    int o4 = orientation(p2, q2, q1);
    return (o1 != o2 && o3 != o4);
  }
};

Answer 1

If you trace the intersect function step by step, and if you exclude the cases where $y_1 = 0$ and where $y_2 = 0,$ you might notice that two of the calls to orientation are merely testing whether $y_1 > 0$ and whether $y_2 > 0.$ The return statement then checks whether those two results are different, that is, whether $y_1$ and $y_2$ are on opposite sides of the $x$ axis.

In the cases where $y_1 = 0$ and where $y_2 = 0,$ the two calls to orientation will return two different values (indicating an intersection with the $x$ axis) except, bizarrely, in the case where $y_1 = y_2 = 0$ (in which case the algorithm will tell you that the segment does not intersect the $x$ axis).

One of the two remaining calls to orientation -- the one that compares the point $(10^9, 0)$ with the points $(x_1, y_1)$ and $(x_2, y_2)$ -- is always going to return the same value as every other time, unless you're so unlucky that someone gives you points like $(x_1, y_1) = (10^9+1, 1)$ and $(x_2, y_2) = (10^9+1, -1).$ So ideally you would skip this call to orientation and merely check whether the one remaining call -- which compares $(0,0)$ with $(x_1, y_1)$ and $(x_2, y_2)$ -- returns the result that puts $(0,0)$ on the desired side of the line through $(x_1, y_1)$ and $(x_2, y_2).$

This last call to orientation will use $(x_1, y_1)$ and $(x_2, y_2)$ as the first two arguments (in one order or the other) and $(0,0)$ as the third argument, so it will set val to either

$$(y_1 - y_2) x_1 - (x_1 - x_2) y_1$$

or the exact opposite of that quantity (changing the sign), and it will reliably always set val to the same sign for every example where the line through $(x_1, y_1)$ and $(x_2, y_2)$ intersects the positive $x$ axis. Which sign that is just depends on the order in which it receives the first two arguments.

Since all we need to do is get a consistent sign, we can assume we will compute $(y_1 - y_2) x_1 - (x_1 - x_2) y_1$ rather than the opposite. To find out which sign is the one that says "intersects positive $x$ axis," we just need to work out one example. Let's suppose $(x_1, y_1) = (1, 1)$ and $(x_2, y_2) = (1, -1).$ This is a segment that intersects the positive $x$ axis, and

$$ (y_1 - y_2) x_1 - (x_1 - x_2) y_1 = 2\times 1 - 0 \times 1 = 2. $$

One more detail to figure out. Consider the segment defined by $(x_1, y_1) = (0, 1)$ and $(x_2, y_2) = (0, -1).$ This segment passes through the $x$ axis at $(0,0).$ Do you consider that to be an intersection with "the positive $x$ axis" or not? Note that the algorithm you are currently using will tell you that this segment does intersect the positive $x$ axis; I am merely unsure whether that is the answer you wanted or a defect in the implementation.

So what I would do is to write a function that returned the result true if both of the following two conditions are true:

• First condition: either $y_1 = 0,$ or $y_2 = 0,$ or $y_1$ and $y_2$ have opposite signs.
• Second condition: $(y_1 - y_2) x_1 - (x_1 - x_2) y_1 > 0$ (unless you think passing through $(0,0)$ should count as an intersection with "the positive $x$ axis," in which case use $\geq$ instead of $>$).

Answer 2

Here is a simple code segment to implement my suggestion.

The first line returns false if the segment is entirely above or below the x axis. Otherwise, the second line returns true if, and only if, the x-intercept is non-negative, as you desire.

{
  if(p.y*q.y>0)return 0;
  return p.x+(q.x-p.x)*p.y/(p.y-q.y)>=0;
}

Answer 3

Segment $\{(x_1, y_1), (x_2, y_2)\}$ crosses $X$ axis when $$ y_1\cdot y_2 < 0 \land x = \in (x_1, x_2) \land x \gt 0 $$ where $$x = \frac{(x_2\cdot y_1 -x_1\cdot y_2)}{y_1 - y_2}$$

In C++ this may look like

bool intersect(double x1, double y1, double x2, double y2) {
    if ( y1 * y2 ) > .0
        return false;
    double x = (x2 * y1 - x1 * y2);
    return x > 0 && x > min(x1, x2) && x < max(x1,x2);
}

Answer 4

I just found another way to do this.

bool intersects_positive_x_axis() {
  if (p.cross(q) > 0) return q < p;
  return p < q;
}

Where $p$ and $q$ are the two endpoints of the segment, $cross$ is the cross product operator, and $<$ is the comparison by bearing (angle). Since I'm doing a polar sort with a radial sweep algorithm, I already had this implemented.

If $p \times q > 0$ then the segment endpoints are in counter clockwise order, but if the order by bearing is not the same, then it means the segment must be crossing the positive side of the x-axis. This is because points in the first quadrant have the lowest bearing value, and points in the fourth quadrant have the highest.

This code ignores the intersection with the point $(0, 0)$, which has not been tested.