TheAlgorithms-Python

1
"""
2
Check if three points are collinear in 3D.
3

4
In short, the idea is that we are able to create a triangle using three points,
5
and the area of that triangle can determine if the three points are collinear or not.
6

7

8
First, we create two vectors with the same initial point from the three points,
9
then we will calculate the cross-product of them.
10

11
The length of the cross vector is numerically equal to the area of a parallelogram.
12

13
Finally, the area of the triangle is equal to half of the area of the parallelogram.
14

15
Since we are only differentiating between zero and anything else,
16
we can get rid of the square root when calculating the length of the vector,
17
and also the division by two at the end.
18

19
From a second perspective, if the two vectors are parallel and overlapping,
20
we can't get a nonzero perpendicular vector,
21
since there will be an infinite number of orthogonal vectors.
22

23
To simplify the solution we will not calculate the length,
24
but we will decide directly from the vector whether it is equal to (0, 0, 0) or not.
25

26

27
Read More:
28
    https://math.stackexchange.com/a/1951650
29
"""
30

31
Vector3d = tuple[float, float, float]
32
Point3d = tuple[float, float, float]
33

34

35
def create_vector(end_point1: Point3d, end_point2: Point3d) -> Vector3d:
36
    """
37
    Pass two points to get the vector from them in the form (x, y, z).
38

39
    >>> create_vector((0, 0, 0), (1, 1, 1))
40
    (1, 1, 1)
41
    >>> create_vector((45, 70, 24), (47, 32, 1))
42
    (2, -38, -23)
43
    >>> create_vector((-14, -1, -8), (-7, 6, 4))
44
    (7, 7, 12)
45
    """
46
    x = end_point2[0] - end_point1[0]
47
    y = end_point2[1] - end_point1[1]
48
    z = end_point2[2] - end_point1[2]
49
    return (x, y, z)
50

51

52
def get_3d_vectors_cross(ab: Vector3d, ac: Vector3d) -> Vector3d:
53
    """
54
    Get the cross of the two vectors AB and AC.
55

56
    I used determinant of 2x2 to get the determinant of the 3x3 matrix in the process.
57

58
    Read More:
59
        https://en.wikipedia.org/wiki/Cross_product
60
        https://en.wikipedia.org/wiki/Determinant
61

62
    >>> get_3d_vectors_cross((3, 4, 7), (4, 9, 2))
63
    (-55, 22, 11)
64
    >>> get_3d_vectors_cross((1, 1, 1), (1, 1, 1))
65
    (0, 0, 0)
66
    >>> get_3d_vectors_cross((-4, 3, 0), (3, -9, -12))
67
    (-36, -48, 27)
68
    >>> get_3d_vectors_cross((17.67, 4.7, 6.78), (-9.5, 4.78, -19.33))
69
    (-123.2594, 277.15110000000004, 129.11260000000001)
70
    """
71
    x = ab[1] * ac[2] - ab[2] * ac[1]  # *i
72
    y = (ab[0] * ac[2] - ab[2] * ac[0]) * -1  # *j
73
    z = ab[0] * ac[1] - ab[1] * ac[0]  # *k
74
    return (x, y, z)
75

76

77
def is_zero_vector(vector: Vector3d, accuracy: int) -> bool:
78
    """
79
    Check if vector is equal to (0, 0, 0) of not.
80

81
    Sine the algorithm is very accurate, we will never get a zero vector,
82
    so we need to round the vector axis,
83
    because we want a result that is either True or False.
84
    In other applications, we can return a float that represents the collinearity ratio.
85

86
    >>> is_zero_vector((0, 0, 0), accuracy=10)
87
    True
88
    >>> is_zero_vector((15, 74, 32), accuracy=10)
89
    False
90
    >>> is_zero_vector((-15, -74, -32), accuracy=10)
91
    False
92
    """
93
    return tuple(round(x, accuracy) for x in vector) == (0, 0, 0)
94

95

96
def are_collinear(a: Point3d, b: Point3d, c: Point3d, accuracy: int = 10) -> bool:
97
    """
98
    Check if three points are collinear or not.
99

100
    1- Create tow vectors AB and AC.
101
    2- Get the cross vector of the tow vectors.
102
    3- Calcolate the length of the cross vector.
103
    4- If the length is zero then the points are collinear, else they are not.
104

105
    The use of the accuracy parameter is explained in is_zero_vector docstring.
106

107
    >>> are_collinear((4.802293498137402, 3.536233125455244, 0),
108
    ...               (-2.186788107953106, -9.24561398001649, 7.141509524846482),
109
    ...               (1.530169574640268, -2.447927606600034, 3.343487096469054))
110
    True
111
    >>> are_collinear((-6, -2, 6),
112
    ...               (6.200213806439997, -4.930157614926678, -4.482371908289856),
113
    ...               (-4.085171149525941, -2.459889509029438, 4.354787180795383))
114
    True
115
    >>> are_collinear((2.399001826862445, -2.452009976680793, 4.464656666157666),
116
    ...               (-3.682816335934376, 5.753788986533145, 9.490993909044244),
117
    ...               (1.962903518985307, 3.741415730125627, 7))
118
    False
119
    >>> are_collinear((1.875375340689544, -7.268426006071538, 7.358196269835993),
120
    ...               (-3.546599383667157, -4.630005261513976, 3.208784032924246),
121
    ...               (-2.564606140206386, 3.937845170672183, 7))
122
    False
123
    """
124
    ab = create_vector(a, b)
125
    ac = create_vector(a, c)
126
    return is_zero_vector(get_3d_vectors_cross(ab, ac), accuracy)
127