Storing a straight line equation

How to store a straight line (infinite length, not a line segment) efficiently?

This is not a duplication of How to represent a geometric line programmatically?, because the linked question is about 3D, and it does not answer the main problem reflected in this question.

Definition of a straight line:

This question is asking about the data structure, not user interface. I don’t care about how the equation is defined or presented (because I’m not making a graphing calculator).

Basically, a straight line is an equation (not necessarily a function of x or y) that, when drawn on a rectangular coordinate system, results in an infinitely long line, of any inclination (slope), at any intercept (assuming that the floating point range is not exceeded).

Therefore, these are all valid straight line equations:

y = x
y = -2x
y = x + 3
y = 4x + 5
x = 6
y = 7

They all stand for a straight line, as shown in https://www.desmos.com/calculator/jnotvj4k7u

I am trying to create a type (class or a class hierarchy) (in Java, if language matters) that can represent any of these straight lines.

Possible uses of a straight line:

  • Used in an image, such as imageline in GD to draw a line that cuts the image (the inverted Y-axis is a minor problem irrelevant to this question). For example, the equation y = x can cut an image diagonally.
  • Stored in a file. The structure in the file should be same as that in code.
  • Implement the equals and hashCode methods that work for identical lines.
  • Evaluate the intersection point of two straight lines.
  • Evaluate the intersection point(s) of a straight line and, say, a quadratic equation (given double a, double b, double c for ax^2 + bx + c = 0) or a circle (given Point center and double radius)

My question

I have considered three possible methods, which will be listed as an answer below: https://softwareengineering.stackexchange.com/a/324229/234322

My question is, is there a fourth solution? Or, is there a way to minimize the disadvantages of these methods?

4

The equations can be all rewritten into form :

a*X + b*Y + c = 0

That means you can store three doubles a, b and c.

This doesn’t have a problem in representing an arbitrary slope. You can also calculate slope as a/b (or b/a). Two lines are equal if there exists k where a1*k = a2, b1*k=b2, c1*k = c2.

4

Possible methods

For convenience of expression, this class will be used to represent any real points in a coordinate system in code snippets below:

public class Point{
    public double x, y;

    @Override public boolean equals(Object other){
        if(!(other instanceof Point)) return false;
        Point point = (Point) other;
        return point.x == this.x && point.y == this.y;
    }
}

Method 1: slope + (Y-)intercept

Using the slope-intercept form, a class like this (in Java) can be created:

public class Line{
    public double slope;
    public double yIntercept;
}

This is a possible constructor to create a line that passes through two given points: (all straight lines have real points, so any two distinctive points can create a straight line)

public Line(Point pt0, Point pt1){
    if(pt0.equals(pt1)) throw new IllegalArgumentException("Cannot create straight line from two identical points");
    this.slope = (pt0.y - pt1.y) / (pt0.x - pt1.x);
    this.yIntercept = pt0.y - this.slope * pt0.x;
}

As most programmers can instinctively notice, there is a possible ArithmeticException of division by zero at line 1 of the constructor. What does this mean, if pt0 and pt1 are not equal? This means that two points have the same X-coordinate but different Y-coordinate, i.e. a vertical line (in a Y-X rectangular coordinate system) should be created. This also represents the equation x = x0, where x0 is a (mathematical) constant.

Even if we specifically check it and set slope to be java.lang.Double.NaN or java.lang.Double.POSITIVE_INFINITY, what about yIntercept? It should be NaN, because there are no solutions or infinite solutions. (Y-intercept means “Y-coordinate when x = 0”, which is either always true or always false for a x = x0 equation)

A possible solution is to represent a vertical line with an extra subclass (then we can use this subclass by hiding the class constructor and use a static getter Line.createFromTwoPoints(Point, Point) instead):

public class VerticalLine extends Line{
    private double xIntercept;
    public VerticalLine(double x){
        this.slope = Math.POSITIVE_INFINITY;
        this.yIntercept = Math.NaN;
        this.xIntercept = x;
    }
}

However, this method is inconvenient. It seems to single out the condition of a vertical line, which is not a special condition and should not be separated from the rest of conditions. It also creates an extra field in the VerticalLine class. If we use it in replacement of yIntercept, it doesn’t sound like a good idea to call a field yIntercept while it is in fact xIntercept, or use a field called intercept sometimes as the Y-intercept but sometimes as the X-intercept. This inconvenience becomes significant when there is a big mess of getters and utility functions, sometimes overriding, sometimes not overriding.

Method 2: direction + (Y-)intercept

Same with Method 1, except that the slope is replaced by its arc-tangent. This makes the infinite slope a java.lang.Math.PI direction instead, but still the same problem with the X- and Y-intercepts. Might also work slower because evaluation of intersection points might involve more calls to trigonometric functions.

Method 3: two-point form

This is very inefficient.

Memory

This requires storage of four doubles, rather than two to three doubles above.

Performance

The memory structure of two identical lines may not be identical. This means that the equals method and the hashCode method, and also many other methods, may involve more calculations. Refer to the “Possible uses” section in the main post regarding the content of “many other methods”.

11

A couple of possibilities:

The vector form of the equation for a straight line in 2 dimensions is n.x + s = 0, where ‘n’ is a vector normal (or perpendicular) to the line “.” is the vector dot product operation, and s is a scalar constant. This allows you to represent arbitrary lines with two integers and a double. (note that the same representation in 3 dimensions forms a plane, and so on). It might be more convenient to use doubles for the vector, however, and if you do that, using a unit vector might make sense. If your vector is a unit vector, “s” can be interpreted as the distance along the normal vector between the line and the origin.

A related representation is to note that a unit vector can be represented as an angle between the vector and one of the axes, so you could store that instead of the vector. This gives a representation of any arbitrary straight line with 2 doubles.

Depending on your application, these may or may not be efficient, but you should be able to profile them reasonably easily and decide which is best for you.

1

A single bit saying if the line is closer to horizontal or vertical. If closer to horizontal, slope + Y-intercept. If closer to vertical, inverse slope + X-intercept.

That’s two doubles, plus a bit.

Equality testing is trivial.

10

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *