4

I am trying to draw a line in MatPlotLib , and find all points above or below the line depending on the slope.

After reading this post, and reading about Cross Product, I believe this is the best approach for me to check the points.

I am unsure what would be the most optimal way to implement this in python.

v1 = {x2-x1, y2-y1}   # Vector 1
v2 = {x2-xA, y2-yA}   # Vector 2
xp = v1.x*v2.y - v1.y*v2.x  # Cross product

Has anyone tried implementing something similar ?

Is there some other way for me to find if points on the plot are above or below a line in MatPlotLib ?

eyllanesc
  • 235,170
  • 19
  • 170
  • 241
P Ved
  • 109
  • 3
  • 13
  • Look at the first part of [this answer](https://stackoverflow.com/a/44062109/2454357). Basically, if you have an `x-y` pair, you plug your `x` value into the equation for your line, say `y1=a+b*x` and compare the result to your `y`-value, i.e. if `y1>y`, the point is below the line and if `y1 – Thomas Kühn Aug 19 '17 at 06:14

2 Answers2

10

As seen e.g. in this question the cross product can indeed be used to determine whether a point lies above or below a line which is defined by two points.

So let a and b be two points defining a line, and p a (set of) point(s) for which we want to know the relative position to the line. Then if

numpy.cross(p-a, b-a) < 0

is True the point(s) lie above the line.

To be accurate here, "above" means that looking from point a towards point b, the point p lies to the left of the line.

This can be used to colorize points in a scatter plot differently depending on whether they're above or below the line, as seem below:

import numpy as np
import matplotlib.pyplot as plt

isabove = lambda p, a,b: np.cross(p-a, b-a) < 0

a = np.array([1,1])
b = np.array([4,3])

p1 = np.array([2,4])
p2 = np.array([3,1])

p = np.array([p1,p2])


fig, (ax,ax2) = plt.subplots(ncols=2, sharex=True, sharey=True)

ax.plot([a[0],b[0]],[a[1],b[1]], marker="o", color="k")
ax.scatter(p[:,0],p[:,1], c=isabove(p,a,b), cmap="bwr", vmin=0, vmax=1)

p = np.random.rand(10,2)*5

ax2.plot([a[0],b[0]],[a[1],b[1]], marker="o", color="k")
ax2.scatter(p[:,0],p[:,1], c=isabove(p,a,b), cmap="bwr", vmin=0, vmax=1)


ax.set_xlim(0,6)
ax.set_ylim(0,6)
plt.show()

enter image description here

ImportanceOfBeingErnest
  • 321,279
  • 53
  • 665
  • 712
  • Nice answer, especially if one indeed wants to know if point `p` is left or right of the line with direction `a -> b`. However, if one wants to strictly know if the point is *above or below* the line (i.e. bigger or smaller `y` value at given `x`) comparing to the line equation is still much simpler, because with the cross product you would still need to have an `if` clause testing for the orientation of the line. – Thomas Kühn Aug 19 '17 at 11:11
  • @Thomas You can simply make sure the x coordinate of point `a` is smaller than the one of `b`, i.e. sort the points along the x axis. That would automatically ensure that "above" means "above". The question which solution is simpler is probably more dependent on what you start with. If you have two points defining the line, the cross product is the preferable solution, if you have a slope and a y-intercept, the comparisson in terms of the y coordinate with respect to the line as in [this answer](https://stackoverflow.com/a/44062109/2454357). Of course each can be calculated from the other. – ImportanceOfBeingErnest Aug 19 '17 at 11:44
  • Hmm, good point about ordering the `x` values. I still have to make up my mind which calculation would be more efficient if you have many points. Of course the `np.cross` function makes the code look quite neat and probably also fast ... – Thomas Kühn Aug 19 '17 at 11:54
  • @Thomas Intuitively I would say evaluating the line equation is faster, as for `n` points it involves `n` multiplications and `n` comparisons. The cross product involves `2n` multiplications and `n` comparisons. – ImportanceOfBeingErnest Aug 19 '17 at 12:02
0

A dirty way - use the method for left/right with cross product (How to tell whether a point is to the right or left side of a line), then evaluate the slope of the line. If slope is negative, then any point left of the line is above the line, and if slope is positive any point left of the line is below the line. If the point is to the right, these are reversed. (Obviously the answer depends on the orientation of the y-axis, for my example up is negative and down is positive.) This method requires programming the special cases for vertical and horizontal lines. For horizontal lines, the cross product method will give you the point's position above the line. For vertical lines, there is no real answer, but we point to isLeftOfLine instead.

C++ code:

bool Point::isLeftOfLine(Line cmp)
{
    return ((cmp.p2.x - cmp.p1.x) * (y - cmp.p1.y) > (cmp.p2.y - cmp.p1.y) * (x - cmp.p1.x));
}

bool Point::isTopOfLine(Line cmp)
{
    if(cmp.p1.x == cmp.p2.x || cmp.p1.y == cmp.p2.y)
    {
        return isLeftOfLine(cmp);
    }
return isLeftOfLine(cmp) == cmp.slope() < 0;
}

double Line::slope()
{
    return (p2.y - p1.y) / (p2.x - p1.x);
}
onefineday
  • 1