Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl-Sensitive Sunglasses
 
PerlMonks  

Re^5: searching polygons not merged

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


in reply to Re^4: searching polygons not merged
in thread searching polygons not merged

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

Indeed. Any particularly flat (in either Cartesian direction) ploygon is going to be better suited to a bounding box. Whether these are plentiful or rare in the data set is only something which the OP can answer.

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

I'd claim that not only is any regular polygon with n>4 better represented by a circle, the circle is trivially easy to compute. If the data set were all regular polygons (and I'm not assuming for one minute that they are in this case) then circles would be the obvious choice.

A little domain knowledge here would help to inform the choice of bounding box or circle. Horses for courses.

Replies are listed 'Best First'.
Re^6: searching polygons not merged
by haj (Deacon) on Oct 28, 2018 at 19:39 UTC
    ...the circle is trivially easy to compute.

    Quite on the contrary, I'd say that it is the bounding box which is trivially easy to compute, whereas the circle is rather straightforward but still needs quite a couple of floating point operations. Both are linear with the number of points, but you just need to write down the subs for both algorithms for a triangle and you'll easily spot the difference.

    Regarding performance, I guess that floating point operations are slow compared to if/then/else branching.

      Given a vertex and centre of a regular polygon you have all you need for the circle. Can you explain how it isn't trivial?

        Indeed, this case is trivial. For that you need to know in advance that the polygons are regular - I was still stuck with a general list of polygons, some of which might turn out to be better represented by a circle because they're regular.

Re^6: searching polygons not merged
by LanX (Cardinal) on Oct 28, 2018 at 17:56 UTC
    I'd claim any advantage of a circle could be countered by a set of disjoint covering boxes, and the computational cost would be similar.

    Quadtree decomposition is only one way to do it.

    And decomposing in smaller circles wouldn't lead to a disjoint set.

    (Though the "best" approach is probably partitioning a polygon into triangles anyway )

    The inherent catch is that we prefer a cartesian system, hence we'll always prefer a compatible coverage if the costs are similar.

    Remember that the OP wanted to preselect (spatial index) plausible candidates, how would you do this with circles?

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

      The inherent catch is that we prefer a cartesian system, hence we'll always prefer a compatible coverage if the costs are similar.

      I don't disagree. My point is that without knowing anything qualitative about the data set it's going to be difficult to determine if the costs are similar.

      Remember that the OP wanted to preselect (spatial index) plausible candidates, how would you do this with circles?

      Not sure what you mean here. The exclusion by circles should be as simple as this:

      #!/usr/bin/env perl use strict; use warnings; my @circles = ( { x => 3.0, y => 10.0, r => 5.0 }, { x => 4.0, y => 9.0, r => 2.0 }, { x => 12.0, y => 4.0, r => 4.0 }, ); while (my $one = shift @circles) { for my $other (@circles) { my $dx2 = ($one->{x} - $other->{x}) ** 2; my $dy2 = ($one->{y} - $other->{y}) ** 2; my $r2 = ($one->{r} + $other->{r}) ** 2; if ($dx2 + $dy2 < $r2) { warn "Potential overlap: $one->{x}, $one->{y}, $one->{r} w +ith $other->{x}, $other->{y}, $other->{r}\n"; } } }
        > Not sure what you mean here.

        you are suggesting > n**2/2 comparisons, ie 50m for 10k polygons ... that's - sorry - insane.

        Preordering can eliminate most of the fruitless ones.

        See my first reply.

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

Re^6: searching polygons not merged
by LanX (Cardinal) on Oct 28, 2018 at 18:33 UTC
    > . Any particularly flat (in either Cartesian direction) ploygon

    Does "flat" already cover a crescent or other concave bodies? ;)

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

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others avoiding work at the Monastery: (7)
As of 2020-09-29 14:37 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    If at first I donít succeed, I Ö










    Results (146 votes). Check out past polls.

    Notices?