in reply to Re^8: Placeing Tiles in a Circle
in thread Placeing Tiles in a Circle

First find the convex hull of all tiles. Then, ... I calculate the minimum circle by doing it with brute force...The algorithm is fast enough for all practical examples, I checked.

Indeed. As all your points live on a regular grid and large numbers of them will be 'inside'; and of the outermost, many will be eliminated by being co-linear, the convex hull should always reduce to a manageable number for brute force.

For quite a while I thought that -- for the specific case of your regular grid -- the convex hull algorithm could be avoided by finding the 3 points 'by inspection'. Indeed, if your tiles were square, it is, but for the generality of rectangular tiles, I couldn't find a reliable way.

I have to say, it offends me intellectually to know that there are several O(n) algorithms (for the {smallest/minimum/bounding} {enclosing/encircling/} {circle/disk/ball/sphere} problem) out there, and yet I found it impossible to find either a clear description; or a correct and usable implementation :(

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.

Replies are listed 'Best First'.
Re^10: Placeing Tiles in a Circle
by janDD (Acolyte) on Dec 12, 2013 at 16:47 UTC
    Hi

    So do you see any conceptual problems porting the java code from the miniball project to perl? I quickly went over it and, to be honest, I haven't understand it. But I guess, with some time, it should be possible to rewrite it (and learn how its done along the path ...)

    Best regards Jan
[reply]
      do you see any conceptual problems porting the java code from the miniball project to perl?

      There shouldn't be, but ... without a clear understanding of the algorithm, good luck trying to debug the beast.

      And then there is the problem of performance. If you go for a brute-force conversion retaining the same matryoshka doll construction of nested classes -- and you'd probably have to -- the performance would be abysmal written in Perl.

      You'd almost certainly be better off using the C++ version to build a shared library and then write an XS/C wrapper to the primary entry point(s).

      You could -- theoretically -- wrap over the full API into a Perl class, but then you'd have the problem of C++ name mangling.

      With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
      Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
      "Science is about questioning the status quo. Questioning authority".
      In the absence of evidence, opinion is indistinguishable from prejudice.
[reply]

In Section Seekers of Perl Wisdom