Beefy Boxes and Bandwidth Generously Provided by pair Networks
Your skill will accomplish
what the force of many cannot

Re: searching polygons not merged

by hippo (Chancellor)
on Oct 27, 2018 at 15:51 UTC ( #1224769=note: print w/replies, xml ) Need Help??

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 } }

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 (Cardinal) 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

      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. :-)

        > 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

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://1224769]
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others musing on the Monastery: (2)
As of 2020-09-26 15:15 GMT
Find Nodes?
    Voting Booth?
    If at first I donít succeed, I Ö

    Results (141 votes). Check out past polls.