Well, I suppose that in the rare circumstance a point falls on an corner, it would be trivial to determine the other triangles involved (assuming this were needed, and whatever the precision criterion).

Also, (while in a continuous mesh of triangles only a small number would need detailed testing) if the overall process needed to be done a large number of times, any saving in time would be valuable.


Gaz


-----Original Message-----
From: Van Snyder [mailto:[log in to unmask]]
Sent: Friday, 16 May 2003 12:43 PM
To: [log in to unmask]
Subject: Re: Slightly OT: Delaunay triangulation


> Just a couple of thoughts:
> 
> If we are talking about a continuous mesh of triangles ('a la' finite element analysis), can there not be more than three triangles contiguous at an apex point?  (This is not mere pedantry about the number of pointers.)  


Sure, but the point is that there can only be one triangle adjacent to
another one across an edge.  I wrote "... across the failing edge," which
I thought was enough of a clue that the data structure has three pointers
for each triangle, to triangles adjacent *ACROSS ITS EDGES*.  I should
have described the data structure more fully in the original note.

As I also pointed out, starting with some triangle having coordinates that
enclose the point is a good way to start.  It's easy to construct grids in
which the hash gives several triangles.  What's needed next is a rational
way to proceed from one triangle in the initially-selected set to another one.


> Surely the easiest robust hash (as alluded to by both other writers), is to select a set of triangles based on which have the point in question falling between each triangle's maximum and minimum coordinates in each dimension.  Then a shortened version of the 'standard'(?) 2D polygon test can be applied to each triangle (triangles don't have re-entrant angles).
> 
> And 'each triangle' because we either need to determine all triangles in which the point falls, or the preferred triangle. Because a triangle has an odd number of sides, it is not immediately obvious what the major benefits would be in any algorithm that tries to take advantage of the grid matrix (data storage) structure - a 2d structure.
> 
> Is it an issue what precision needs to be applied to the 'comparison of reals' tests that form part of these algorithms? Is it a question of relating this back to the reality that is being modelled?
> 
> 
> 
> Kind regards
> 
> Gaz
> 
> 
> -----Original Message-----
> From: Van Snyder [mailto:[log in to unmask]]
> Sent: Friday, 16 May 2003 10:31 AM
> To: [log in to unmask]
> Subject: Re: Slightly OT: Delaunay triangulation
> 
> 
> Loren P Meissner <[log in to unmask]> wrote:
> 
> > I always thought it is MUCH harder to find out WHICH triangle a point is
> > in. If you have a quick algorithm for "is P in [abc]" you still have to
> > do a search among all the [abc] triangles.
> > 
> > Of course you can narrow down the search by sorting the coordinates of
> > the mesh points and only testing ones that "span" the point in question.
> 
> That's a good start.  If you also have your triangles in a data structure
> such that each triangle has three pointers to adjacent triangles, when
> your "not in this triangle" test fails, you go across the failing edge
> to the next triangle, and so on.  This avoids testing many triangles.
> 
> -- 
> Van Snyder                    |  What fraction of Americans believe 
> [log in to unmask]       |  Wrestling is real and NASA is fake?
> Any alleged opinions are my own and have not been approved or disapproved
> by JPL, CalTech, NASA, Sean O'Keefe, George Bush, the Pope, or anybody else.
> 
> > -----Original Message-----
> > From: Fortran 90 List [mailto:[log in to unmask]] On Behalf
> > Of Alvaro Fernandez
> > Sent: Thursday, May 15, 2003 6:04 AM
> > To: [log in to unmask]
> > Subject: Re: Slightly OT: Delaunay triangulation
> > 
> > Yes, a way to know if a point is inside a triangle. Once that happens, I
> > know which triangle to evaluate.
> >  
> > Alvaro
> 
> 
> ************************************************************************
> The information in this e-mail together with any attachments is
> intended only for the person or entity to which it is addressed
> and may contain confidential and/or privileged material.
> 
> Any form of review, disclosure, modification, distribution
> and/or publication of this e-mail message is prohibited.  
> 
> If you have received this message in error, you are asked to
> inform the sender as quickly as possible and delete this message
> and any copies of this message from your computer and/or your
> computer system network.  
> ************************************************************************


************************************************************************
The information in this e-mail together with any attachments is
intended only for the person or entity to which it is addressed
and may contain confidential and/or privileged material.

Any form of review, disclosure, modification, distribution
and/or publication of this e-mail message is prohibited.  

If you have received this message in error, you are asked to
inform the sender as quickly as possible and delete this message
and any copies of this message from your computer and/or your
computer system network.  
************************************************************************