[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [ProgSoc] join the dots?

I don't quite understand why you want this but it is something I was
working on for a while then finally gave up on then later realised
that what I really wanted to solve was some other problem which turned
out to be a lot easier.


On Tue, May 02, 2000 at 05:57:13PM +1000, Christian Kent wrote:
> 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.

I see a gap between [2] and [3], how do you know that the external
line won't give you a nasty long, thin triangle? Or is that what you
want? I guess that these will only form on the edges so you can make
it an option to delete them at the end if they are not wanted.

> 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).

This is drawing a convex polygon around the whole set, that
seems easy enough to achieve.

> 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.

This should produce some sort of set of triangles but there is no
particular reason why it would choose the best (presuming that
smallest total perimeter is the target). Your algorithm is of
the class of ``greedy algorithms'' where each step attepmts to do
the best it can without having any consideration for future steps
so it can get distracted by something which looks like a good step
to make but which stuffs up other steps.

You also need to ensure that step 6 does not attempt to create
overlapping triangles so you still need a test for overlap.
I somewhere have a test for a pair of triangles that share an
edge to see if they overlap or not but I think you need more than
that -- you need a test for points to see if the point is ``used up''
by triangles and cannot be used any more.

> 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.

Yup, I agree that you need to get the outer stuff settled before
working on the inner.

I'm still curious what you want this for?

	- Tel
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/>