The set of all possible connecting lines between two co-ordinates in such a set (irrespective of whether they are edges or not) has a cardinality of nC2. CPAN has a module for calculating all these combinations Math::Combinatorics which means that a set of 301 co-ordinates can produce an initial set of 45150 'candidate edges'.

The bad news then is that there are millions of combinations of these connecting lines to test to see if they intersect.

I can envisage a shortcut where at each iteration through these combinations, not only the candidate edges, but all their connection-test combinations are eliminated if an intersection occurs, leaving a rapidly diminishing set to test.

The trick to that would be to set up a (bi-directionally) linked (by reference) list through both hashes (after using a hash for the candidate edges instead of an array) and walk down it doing your geometry test and if connection found, breaking deleting and relinking as you go. The reason for that is that a for loop cannot eliminate the queue ahead of itself, but a walk down a linked list can.

One world, one people

In reply to Re: Millions of line segment intersection calcs: Looking for speed tips by anonymized user 468275
in thread Millions of line segment intersection calcs: Looking for speed tips by drewhead

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.