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

Hi BrowserUK,

I need to thank you again for bringing me on the right path. I implemented the algorithm as follows: First find the convex hull of all tiles. Then, depending of the quadrant, take one of the four points of a given tile as "outermost point" => Should be a small number.

With these outermost points, I calculate the minimum circle by doing it with brute force i.e., take all pairs and triple of points.

The algorithm is fast enough for all practical examples, I checked. One example: example

Again: Thanks alot and best regards
Jan

Replies are listed 'Best First'.
Re^9: Placeing Tiles in a Circle
by BrowserUk (Patriarch) on Dec 09, 2013 at 15:42 UTC
    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.
[reply]
      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