问题

我有以下点配置：

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]])
这可以表示为：

[![在这里输入图片描述][1]][1]

给定 `T`、`X1` 和 `X2`，我想找到数组 `points` 中位于黄色区域内的所有点。这个黄色区域总是位于点 `X1` 和 `X2` 的“对面”。

如何以简单高效的方式实现这一目标？

**编辑1**（尝试 B Remmelzwaal 的解决方案）

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

valid_points = list()

# 计算线 T, X1 的 y = mx + b
slope1 = np.diff(list(zip(T, X1)))
m1 = np.divide(slope1[1], slope1[0])
b1 = T[1] - m1 * T[0]

# 计算线 T, X2 的 y = mx + b
slope2 = np.diff(list(zip(T, X2)))
m2 = np.divide(slope2[1], slope2[0])
b2 = T[1] - m2 * T[0]

for point in points:
    # 检查点是否在两条线的下方
    for m, b in (m1, b1), (m2, b2):
        if point[1] > m * point[0] + b:
            break
    else:
        # 仅在两个检查都通过时追加
        valid_points.append(point)

print(valid_points)

配置如下：

代码返回 [2, 5]，但应返回 []。这是不正确的，因为兴趣区域现在在相反的区域（请参见图像）

<details>
<summary>英文:</summary>

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:

[![enter image description here][1]][1]


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 &quot;opposite side&quot; 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] &gt; m*point[0] + b:
                break
        else:
            # only append if both checks pass
            valid_points.append(point)
            
    print(valid_points)

The configuration is the following: 
[![enter image description here][2]][2]
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)


  [1]: https://i.stack.imgur.com/I5mwA.png
  [2]: https://i.stack.imgur.com/mzaf7.png

</details>


# 答案1
**得分**: 1

```python
一个相当天真的解决方案，但它应该能胜任：

```python
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]])

valid_points = list()

# 计算 T、X1 线的 y = mx + b
slope1 = np.diff(list(zip(T, X1)))
m1 = np.divide(slope1[1], slope1[0])
b1 = T[1] - m1*T[0]

# 计算 T、X2 线的 y = mx + b
slope2 = np.diff(list(zip(T, X2)))
m2 = np.divide(slope2[1], slope2[0])
b2 = T[1] - m2*T[0]

for point in points:
    # 检查点是否位于两条线下方
    for m, b in (m1, b1), (m2, b2):
        if point[1] > m*point[0] + b:
            break
    else:
        # 只有在两个检查都通过时才追加
        valid_points.append(point)
        
print(valid_points)

这段代码假定 xT != xX1 和 xT != xX2，但你没有提到这是一个选项。

<details>
<summary>英文:</summary>

A pretty naive solution, but it should do the job:

```python
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]])

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] &gt; m*point[0] + b:
            break
    else:
        # only append if both checks pass
        valid_points.append(point)
        
print(valid_points)

This code does assume that xT != xX1 and xT != xX2, but you haven't mentioned that being an option.

答案2

得分: 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..)"

"非常简单的解决方案可以被看作是一系列的步骤

• 将值嵌入到方程中，使用双点形式
• 对由方程定义的每条线
  • 对要比较的集合中的每个点
    • 在X处，查看Y是否在线的值下面
• 对结果进行布尔AND运算，以便只有在两条线下面的值匹配

然而，使用NumPy强大的数值方法可以使这个过程更快，因为您可以直接使用集合中的值，而不必创建中间方程，但需要以NumPy期望的方式提出问题，这在处理大量线（数百、数百万...）时会更有意义。"

"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]

"或者，您可以仔细排序您的点并使用叉积"

"注意，这里点的排序很重要，以至于在线（矢量）的下面的点实际上在线的右边，您可以通过比较点的X值来计算这一点"

>>> 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])

"最后，在较大的程序中，您可能需要特殊处理那些确切相同的点对"

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]

>>> 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])