Beefy Boxes and Bandwidth Generously Provided by pair Networks
Just another Perl shrine
 
PerlMonks  

Re: searching polygons not merged

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


in reply to searching polygons not merged

You should describe the format of your polygon data, to avoid us guessing.

In general many efficient so called "clipping" algorithms depend on calculating "bounding boxes".

This - the smallest surrounding rectangular - allows eliminating many impossible candidates.

The rules are:

  • Bounding boxes don't intersect => Polygons don't intersect
  • Bounding boxes can only intersect if both x and y intervals intersect.
  • Two intervals a (= [a0,a1] ) and b only intersect iff a0 <= b1 and b0 <= a1

Thus storing the bounding-boxes in an ordered structure° helps efficiently eliminating impossible combinations.

But I suppose you are better off using an already available graphic lib.

HTH! :)

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

update

°) see also Spatial_index#Spatial_index and for instance Quadtree

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others scrutinizing the Monastery: (2)
As of 2020-08-12 04:04 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    Which rocket would you take to Mars?










    Results (64 votes). Check out past polls.

    Notices?