tpitkanen
commented
2 years ago Seems like there's a nasty nested loop in Measurement.save_cuts where the innermost functions (Selection.get_points() and math_functions.point_inside_polygon()) are slow.
Measurement.save_cuts()
# Go through all points in measurement data
data_count = len(self.data)
for n in range(data_count): # while n < data_count:
if n % 5000 == 0:
# Do not always update UI to make it faster.
if progress is not None:
progress.report(n / data_count * 80)
point = self.data[n]
# Check if point is within selectors' limits for faster processing.
if not self.selector.axes_limits.is_inside(point):
continue
for i, selection in enumerate(self.selector.selections):
if selection.point_inside(point):
points_in_selection[i].append(point)Selection.point_inside()
def point_inside(self, point):
"""Check if point is inside selection.
Args:
point: [X, Y] representing a point.
Return:
Returns True if point is within selection. False otherwise.
"""
if not self.axes_limits.is_inside(point):
return False
inside = mf.point_inside_polygon((point[0], point[1]),
self.get_points())
# While at it, increase event point counts if not counted already.
if inside and not self.events_counted:
self.event_count += 1
return inside
Selection.get_points()
def get_points(self):
"""Get points in selection
Get points in selection in list. Format: ((x1,y1), (x2,y2), ...).
If no points, empty list is returned
Return:
((x1, y1), (x2, y2), ...)
"""
points = self.points.get_data()
pointlist = []
for i in range(len(points[0])):
pointlist.append([points[0][i], points[1][i]])
return pointlistmath_functions.point_inside_polygon()
def point_inside_polygon(point, poly):
"""Finds out if a point x, y is inside a polygon "poly"
Determine if a point is inside a given polygon or not
Polygon is a list of (x,y) pairs.
Algorithm got from: http://www.ariel.com.au/a/python-point-int-poly.html
"""
# TODO test using shapely or numpy for this
x, y = point
n = len(poly)
inside = False
p1x, p1y = poly[0]
for i in range(n + 1):
p2x, p2y = poly[i % n]
if y > min(p1y, p2y):
if y <= max(p1y, p2y):
if x <= max(p1x, p2x):
if p1y != p2y:
xinters = (y - p1y) * (p2x - p1x) / (p2y - p1y) + \
p1x
if p1x == p2x or x <= xinters:
inside = not inside
p1x, p1y = p2x, p2y
return insideThere's a TODO for # TODO test using shapely or numpy for this in math_functions.point_inside_polygon(), but I think Selection.get_points() is a problem too. This could be faster if the Selection.get_points() was cached with lru_cache, or maybe just called once for each selection in Measurement.save_cuts() and then passed to Selection.point_inside(). We could also save the Selection.get_points() in the Selection object and update it when it changes (or when it's needed), but that has the potential for cache invalidation issues.
tleppala
jaakkojulin
Generic algorithm is used to check if point is inside selection polygon. Algorithm is called about num_points x selections times when points in cuts are tested (also algorithm tests for each side of polygon). As data is discrete with 8k steps, more efficient algorithm might be to convert selection polygons to max_y, min_y arrays. By doing so testing if point is inside selection requires at most 2 comparisons (using full arrays). Limitations using this method is there can't be multiple regions in single x (or y if other direction is used) position. If this is deemed to be problem method can be refined for such eventualities (maybe split affected selections to multiple pieces to remove problem areas). Also this conversion is requires to be made only once.