1

I have a system of inequalities representing the area between pairs of concentric ellipses, as seen in the following diagram: Link to the graph on desmos enter image description here I want to calcualte the coordinates of the vertices of the polygon approximating the unshaded area. The ultimate goal is to calculate the minimum bounding circle of this polygon: enter image description here I've researched a similar question dealing with linear expressions which uses scipy.optimize.linprog, however I do not believe that this would be usable in this case I am dealing with quadratic equations and am not trying to find maximum or minimum values for an expression.

Jeremy
  • 661
  • 7
  • 19
  • 1
    This is a really interesting, and, in general, pretty difficult problem, so you kind of have to figure out how much generality you want to aim for. I think it would help others help you if you say what is the larger goal you're working towards. – Robert Dodier Mar 01 '22 at 19:23
  • @RobertDodier Yes, I can certainly share. The problem can basically be boiled down to: given four locations a, b, c, x determine the coordinates of x and approximate error given rounded measurements of the distance from each other point to x. These distances are rounded to the nearest integer. The way I thought to approach it is create two concentric ellipses centered at each point a, b, c where the inner ellipse represents the lower bound of actual distance (distance-0.5) and the outer ellipse represents the upper bound of actual distance (distance+0.5). – Jeremy Mar 01 '22 at 19:43
  • 1
    The biggest question is, do you need to solve this symbolically, i.e. given undetermined points a, b, c, derive a formula for x? Or do you need to solve it for specific cases, i.e. give a = something, b = something, c = something, find x for those values. Less pressing: how important is it to take the integer-ness of positions into account? Can you assume positions are real-valued and round to the nearest integer at the end? Also, do I understand correctly that the ellipses represent differing measurement precisions in horizontal vs vertical? and therefore the ellipses are always axis aligned? – Robert Dodier Mar 01 '22 at 20:58
  • 1
    To back up a little bit more -- what is the bigger picture in which this solution is a part? Are you working with locations of physical objects, or is this to find location of pixels on a screen? Another way to put, what are you going to do with the solution, once you have one? I don't mean to be difficult. As I was saying, this can be a pretty difficult problem, and the choices you make at steps along the way are going to have a pretty big impact on the solution. – Robert Dodier Mar 01 '22 at 21:01
  • @RobertDodier I understand, I don't need to solve this symbolically just for specific cases. This bigger picture is to calculate approximate location data from an API, which returns rounded distance in miles from the client location to a given resource. The API lets you set your location, so my plan is to use 3 clients with locations a few hundred miles apart, iterate over each resource, and request the distance data for each and approximate the resource location. The locations are specified in lon, lat so to approximate radial distance I considered ellipses – Jeremy Mar 01 '22 at 21:31
  • 1
    Great, thanks for the additional info. You want d(x, a) = d(x, b) = d(x, c) where d = distance. It's equivalent, and probably easier to work with square distance (no square root). One idea is to frame this as a minimization problem. Construct a figure of merit by subtracting right-hand side from left-hand side of each equation and squaring the difference, i.e. F(x) = (d(x, a)^2 - d(x, b)^2)^2 + (d(x, b)^2 - d(x, c)^2)^2. Then apply any reasonable algorithm, e.g. BFGS, conjugate gradient, etc. (I don't recommend gradient descent since there are much more powerful algorithms available.) – Robert Dodier Mar 02 '22 at 04:48
  • 1
    Since it's only two dimensions (in x), and there is presumably a global minimum, this is a relatively easy minimization problem. That said, there might be much better ways to approach this problem; I suspect it's well known. You might try math.stackexchange.com. Good luck and have fun. – Robert Dodier Mar 02 '22 at 04:50
  • @RobertDodier thanks, this sounds like a good solution. You’re right this is a trilateration problem, but there are no resources that I can find for solving the problem using non-exact measurements, but your solution sounds perfect! – Jeremy Mar 02 '22 at 15:14

0 Answers0