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.

---

---

• Are you posting in the right place? Check out Where do I post X? to know for sure.
• Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:

  <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>

• Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
• Want more info? How to link or How to display code and escape characters are good places to start.