Re: [ProgSoc] join the dots?

[Christian Kent <whophd@nospam.progsoc.uts.edu.au>]

Okay I think I have a water-tight solution:

1.  Find an external point (northmost will do).  Remember it.

2.  Draw an external line (defined:  all other points lie on one side).
    Use y=mx+b formula.

3.  This forms the base of one triangle.
    Get the closest other point to form a third side.
    Closest = smallest possible perimeter.
    Put this triangle in a list.

4.  The other point on your base is by definition also external.
    Take your new external point and repeat step 2,
    until you get back to where you started.
    (The triangles you form so far may or may not be sharing their sides).

5.  Phase II -- each non-external line needs to form part of TWO TRIANGLES
    so find an internal line which belongs to only one triangle.

6.  For each one, find the closest point which would form a triangle that
    is not already in your triangle list.

7.  Repeat;  you may have to restart Phase II repeatedly because you
    create new uncoupled-internal sides as you go.

8.  You are completed when all internal sides are coupled.

Voila, triangles are stored in memory.


Andrew Thoms and I had a working theory that worked recursively like a
B-tree (for each triangle that you created which contained an internal
line).  It was great, but I tried it on a Southern Cross configuration
(with a centre dot) and this caused an overlap triangle to occur across
the top of the cross -- the opposite side of the cross was closer than the
bottom of the cross.  It failed because it did not seek out
externally-positioned triangles first.


I seek professional criticism  :)

CK.

--
You are subscribed to the progsoc mailing list. To unsubscribe, send a
message containing "unsubscribe" to progsoc-request@nospam.progsoc.uts.edu.au.
If you are having trouble, ask owner-progsoc@nospam.progsoc.uts.edu.au for help.

This list is archived at <http://www.progsoc.uts.edu.au/lists/progsoc/>