Beefy Boxes and Bandwidth Generously Provided by pair Networks
"be consistent"
 
PerlMonks  

Re^2: searching polygons not merged

by LanX (Cardinal)
on Oct 27, 2018 at 15:59 UTC ( #1224770=note: print w/replies, xml ) Need Help??


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

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

Replies are listed 'Best First'.
Re^3: searching polygons not merged
by hippo (Chancellor) on Oct 28, 2018 at 10:05 UTC

    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

        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.

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others cooling their heels in the Monastery: (4)
As of 2020-09-26 16:32 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    If at first I donít succeed, I Ö










    Results (141 votes). Check out past polls.

    Notices?