Find points inside region delimited by two lines

Question

I have the following point configuration:

import numpy as np 

T=np.array([9,9])
X1=np.array([8,16])
X2=np.array([16,3])
points=np.array([[4, 15],
                 [13,17],
                 [2, 5],
                 [16,8]])

This can be represented as:

Given T, X1, and X2, I want to find all points of the array points that are inside the yellow region. This yellow region is always in the "opposite side" of the points X1 and X2.

How can I achieve this in a simple and efficient way?

Edit1 (trying B Remmelzwaal solution)

T=np.array([9,9])
X1=np.array([10,2])
X2=np.array([2,15])
points=np.array([[2, 5]])

valid_points = list()

# calculating y = mx + b for line T, X1
slope1 = np.diff(list(zip(T, X1)))
m1 = np.divide(slope1[1], slope1[0])
b1 = T[1] - m1*T[0]

# calculating y = mx + b for line T, X2
slope2 = np.diff(list(zip(T, X2)))
m2 = np.divide(slope2[1], slope2[0])
b2 = T[1] - m2*T[0]

for point in points:
    # check if point is under both lines
    for m, b in (m1, b1), (m2, b2):
        if point[1] > m*point[0] + b:
            break
    else:
        # only append if both checks pass
        valid_points.append(point)
        
print(valid_points)

The configuration is the following: and the code returns returns [2,5] and it should return []. This is not correct since the region of interest is now in the opposite region (see image)

Answer 1

The naive solution to this can be thought of as a series of stages

• embed the values into equations in a Two-Point Form
• for each line defined by the Equations
  • for each point in the collection to compare
    • at X, see if Y is below the line value
• boolean AND on the results, such that only values below both lines match

However, this can be much faster with NumPy's powerful numeric methods, as you can directly use the values in collections without bothering to create the intermediate equations, but need to then pose it in a manner it expects and would make more sense to do for a great number of lines (hundreds, millions..)

very extended approach

import numpy as np 

T=np.array([9,9])
X1=np.array([8,16])
X2=np.array([16,3])
points=np.array([[4, 15],
                 [13,17],
                 [2, 5],
                 [16,8]])

equations = []
for point_pair in [(T, X1), (T, X2)]:
    # extract points
    (x1, y1), (x2, y2) = point_pair  # unpack
    # create equation as a function of X to get Y
    fn = lambda x, x1=x1, y1=y1, x2=x2, y2=y2: (y2-y1)/(x2-x1)*(x-x1)+y1
    equations.append(fn)

results = {}  # dict mapping lines to their point comparisons
for index, equation in enumerate(equations):
    key_name = "line_{}".format(index + 1)
    results_eq = []
    for point in points:
        point_x, point_y = point  # unpack
        line_y = equation(point_x)
        results_eq.append(point_y < line_y)  # single bool
    array = np.array(results_eq)             # list -> array of bools
    results[key_name] = array                # dict of arrays of bools

# & is used here to compare boolean arrays such that both are True
final_truthyness = results["line_1"] & results["line_2"]
print(final_truthyness)

>>> print(final_truthyness)
[False False  True False]

---

Alternatively, you can carefully order your points and take the Cross Product

NOTE that the point ordering matters here such that points below are really to the right of the line (vector), you can calculate this by comparing the X values of the points

>>> X1[0] < T[0], X2[0] < T[0]             # determine point ordering
(True, False)
>>> a = np.cross(points - X1, T - X1) > 0
>>> b = np.cross(points - T, X2 - T) > 0
>>> a,b ; a&b                              # individual arrays ; AND
(array([ True, False,  True, False]), array([False, False,  True, False]))
array([False, False,  True, False])

Finally, you might take some caution in a larger program to special case point pairs which are exactly the same point