Beefy Boxes and Bandwidth Generously Provided by pair Networks
Syntactic Confectionery Delight
 
PerlMonks  

Re: Millions of line segment intersection calcs: Looking for speed tips

by extremely (Priest)
on Aug 03, 2005 at 14:57 UTC ( #480502=note: print w/ replies, xml ) Need Help??


in reply to Millions of line segment intersection calcs: Looking for speed tips

You should be able to divide and conquer the data set. Rather than sorting the list by segment length, you should pick a dimension and sort on that.

Sort all the points by X and then Y. Create all the edges so that the higher X is first. Sort all the edges by X1, then X2. When processing a segment against the list, you can skip any segment where Xn1 is less than X2 or Xn2 is greater than X1. Better still, you can exit the loop early once Xn1 is less than X2 since all the rest of the segments are certain to not intersect.

The segment intersection calcs are expensive, adding a bail-out test for simple cases will go a long way by itself... but sorting the data to bail out of the entire list early should pay off handsomely as well.

--
$you = new YOU;
honk() if $you->love(perl)


Comment on Re: Millions of line segment intersection calcs: Looking for speed tips

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others avoiding work at the Monastery: (12)
As of 2014-10-30 12:40 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    For retirement, I am banking on:










    Results (207 votes), past polls