Re: [ProgSoc] join the dots?

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

On Wed, 3 May 2000, Telford Tendys wrote:

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

So you're saying ... you had a brainwave about it?

> 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

It probably will.  I mean it really can, which is what I intended it to
do.

Thing is, I went back to the person whom I'm thinking about this for, and
it turns out that according to "what's normal", you wouldn't want this
really obtuse triangle after all.

Which sh*tted me off.  And then I pointed out, that if you don't demand
the creation of a convex polygon around the outside ... well, you no
longer have a threshold to work by.  I mean, what constitutes a "nasty
long thin triangle" anyway?!!  I could end up having the polygon around
the outside having a nasty great bite taken out of it, and leave it on the
basis that "oh it's just a long thin triangle, but maybe not so long and
not so thin as you thought".

So I'm sticking by this definition.  Gotta have convex.  If you can think
of a quicker way to determine the individul vertices I'd be gratified  :)

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

I have yet to implement the y = mx + b thing though  :)

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

Probably not.  Ideally I would ask for greatest total perimeter actually
... just thinking about it, I can't say "smallest total area" because it
should always total the same, right?  :)   So the greatest number of
triangles for the given area, yes?  Well no, I mean you could have the
same number of triangles and still more than one solution.  So, maximise
the perimeter.

(I have a feeling that minimising the perimeter for each triangle may lead
me towards that goal anyway).

But, but, but ... I'm having a hard enough time finding an algorithm that
=guarantees= a correct solution without having two algorithms to choose
from.  Not yet, anyway.

> the class of ``greedy algorithms'' where each step attepmts to do
> the best it can without having any consideration for future steps

Hmmmm.  All I can say is, do you have any suggestions as to what it should
be doing instead?

> so it can get distracted by something which looks like a good step
> to make but which stuffs up other steps.

Well I did trial it extensively on the back of a McDonald's traymat so I
think the "other steps" aren't actually stuffing up, after all.

> 
> You also need to ensure that step 6 does not attempt to create
> overlapping triangles so you still need a test for overlap.

I =think= that it cannot.  I haven't found a set of points yet that will
cause this.  This is because Step 6 will not create a triangle that
already exists ... and some intrinsic nature of the location of the
search, from what I can tell.  I may be wrong.  But I haven't disproved my
own theory yet.  Going around the outside first seemed to make the
difference.

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

This would be cool if I break my latest theory.

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

<nods>

> 
> I'm still curious what you want this for?

It's for one of the people that came with us to Chinese after SLUG the
other night ... once I have the triangles, you can calculate the volume
underneath the whole thing (each point has a "reduced level" height).  
The assignment is programming but the subject certainly isn't.  The tutor
(and lecturer) don't even know how to automate the triangle-discovery
process ... and if they tell them after the assignment that "Oh we just
expected you to do that part by hand and type in the data because that
kind of thing is impossible" then I'll spew because it really should be
possible!  Well, that's what I said last week anyway.  Me and my big
mouth.  FWIW, the subject itself is called "Automated Systems" something
or other.


Kewl, I just received some emailcash  :)

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