I say a circle because that's what I think is easier to draw. but really I wouldn't mind some sort of deformed shape.
I started with averaging the x/ys of all points then taking the longest distance and make a circle from that. It worked sort of okay, but wasn't really right.
I was pointed to this by another programmer
nayuki.io/page/smallest-enclosing-circle (this one even give you the code)
but I wonder if there's an easier way to do it in Construct.
Here's what I have so far...
Unless I'm missing something its just average the xy's
And then pick the farthest from there.
Offset with the half the square if you want it inside.
Instead of the average you could find the median and use that for the center.
X = (xmax+xmin)/2
Y = (ymax+ymin)/2
Then just use the furthest point. Might give a tighter circle.
Oh, I'll have to try that.
Here's another method that tries to get the points like the other examples.
Seems there are some corner cases though.
Develop games in your browser. Powerful, performant & highly capable.
Just realized that circle perimeter is drawn by taking 3 points. 2 points has furthest distance from each other and the third point taking from middle position of previous 2 points toward furthest point from there. 3rd point only apply if itself outside of 2 most furthest point range.
thanks all this is super helpful! its pretty confusing to apply, but I think I'm getting it.
alextro what do you mean by "toward furthest point from there" and "outside of 2 most furthest"?
do you mean you get the center of the circle by figuring out the distance between 2 furthers points, getting the center of that line, and then do what?
Sort of trigonometri equation approach that involved tangent. I'll investigate to figure out. My current solution is not precise and not smooth (no trigonometri):
It should be possible to implement the welzl algorithm to do it. We just need to use some cleverness to return multiple values and be able to pass arrays to the function.
The meatiest part of the algorithm is probably the math to give the smallest circle around three points.
The algorithm came out cleaner in events than I expected.
okay, this is some crazy recursion. The function calls itself twice all while being called everytick! (but it obviously works!)
That was just what that algorithm did, which I honestly don’t fully understand. What I do know is it should be one of the faster algorithms for that problem, according to Wikipedia.
Finally, with visual approach "raycast' determine circle with 3 most outside points is possible: https://www.dropbox.com/s/2l1vyyyr94t3sti/Circle_3Points.capx?dl=0