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

Re: [ProgSoc] join the dots?



Hows this:

1. start with array of points (x,y)
2. also have an array of lines (x1,y1, x2,y2)
3. for each point, create a line to the closest other point, so long as it
has not already been created, and does not cross over another line.
4. do 3. until no more lines are created.
5. draw all your lines and you will have optimal triangles.

On Mon, 1 May 2000, Christian Kent wrote:

> 
> Is it possible to systematically take a series of random x,y coords and
> find all the triangles that you form by joining the dots?  Typical stupid
> problem that is piss-easy for a human ...
> 
> I keep running into the problem that "discovering" the vertices will lead
> to overlapping triangles:
> 
> (a) fill an array of proximal points by finding heaps of hypotenuses and
> sorting them by distance.  Trouble is that once you find the 3 closest
> points per point, you've already got lines crossing over "ideal" triangles
> and yet not all the other triangles have their sides defined.
> 
> (b) fill an array of all possible vertices, thus define every triangle,
> then by a system of elimination determine the "ideal" triangles.  But how?  
> If I keep an eye on whether every point is still represented after each
> triangle is eliminated, I can still end up with an "open" area where you'd
> normally expect an obtuse triangle around the outside.
> 
> 
> Any ideas??
> 
> 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/>
> 

-- 
___________________________________________________________________________
	         Tim Johnson is : timj@nospam.progsoc.uts.edu.au
		   http://www.progsoc.uts.edu.au/~timj

          Drawing on my fine command of language, I said nothing.

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