0

Goal:

For a point a and a rectangle B, I would like to calculate the shortest distance between these two objects.

Motivation

Because this calculation is part of the innermost loop of multiple loops, I would like to optimize this calculation as much as possible. With my current python knowledge, making use of dedicated NumPy functions should be the way to goal(?).

Some more details:

  • The situation is 2D; x,y coordinates
  • rectangle B is defined by a certain center-of-gravity/mid-point, and width and length (And thus not by a vector of points)
  • the distance is thus from a to the edges of the rectangle B

My current implementation makes use of the following idea: link. Here the rectangle is divided into multiple subareas. First, it is determined inside which sub-area of B a is located. Hereafter, the calculating the shortest distance between a and B is then straightforward. However, a lot of logic checking is required to determine inside which sub-area a is located. It looks something as following,

def distance_a_to_B(a:Point):
    if a in sub_area_1:
        return easy_calculation_1(a)
    if a in sub_area_2:
        return easy_calculation_2(a)
    if a in sub_area_3:
        return easy_calculation_3(a)
    etc

Ideally,

  • I would like to have an alternative/faster logic checking (Python improvement) or
  • a faster mathematical algorithm

Maybe...?

One possible alternative I came up with while writing this question, is to calculate a discrete amount of n points based on Bs chaterestics. From this vector of n points I think it is quite easy use NumPy to:

  • calculate the shortest distance between a and each point of the n points
  • find the smallest value of this new vector

For a larger n, this solution would become more precise with a higher performance cost. Do you think this could be a better solution? Or do you have any suggestions for a mathematical (and no approximation) algorithm?

EDIT: added extra clarification, that the distance is towards the edges of the rectangle B

Florian Metzger-Noel
  • 782
  • 10
  • 29
HerChip
  • 113
  • 10
  • Do you want to find the distance to a set of points, or the *rectangle itself*? If it's to a set, what points belong to this set? Corners only? Also, judging by the definition of rectangle, are they always aligned the same? – matszwecja Apr 20 '22 at 13:06
  • Good point, the goal is to find the distance towards a rectangle. I have added this info to the question. – HerChip Apr 20 '22 at 13:20
  • There's a thread about this problem here: https://stackoverflow.com/questions/52004232/how-to-calculate-the-distance-from-a-point-to-the-nearest-point-of-a-rectange I don't think, that you can speed up the inner loop with numpy. Numpy is great for working with large arrays and for performing operations on those. – Florian Metzger-Noel Apr 21 '22 at 09:38
  • Is your rectangle allowed to have rotation? – Florian Metzger-Noel Apr 21 '22 at 09:40
  • Although the innermost loop cannot (imho) be optimized using numpy, you could use numpy to optimize measuring the distance of n points to m rectangles using numpy arrays and operations on those. Can you provide more source code so I can understand the loops that you're running? – Florian Metzger-Noel Apr 21 '22 at 09:46

1 Answers1

0

I think, this is a nice implementation of the distance function:

from math import sqrt

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

class Rectangle:
    def __init__(self, center: Point, width: float, height: float):
        self.center = center
        self.width = width
        self.height = height

    def distance_to_point(self, point: Point) -> float:
        """ assuming that the distance to a point inside of this rect is zero """
        dx = abs(self.center.x - point.x) - (self.width * 0.5)
        dy = abs(self.center.y - point.y) - (self.height * 0.5)
        return sqrt((dx * (dx > 0)) ** 2 + (dy * (dy > 0)) ** 2)

I don't know, how well the Python interpreter translates this code. It is possible, to implement this approach completely branchless, which is a nice property for optimized code.

If you want to compare one point to many rectangles (1:n), you could store all rectangles in a numpy array and compare your point to all rectangles at once using numpy array functions. The same would be possible for n:1 comparison. This could greatly speed up the process!

Without knowing more about your loops I can't provide such a solution, though.

Florian Metzger-Noel
  • 782
  • 10
  • 29