in reply to searching polygons not merged

but that example performance is really bad

This will run in less than half the time:

while (my $polygon1 = shift @polygon) {
    foreach my $polygons2(@polygon){
        # Comparison code here
    }
}

[download]

Additionally, I'd probably create an array of the smallest circles which enclose all the vertices of each polygon before starting the main loop. If the two circles don't overlap (an easy calc) then the two polygons won't either. That will reduce the number of more expensive calcs required.

Replies are listed 'Best First'.
Re^2: searching polygons not merged
by LanX (Saint) on Oct 27, 2018 at 15:59 UTC
    Good points.

    But I'm not sure if the minimum circle is more efficient than a minimum bounding box.

    (I bet it's not)

    Cheers Rolf
    (addicted to the Perl Programming Language :)
    Wikisyntax for the Monastery FootballPerl is like chess, only without the dice

[reply]

      The minimum circle is more expensive to compute (for an irregular polygon) but that's O(n). Since the circle is smaller it will be no worse and maybe a good bit better for weeding out non-overlaps and the bonus that brings will depend entirely on the dataset being examined. Without seeing sample data, would you take the O(n) hit for an O(n2) gain? I probably would.

      (I bet it's not)

      It's a gamble either way. :-)

[reply]
        > Since the circle is smaller 

        This is generally not true.

        A pointy triangle could be idealized as an edge, the resulting circle will always be bigger than a bounding box.

        (The corners of the box are on the circle, see Thales's theorem)

        You might now claim that something like a regular octagon is better represented by a circle (probably).

        But how does the average polygon look like?

        I bet it depends on the randomization

        • random vertices
        • random edges
        • random angles
        will produce totally different samples

        Furthermore it'll be more difficult to fit circles into a quadtree search.

        I think using circles in a Cartesian system causes too many headaches.

        Cheers Rolf
        (addicted to the Perl Programming Language :)
        Wikisyntax for the Monastery FootballPerl is like chess, only without the dice

[reply]

In Section Seekers of Perl Wisdom