11
Fabian
3y

aaAAaaAaaAaaAaAAAAAaAaaa floating points!

I debugged my algorithm for quite a while, wondering why it sometimes gives out "Circle(Point({1.7976931348623157E308,1.7976931348623157E308}),1.7976931348623157E308)" as the smallest circle around a group of points.
Figured out that it sometimes just never found any circle defined by two or three of the points which included all points (which is mathematically impossible).
Then finally I made it print out the points it thought were not inside the circle:
"1,7,8: Circle(Point({0.6636411126185259,0.535709780023259}),0.4985310690982777)
skip, 1 not inside"
So it defined the circle with 1 being on the edge, but then thought 1 was outside. Thank you, floating point Math.

For anyone wondering about the notation: That way I can directly copy/paste it into Geogebra to have a visualisation.

Comments
  • 0
    I think I fixed it with a 1e-10 buffer. The range of points is 0 to 1 on x and y. It's currently running thousands of tests and checking each time whether it finds a solution. Seems good so far.
  • 5
    Rule 1.000000000002 of programming, never use floats when possible.
  • 0
    @irene First I take every combination of two points and generate a circle with radius (distance/2) around their midpoint, then I take every combination of three points and generate a circle touching all three (using the long formulas at ambrsoft.com/trigocalc/circle3d.htm), then I take the smallest of those circles (2-combos and 3-combos) which has all other points in them. That should always give the minimum size circle that includes all points, which was the task.
    The check whether something is inside was what went wrong. And it's fixed now.
    I can probably also optimise quite a bit, it's not required to check every single 2-combo and 3-combo, but it's just for school, so getting it done fast is more important than performance.
    In theory I was also supposed to then take that circle as a step in a bigger algorithm, which seems to have a better runtime for large amounts of circles. But the time for the task is over anyway, I just finished the first part for fun.
  • 0
    @irene If I understood you correctly, here's a case that doesn't work: https://geogebra.org/classic/...
    Here a very detailed walkthrough, because this is getting complicated:

    Points A, B, C, D, E and F are the points to be included in the wanted circle.
    H is the barycenter/weighted center (weights 1, 1, 1, 1, 1, 1).
    B is furthest from it (5.35), then A (4.94), then E (4.76). Then follows C (4.34), F (1.43) and D (1.29).
    The longest distance of the three is AE (9.58), followed by AB (6.69) and BE (6.53).
    H is the midpoint of AE (covered in the image by the distance indicator for AE). A circle with radius AH (or EH) does not include point C.
    Therefore, on to step 3 of your instructions:
    h is the perpendicular bisector of AB, i of BE, the two remaining segments between the three points farthest from the barycenter.
    They cross in Point I (zoom in to see it).

    (stupid character limit)
  • 0
    (continuation)

    A circle with radius AI (or BI or EI) is the same as defining a circle by A+B+E in Geogebra, I just didn't know about that construction method before.
    But unfortunately, that circle also doesn't include point C.

    Your method seems to basically be a filter for my method, I brute-force every 2-combo and 3-combo, you select two. Sadly they aren't always the right ones, so I can't use that. I guess I could make it first try that and in the rare cases it fails, then brute-force it, but I'm still programming this for fun, so I won't do that.
    Or did I misunderstand your method? Did you mean something else?
  • 1
    Damn I like the idea of printing to Geogebra notation to have a quick look, gotta remember that trick
  • 1
    @ohemelaar In that case, have another trick: To enter more things at once, make it print a list into one line. Something like this:
    {Point({0,1}),Point({2,3}),Point({4,5})}
    The only downside is that you can't reference it by name from other formulas, but you can still click it in Geogebra, then you can even make it animate through all the elements.
Add Comment