1# Copyright 2014 The Chromium Authors. All rights reserved.
2# Use of this source code is governed by a BSD-style license that can be
3# found in the LICENSE file.
4
5"""This module provides implementations of common computer Vision operations."""
6
7from __future__ import division
8from telemetry.internal.util import external_modules
9
10np = external_modules.ImportRequiredModule('numpy')
11
12
13def AreLinesOrthogonal(line1, line2, tolerance):
14  """Returns true if lines are within tolerance radians of being orthogonal."""
15  # Map each line onto an angle between 0 and 180.
16  theta1 = np.arctan2(np.float(line1[1] - line1[3]),
17                      np.float(line1[0] - line1[2]))
18  theta2 = np.arctan2(np.float(line2[1] - line2[3]),
19                      np.float(line2[0] - line2[2]))
20  angle2 = abs(theta2 - theta1)
21  if angle2 >= np.pi:
22    angle2 -= np.pi
23  # If the difference between the angles is more than pi/2 - tolerance, the
24  # lines are not orthogonal.
25  return not abs(angle2 - (np.pi / 2.0)) > tolerance
26
27
28def FindLineIntersection(line1, line2):
29  """If the line segments intersect, returns True and their intersection.
30  Otherwise, returns False and the intersection of the line segments if they
31  were to be extended."""
32  # Compute g, and h, the factor by which each line must be extended to
33  # exactly touch the other line. If both are between 0 and 1, then the lines
34  # currently intersect. We use h to compute their intersection.
35  line1p1 = line1[:2]
36  line1p0 = line1[2:]
37  line2p1 = line2[:2]
38  line2p0 = line2[2:]
39  E = np.subtract(line1p1, line1p0)
40  F = np.subtract(line2p1, line2p0)
41  Pe = np.asfarray((-E[1], E[0]))
42  Pf = np.asfarray((-F[1], F[0]))
43  h = np.dot(np.subtract(line1p0, line2p0), Pe)
44  h = np.divide(h, np.dot(F, Pe))
45  g = np.dot(np.subtract(line2p0, line1p0), Pf)
46  g = np.divide(g, np.dot(E, Pf))
47  intersection = np.add(line2p0, np.dot(F, h))
48  intersect = (h >= -0.000001 and h <= 1.000001 and
49               g >= -0.000001 and g <= 1.000001)
50  return intersect, intersection
51
52
53def ExtendLines(lines, length):
54  """Extends lines in an array to a given length, maintaining the center
55  point. Does not necessarily maintain point order."""
56  half_length = length / 2.0
57  angles = np.arctan2(lines[:, 1] - lines[:, 3], lines[:, 0] - lines[:, 2])
58  xoffsets = half_length * np.cos(angles)
59  yoffsets = half_length * np.sin(angles)
60  centerx = (lines[:, 0] + lines[:, 2]) / 2.0
61  centery = (lines[:, 1] + lines[:, 3]) / 2.0
62  lines[:, 0] = centerx - xoffsets
63  lines[:, 2] = centerx + xoffsets
64  lines[:, 1] = centery - yoffsets
65  lines[:, 3] = centery + yoffsets
66  return lines
67
68
69def IsPointApproxOnLine(point, line, tolerance=1):
70  """Approximates distance between point and line for small distances using
71  the determinant and checks whether it's within the tolerance. Tolerance is
72  an approximate distance in pixels, precision decreases with distance."""
73  xd = line[0] - line[2]
74  yd = line[1] - line[3]
75  det = ((xd) * (point[1] - line[3])) - ((yd) * (point[0] - line[2]))
76  tolerance = float(tolerance) * (abs(xd) + abs(yd))
77  return abs(det) * 2.0 <= tolerance
78
79
80def SqDistances(points1, points2):
81  """Computes the square of the distance between two sets of points, or a
82  set of points and a point."""
83  d = np.square(points1 - points2)
84  return d[:, 0] + d[:, 1]
85
86
87def SqDistance(point1, point2):
88  """Computes the square of the distance between two points."""
89  d = np.square(point1 - point2)
90  return d[0] + d[1]
91