1

I'm making a program that consists of a bunch of placable/moveable items in space, and each item has an invisible circle encompassing its size. The items can be parented to other items, so for each parent item I also want the smallest possible outer circle that encompasses the extent of all its children. For example, if I had a parent item at (0,0) with size 1, and a child at (4, 0) also size 1, the outermost points would be (-1, 0) and (5, 0) therefore the outer circle would be at (2, 0) with radius 6.

My question is: what's the most efficient way for the program get this circle if it has several arbitrarily placed/sized circles to look at, most of which are probably irrelevant? So essentially how do I get the 2 or 3 outermost points and circumscribe them?

Also, this project is actually in a 3D world so really it would all be spheres... I just figure it'd be easier to start with circles and add a dimension once I understand the simpler version

Davis Diercks
  • 119
  • You must express in precise mathematical form "most of which are probably irrelevant". – David G. Stork Aug 06 '18 at 17:15
  • I just mean that I only need the circles with the outermost points on them, and the rest of the ones in the group will be fully inside the outer circle and could be removed without affecting the result – Davis Diercks Aug 06 '18 at 17:18
  • 1
    This question might be answered more quickly by posting it on Stack Overflow. It deals with software more than this venue. Good luck and, if you get an answer from Falkreon, it's probably a good answer. – poetasis Aug 06 '18 at 17:23
  • I considered that; at the time it seemed like more of a mathematical problem but you might be right. I'll try that, thanks – Davis Diercks Aug 06 '18 at 17:24
  • Of possible use: https://mathematica.stackexchange.com/questions/87676/random-non-overlapping-disks-in-a-square – David G. Stork Aug 06 '18 at 17:28
  • I just drew some arbitrary overlapping circles of various radii, and drew an enclosing axis-aligned rectangle: that would be easy to figure. Then I noticed two bounding parallel tangents at about $20 ^\circ $ but it would be hard to compute. Perhaps you can do a "binary search" of radius; but where to put the centre? If you start with a 1D example of (overlapping) line segments, to find an enclosing line, would that be an easier starting point? It might be trivial, but engages the brain. – Weather Vane Aug 06 '18 at 17:29
  • Thanks all, I looked at the similar thread and that might be what I was looking for... I'll look at the papers etc when I get some time. Might just do it iteratively since I don't think it'll have to do it every frame. – Davis Diercks Aug 06 '18 at 19:55

0 Answers0