Re: Res: Res: Polygon from point cloud and other from triangle list?

> Perhaps something reasonable could be had by calculating the Delaunay triangulation (which will give you the convex hull), and then removing triangles from the boundary iteratively until you can remove no more triangle without breaking whatever connectedness/area rule you want to enforce.

I haven't come across alpha shapes before, but from the previous links this sounds like it's exactly an alpha shape? All alpha shapes are a subset of the delaunay triangulation of the point set. The alpha value just defines the particular subset. 

Or am I missing something?

Ta,
Sam

From: Jon Watte [mailto:[email protected]] 
Sent: 25 June 2009 01:54
To: Game Development Algorithms
Subject: Re: [Algorithms] Res: Res: Polygon from point cloud and other from triangle list?

An alpha shape is not guaranteed to be a closed non-overlapping polygon, though, which I think that the original requester needs. Specifically, an alpha shape may create thin "bridges" of areas where two vertices are connected "both ways" and thus generate an infinitely thin connection.

Non-convex hulls are a better fit, if you don't need to punch holes into your polygon (e g if there are no "lakes" in the middle that you want open/not covered).

Perhaps something reasonable could be had by calculating the Delaunay triangulation (which will give you the convex hull), and then removing triangles from the boundary iteratively until you can remove no more triangle without breaking whatever connectedness/area rule you want to enforce. To make it well defined, you probably want to remove the largest removable triangle from each pass of border triangle removal..

Sincerely,

jw


metanet software wrote: 
hi,
you might also want to check out alpha shapes and non-convex hulls: 

http://www.spatialanalysisonline.com/output/html/Non-convexhulls.html
http://www.cs.wustl.edu/~pless/546/lectures/lecture22.pdf
http://cgm.cs.mcgill.ca/~godfried/teaching/projects97/belair/alpha.html

raigan


--- On Wed, 6/24/09, Jose Marin <[email protected]> wrote:

  
From: Jose Marin <[email protected]>
Subject: [Algorithms] Res: Res: Polygon from point cloud and other from triangle list?
To: "Game Development Algorithms" <[email protected]>
Received: Wednesday, June 24, 2009, 3:03 PM

Thanks for the ideas, Jon!

If I find a good algorithm, I'll post it here, if someone
is interested.

Regards

Jose



----- Mensagem original ----
De: Jon Watte <[email protected]>
Para: Game Development Algorithms <[email protected]>
Enviadas: Quarta-feira, 24 de Junho de 2009 15:31:56
Assunto: Re: [Algorithms] Res: Polygon from point cloud and
other from triangle list?

Jose Marin wrote:
    
I need to find the outline polygon (may be non-convex,
      
and will be on most of the times) defined by the resulting
shape.
    
  
      
The problem is that "the outline polygon" is not well
defined, if you 
allow it to be non-convex.
If you can define what it means to be "the outline
polygon," that would 
get you closer to an algorithm.
Write down a number of cases on paper. Draw what you think
should be the 
resulting polygon. Try to figure out what rule you,
yourself, use to 
create that polygon.

For example, you can start with the polygon that consists
of all the 
shapes -- this is a polygon; it's just disjoint. Now, you
probably want 
it to be connected. That's one requirement right there. How
would you go 
about connecting those shapes? The answer to that question
is not well 
defined, either, but it's a start.

Sincerely,

jw


-- 

  Revenge is the most pointless and damaging of human
desires.


------------------------------------------------------------------------------
_______________________________________________
GDAlgorithms-list mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list



      Veja quais são os assuntos do momento
no Yahoo! +Buscados
http://br.maisbuscados.yahoo.com

------------------------------------------------------------------------------
_______________________________________________
GDAlgorithms-list mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list

    


      __________________________________________________________________
The new Internet Explorer® 8 - Faster, safer, easier.  Optimized for Yahoo!  Get it Now for Free! at http://downloads.yahoo.com/ca/internetexplorer/

------------------------------------------------------------------------------
_______________________________________________
GDAlgorithms-list mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list

  

-- 
  Revenge is the most pointless and damaging of human desires.

------------------------------------------------------------------------------
_______________________________________________
GDAlgorithms-list mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list