gdalgorithms-list

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

[Jon W. <jw...@gm...>]

Ah, you want to "fill in" any "lakes" created!

Alpha shapes, and polygon union, are not the right solutions for that.

If they are not overlapping, then they need to be touching to create a 
"seal." I assume that you use snapping or something to make this well 
behaved. If you allow connection edge-to-edge and vertex-to-edge, rather 
than just vertex-to-vertex, then first you need to tesselate the 
touching polygons by subdividing edges where they touch the other vertices.
Once you have done that, create the triangle mesh that is the union of 
the existing polygons. At this point, you can identify which groups of 
triangles make their own "islands."
At this point, all you need to do is the "cap holes" algorithm on the 
resulting islands (I'm sure you're familiar with it from various 3D 
tools). This basically means identifying open edge loops that are not 
the "outside" loop, and tesselating that loop as a convex polygon to 
generate triangles. The only problem is figuring out which loop is 
"outside" and which is "inside."
If there is only one loop, then that's "outside." If there is more than 
one loop, then you can test for triangle overlap; the "outside" loop, 
tesselated, will encompass all "inside" loops.
There is still one problem: When you join two polygons vertex-to-vertex, 
the loop/edge following needs to not "cross over" to create two 
overlapping loops. There are various options; for example, if you start 
on an edge that you know is "outside," then you always take the outgoing 
edge in such an X intersection that curves the most outwards, which ends 
up being a maximum value (or minimum value) test of a cross product 
(testing just the sign is not good enough).

Something like that?

Sincerely,

jw



Jose Marin wrote:
> Think on a Tangram game.
> The pieces aren't overlapping.
> They are all convex, but the resulting image can be non-convex.
> I need to determinate the union of the shapes, creating a polygon of the resulting image.
>
> For example, if the pieces are forming a rectangle, the resulting polygon has four line segments, the outline of that rectangle.
>
> If the pieces are forming a rabbit, I need to determinate the polygon (or polygons) of the outline of the rabbit.
>
>   


-- 

  Revenge is the most pointless and damaging of human desires.

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

[Peter L. <pe...@to...>]

that sounds like you only need to remove internal edges.  You're 
learning that specifying a problem clearly is sometimes harder than 
coming up with the solution!
   It sounds to me like you have a set of polygons (specified by 
vertices only?) and you need to find out which ones share edges, and 
remove the unnecessary edges. If you really are mimicking the Tangram 
game, there's no requirement that vertices adjoin.  So you need to focus 
on the edges - identify the ones that are collinear and combine the 
polygons that share them, removing edges and possibly creating new vertices.
  So first identify the data structure that makes this task easiest. If 
I've identified the problem correctly, you need a structure with edges, 
not just vertices. So convert your data to that. Then you need an 
algorithm to search through the edges and find out which ones are 
candidates for removal.  If this is for a class assignment or some other 
non-realtime project, you probably don't need to worry about extremely 
efficient data structures or optimized algorithms (which is what gets 
the readers of this list excited :)

Jose Marin wrote:
> Think on a Tangram game.
> The pieces aren't overlapping.
> They are all convex, but the resulting image can be non-convex.
> I need to determinate the union of the shapes, creating a polygon of the resulting image.
>
> For example, if the pieces are forming a rectangle, the resulting polygon has four line segments, the outline of that rectangle.
>
> If the pieces are forming a rabbit, I need to determinate the polygon (or polygons) of the outline of the rabbit.
>
>
>
> ----- Mensagem original ----
> De: Jon Watte <jw...@gm...>
> Para: Game Development Algorithms <gda...@li...>
> Enviadas: Quinta-feira, 25 de Junho de 2009 17:26:39
> Assunto: Re: [Algorithms] Res: Res: Polygon from point cloud and other from triangle list?
>
> Jose Marin wrote:
>   
>> Yes, polygon union!
>>
>> I should have done more research before posting, so the description of the problem would be more clear.
>>
>> I have found some libraries that do that, but all that I need is a simple algorithm to compute the union, not a full feature geometry library.
>>
>>  
>>     
>
> Are your polygons already overlapping, and all you need to do is ensure 
> no self-overlap in the output? Or do you not need the final union to be 
> fully connected using non-degenerate faces?
>
> Sincerely,
>
> jw
>
>
>
>
>
>   

[Algorithms] Res: Res: Res: Polygon from point cloud and other from triangle list?

[Jose M. <jos...@ya...>]

Think on a Tangram game.
The pieces aren't overlapping.
They are all convex, but the resulting image can be non-convex.
I need to determinate the union of the shapes, creating a polygon of the resulting image.

For example, if the pieces are forming a rectangle, the resulting polygon has four line segments, the outline of that rectangle.

If the pieces are forming a rabbit, I need to determinate the polygon (or polygons) of the outline of the rabbit.



----- Mensagem original ----
De: Jon Watte <jw...@gm...>
Para: Game Development Algorithms <gda...@li...>
Enviadas: Quinta-feira, 25 de Junho de 2009 17:26:39
Assunto: Re: [Algorithms] Res: Res: Polygon from point cloud and other from triangle list?

Jose Marin wrote:
> Yes, polygon union!
>
> I should have done more research before posting, so the description of the problem would be more clear.
>
> I have found some libraries that do that, but all that I need is a simple algorithm to compute the union, not a full feature geometry library.
>
>  

Are your polygons already overlapping, and all you need to do is ensure 
no self-overlap in the output? Or do you not need the final union to be 
fully connected using non-degenerate faces?

Sincerely,

jw





-- 

  Revenge is the most pointless and damaging of human desires.


------------------------------------------------------------------------------
_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
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

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

[Sam M. <sam...@ge...>]

> 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:jw...@gm...] 
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 <jos...@ya...> wrote:

  
From: Jose Marin <jos...@ya...>
Subject: [Algorithms] Res: Res: Polygon from point cloud and other from triangle list?
To: "Game Development Algorithms" <gda...@li...>
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 <jw...@gm...>
Para: Game Development Algorithms <gda...@li...>
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
GDA...@li...
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
GDA...@li...
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
GDA...@li...
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.

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

[Jon W. <jw...@gm...>]

Jose Marin wrote:
> Yes, polygon union!
>
> I should have done more research before posting, so the description of the problem would be more clear.
>
> I have found some libraries that do that, but all that I need is a simple algorithm to compute the union, not a full feature geometry library.
>
>   

Are your polygons already overlapping, and all you need to do is ensure 
no self-overlap in the output? Or do you not need the final union to be 
fully connected using non-degenerate faces?

Sincerely,

jw





-- 

  Revenge is the most pointless and damaging of human desires.

[Algorithms] Res: Res: Polygon from point cloud and other from triangle list?

[Jose M. <jos...@ya...>]

Yes, polygon union!

I should have done more research before posting, so the description of the problem would be more clear.

I have found some libraries that do that, but all that I need is a simple algorithm to compute the union, not a full feature geometry library.

Thanks



----- Mensagem original ----
De: Richard Fabian <ra...@gm...>
Para: Game Development Algorithms <gda...@li...>
Enviadas: Quinta-feira, 25 de Junho de 2009 6:28:18
Assunto: Re: [Algorithms] Res: Polygon from point cloud and other from triangle list?

this is a completely different problem, this is just a polygon union
function isn't it?

2009/6/24 Jose Marin <jos...@ya...>:
>
> Hmm, really, its a very generic question, I should be more detailed.
>
> I have some shapes, grouped together, and would like to create a polygon that represents the resulting shape.
>
> Something like a tangram shape, that is formed by smaller shapes.
>
> I need to find the outline polygon (may be non-convex, and will be on most of the times) defined by the resulting shape.
>

-- 
fabs();
Just because the world is full of people that think just like you,
doesn't mean the other ones can't be right.

------------------------------------------------------------------------------
_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
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

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

[Richard F. <ra...@gm...>]

this is a completely different problem, this is just a polygon union
function isn't it?

2009/6/24 Jose Marin <jos...@ya...>:
>
> Hmm, really, its a very generic question, I should be more detailed.
>
> I have some shapes, grouped together, and would like to create a polygon that represents the resulting shape.
>
> Something like a tangram shape, that is formed by smaller shapes.
>
> I need to find the outline polygon (may be non-convex, and will be on most of the times) defined by the resulting shape.
>

-- 
fabs();
Just because the world is full of people that think just like you,
doesn't mean the other ones can't be right.

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

[Jon W. <jw...@gm...>]

<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
  <meta content="text/html;charset=ISO-8859-1" http-equiv="Content-Type">
</head>
<body bgcolor="#ffffff" text="#000000">
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.<br>
<br>
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).<br>
<br>
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..<br>
<br>
Sincerely,<br>
<br>
jw<br>
<br>
<br>
metanet software wrote:
<blockquote cite="mid:837...@we..."
 type="cite">
  <pre wrap="">hi,
you might also want to check out alpha shapes and non-convex hulls: 

<a class="moz-txt-link-freetext" href="http://www.spatialanalysisonline.com/output/html/Non-convexhulls.html">http://www.spatialanalysisonline.com/output/html/Non-convexhulls.html</a>
<a class="moz-txt-link-freetext" href="http://www.cs.wustl.edu/~pless/546/lectures/lecture22.pdf">http://www.cs.wustl.edu/~pless/546/lectures/lecture22.pdf</a>
<a class="moz-txt-link-freetext" href="http://cgm.cs.mcgill.ca/~godfried/teaching/projects97/belair/alpha.html">http://cgm.cs.mcgill.ca/~godfried/teaching/projects97/belair/alpha.html</a>

raigan


--- On Wed, 6/24/09, Jose Marin <a class="moz-txt-link-rfc2396E" href="mailto:jos...@ya...">&lt;jos...@ya...&gt;</a> wrote:

  </pre>
  <blockquote type="cite">
    <pre wrap="">From: Jose Marin <a class="moz-txt-link-rfc2396E" href="mailto:jos...@ya...">&lt;jos...@ya...&gt;</a>
Subject: [Algorithms] Res: Res: Polygon from point cloud and other from triangle list?
To: "Game Development Algorithms" <a class="moz-txt-link-rfc2396E" href="mailto:gda...@li...">&lt;gda...@li...&gt;</a>
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 <a class="moz-txt-link-rfc2396E" href="mailto:jw...@gm...">&lt;jw...@gm...&gt;</a>
Para: Game Development Algorithms <a class="moz-txt-link-rfc2396E" href="mailto:gda...@li...">&lt;gda...@li...&gt;</a>
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:
    </pre>
    <blockquote type="cite">
      <pre wrap="">I need to find the outline polygon (may be non-convex,
      </pre>
    </blockquote>
    <pre wrap="">and will be on most of the times) defined by the resulting
shape.
    </pre>
    <blockquote type="cite">
      <pre wrap="">&nbsp; 
      </pre>
    </blockquote>
    <pre wrap="">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


-- 

&nbsp; Revenge is the most pointless and damaging of human
desires.


------------------------------------------------------------------------------
_______________________________________________
GDAlgorithms-list mailing list
<a class="moz-txt-link-abbreviated" href="mailto:GDA...@li...">GDA...@li...</a>
<a class="moz-txt-link-freetext" href="https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list">https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list</a>
Archives:
<a class="moz-txt-link-freetext" href="http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list">http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list</a>



&nbsp; &nbsp; &nbsp; Veja quais s&atilde;o os assuntos do momento
no Yahoo! +Buscados
<a class="moz-txt-link-freetext" href="http://br.maisbuscados.yahoo.com">http://br.maisbuscados.yahoo.com</a>

------------------------------------------------------------------------------
_______________________________________________
GDAlgorithms-list mailing list
<a class="moz-txt-link-abbreviated" href="mailto:GDA...@li...">GDA...@li...</a>
<a class="moz-txt-link-freetext" href="https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list">https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list</a>
Archives:
<a class="moz-txt-link-freetext" href="http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list">http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list</a>

    </pre>
  </blockquote>
  <pre wrap=""><!---->

      __________________________________________________________________
The new Internet Explorer&reg; 8 - Faster, safer, easier.  Optimized for Yahoo!  Get it Now for Free! at <a class="moz-txt-link-freetext" href="http://downloads.yahoo.com/ca/internetexplorer/">http://downloads.yahoo.com/ca/internetexplorer/</a>

------------------------------------------------------------------------------
_______________________________________________
GDAlgorithms-list mailing list
<a class="moz-txt-link-abbreviated" href="mailto:GDA...@li...">GDA...@li...</a>
<a class="moz-txt-link-freetext" href="https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list">https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list</a>
Archives:
<a class="moz-txt-link-freetext" href="http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list">http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list</a>

  </pre>
</blockquote>
<br>
<br>
<div class="moz-signature">-- <br>
<pre>  Revenge is the most pointless and damaging of human desires.
</pre>
</div>
</body>
</html>

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

[metanet s. <met...@ya...>]

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 <jos...@ya...> wrote:

> From: Jose Marin <jos...@ya...>
> Subject: [Algorithms] Res: Res: Polygon from point cloud and other from triangle list?
> To: "Game Development Algorithms" <gda...@li...>
> 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 <jw...@gm...>
> Para: Game Development Algorithms <gda...@li...>
> 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
> GDA...@li...
> 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
> GDA...@li...
> 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/

Re: [Algorithms] Polygon from point cloud and other from triangle list?

[Rachel B. <ra...@ra...>]

What you are looking for is probably "Alpha Shapes". This PDF:
http://www.cis.rit.edu/people/faculty/kerekes/pdfs/AIPR_2007_Gurram.pdf is a
good starting point.

(Sorry if that is a duplicate or even triplicate post - I just changed
mailing addresses, and mailman mumbled something about "message being held
for moderation"....)

Rachel

Re: [Algorithms] Polygon from point cloud and other from triangle list?

[Rachel B. <ra...@ra...>]

What you are looking for is probably "Alpha Shapes". This PDF:
http://www.cis.rit.edu/people/faculty/kerekes/pdfs/AIPR_2007_Gurram.pdf is a
good starting point.

(Sorry if that is a duplicate or even triplicate post - I just changed
mailing addresses, and mailman mumbled something about "message being held
for moderation"....)

Rachel

[Algorithms] Res: Res: Polygon from point cloud and other from triangle list?

[Jose M. <jos...@ya...>]

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 <jw...@gm...>
Para: Game Development Algorithms <gda...@li...>
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
GDA...@li...
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

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

[Jon W. <jw...@gm...>]

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.

Re: [Algorithms] Polygon from point cloud and other from triangle list?

[James R. <ja...@fu...>]

Something like a Voronoi diagram?

http://en.wikipedia.org/wiki/Voronoi_diagram



Jose Marin wrote:
> Hi.
>
> Do you know some algorithm to create a polygon from a 2D point cloud?
>
> Another task would be create a polygon from a bunch of triangles (not related to the above task).
>
> The resulting polygon may be non-convex.
>
> I have searched, but didn't find any good solution...
>
> Thanks.
>
> Jose
>
>
>
>       Veja quais são os assuntos do momento no Yahoo! +Buscados
> http://br.maisbuscados.yahoo.com
>
> ------------------------------------------------------------------------------
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>
>   

[Algorithms] Res: Polygon from point cloud and other from triangle list?

[Jose M. <jos...@ya...>]

Hmm, really, its a very generic question, I should be more detailed.

I have some shapes, grouped together, and would like to create a polygon that represents the resulting shape.

Something like a tangram shape, that is formed by smaller shapes.

I need to find the outline polygon (may be non-convex, and will be on most of the times) defined by the resulting shape.

----- Mensagem original ----
De: Simon Fenney <sim...@po...>
Para: Game Development Algorithms <gda...@li...>
Enviadas: Quarta-feira, 24 de Junho de 2009 10:28:23
Assunto: Re: [Algorithms] Polygon from point cloud and other from triangle list?

Jose Marin wrote:
> Hi.
> 
> Do you know some algorithm to create a polygon from a 2D point cloud?
> The resulting polygon may be non-convex.

What other constraints are required? If none then, AFAICS, given N
points you could create (N-1)!/2 different (potentially
self-intersecting) polygons.

Simon


------------------------------------------------------------------------------
_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
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

Re: [Algorithms] Polygon from point cloud and other from triangle list?

[Simon F. <sim...@po...>]

Jose Marin wrote:
> Hi.
> 
> Do you know some algorithm to create a polygon from a 2D point cloud?
> The resulting polygon may be non-convex.

What other constraints are required? If none then, AFAICS, given N
points you could create (N-1)!/2 different (potentially
self-intersecting) polygons.

Simon

Re: [Algorithms] Polygon from point cloud and other from triangle list?

[Richard F. <ra...@gm...>]

try finding the most "lonely" vertex (one furthest from the average
position), then use that as a start point.
from the start point, assume an initial direction vector of any
non-picked point, then pick points adn compare to see if any of them
point "futher out" (have a larger value when dot with outward
direction vector (which is just the normalised position of the initial
vertex))
once you have the lowest curvature, then continue to the next point,
chosing a next vertex that is in the same direction and also low
curvature (high dot in forwards (forwards = this point pos - last
point pos) with high dot in out (again, just the normalised position
of the vertex)

once you have done this until the best next point is the initial
position, you will have a convex shape that you can start adding the
other vertices to.

ad vertices one at a time, choose the unpicked vertex that is closest
to a line, then add it as a split on that line.
repeat until all unpicked vertices are gone.

2009/6/24 Jose Marin <jos...@ya...>:
>
> Hi.
>
> Do you know some algorithm to create a polygon from a 2D point cloud?
>
> Another task would be create a polygon from a bunch of triangles (not related to the above task).
>
> The resulting polygon may be non-convex.
>
> I have searched, but didn't find any good solution...
>
> Thanks.
>
> Jose
>
>
>
>      Veja quais são os assuntos do momento no Yahoo! +Buscados
> http://br.maisbuscados.yahoo.com
>
> ------------------------------------------------------------------------------
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>



-- 
fabs();
Just because the world is full of people that think just like you,
doesn't mean the other ones can't be right.

[Algorithms] Polygon from point cloud and other from triangle list?

[Jose M. <jos...@ya...>]

Hi.

Do you know some algorithm to create a polygon from a 2D point cloud?

Another task would be create a polygon from a bunch of triangles (not related to the above task).

The resulting polygon may be non-convex.

I have searched, but didn't find any good solution...

Thanks.

Jose



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

Re: [Algorithms] sort and sweep / sweep and prune and just touching objects

[<Pau...@sc...>]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

> In this case, the tie breaker could be that end points are sorted before 

> start points. That goes into the sorting function, not the index testing 

> function.
> Although if you support resting/touching contact, you probably want the 
> tie breaker to be end points go after beginning points...

Someone mailed me off-line and said a way to get around this problem is to 
artificially bias end points so that min points have their lowest bit 
cleared from the value and max bits have their lowest bit set, that way a 
max can never have the same value as a min. Of course this could lead to 
false positives, but since its a broadphase algorithm this isn't the end 
of the world. Additionally, if we've entered the realm of false positives 
you might as well quantise the values to unsigned ints/shorts and then you 
can compare integers instead of floats...

Not sure if that was the same as what you are suggesting (the first part)?

Cheers, Paul.
**********************************************************************
This email and any files transmitted with it are confidential and intended 
solely for the use of the individual or entity to whom they are addressed. 
If you have received this email in error please notify pos...@sc...
This footnote also confirms that this email message has been checked for 
all known viruses.
Sony Computer Entertainment Europe Limited
Registered Office: 10 Great Marlborough Street, London W1F 7LP, United 
Kingdom
Registered in England: 3277793
**********************************************************************
P Please consider the environment before printing this e-mail

-----BEGIN PGP SIGNATURE-----
Version: PGP Universal 2.9.1 (Build 287)
Charset: US-ASCII

wsBVAwUBSjtMznajGqjtoMHxAQgnOQf/aEsMSMDcFOlDCp9BjJV4W8INk45Mlnuw
nGqcK4dMxkfZ/B88pv7S1KmXCuQmpwcnyovKKvsF/kvOsePmyTSKqCrnNAkAkGAx
op6SdI7KbBksiqVg6at7ZggQomk3NtNasWpFT/ZDcggbQdYiy6IOt5b2Fg/0p2L9
E8+D5KRX2C9JHX8lxUn3tAxeWgCnEwkbQzS7iE1KF3ePDTeadvq5qO5rRn2Yua41
Zeu+WWxfBN/sK35vxbyyXenbgupiGqjr6YhKaMXSysZO4QX9IGGVBM27C2biOzlJ
8jaggnplGoPXs98SJUbMAXLkgQWJznm8Q/bRmTXdqRl+O3EOZ+VXJw==
=8PdK
-----END PGP SIGNATURE-----

Re: [Algorithms] sort and sweep / sweep and prune and just touching objects

[Jon W. <jw...@gm...>]

Pau...@sc... wrote:
> A-------B
>         C-------D
>         E---------F
>
> Indices:
>
> A  B  C  D  E  F
> 0  2  1  4  3  5
>
> So if you were to check C to see if it were before B by index you'd get a 
> positive, but checking E for before B gives a negative even though both 
> B,C and E have the same actual value.
>   


In this case, the tie breaker could be that end points are sorted before 
start points. That goes into the sorting function, not the index testing 
function.
Although if you support resting/touching contact, you probably want the 
tie breaker to be end points go after beginning points...

Sincerely,

jw


-- 

  Revenge is the most pointless and damaging of human desires.

Re: [Algorithms] sort and sweep / sweep and prune and just touching objects

[<Pau...@sc...>]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

> If the problem is that the same value maps to multiple indices, then I 
> don't see why -- you get a stable sort by checking index (as long as the 

> index relates to the value).

The values are sorted correctly, the trouble is when i come to detect 
whether the is a 1d overlap of bounds, i can't check the indices instead 
of the values because one value maps to many indices in the case of 
exactly touching objects:

i.e.

A-------B
        C-------D
        E---------F

Indices:

A  B  C  D  E  F
0  2  1  4  3  5

So if you were to check C to see if it were before B by index you'd get a 
positive, but checking E for before B gives a negative even though both 
B,C and E have the same actual value.

Hope i haven't messed that example up :)

Cheers, Paul.

**********************************************************************
This email and any files transmitted with it are confidential and intended 
solely for the use of the individual or entity to whom they are addressed. 
If you have received this email in error please notify pos...@sc...
This footnote also confirms that this email message has been checked for 
all known viruses.
Sony Computer Entertainment Europe Limited
Registered Office: 10 Great Marlborough Street, London W1F 7LP, United 
Kingdom
Registered in England: 3277793
**********************************************************************
P Please consider the environment before printing this e-mail

-----BEGIN PGP SIGNATURE-----
Version: PGP Universal 2.9.1 (Build 287)
Charset: US-ASCII

wsBVAwUBSjp/mHajGqjtoMHxAQhwfQgAkuRIr44cCNt86GsEVgfqceS2v22QPmHy
TlZZSHp5LSdjKGQCbj5YznMzhZdbmNKFj9Xj+DCzG9KQHU1ShBnh5t0xljDiQ9EV
aNmMjRo2J7JpqXw+p01rwk9NLuzcNbjxYYDMy8s8ddYDc9Av0eD+IFzSfZIb6Upb
mX6PV7BGlGtmeKvLSR46YKpgEF53aHIkY1WF3HF9yprJzqdVlbZzHRONMwO1h47s
VvGPFBYdqRBcwQ12WHIOCCLgV6ec7nW5fKbXzOZ4ejh2KMlMEG3o5qu8bVR3LyZY
ufN3TlkfU8s4L5JALwH4osJKhvjTGe15bp4JS0MSFm+JkaJXhZqB1A==
=wi0P
-----END PGP SIGNATURE-----

Re: [Algorithms] sort and sweep / sweep and prune and just touching objects

[Jon W. <jw...@gm...>]

Pau...@sc... wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA256
>
>   
>> In a stable sort, you generally have a tie breaker, such as the "this" 
>> pointer of the value in question, in the case of a tie.
>>     
>
> Hmmm, wouldn't that mean i'd need to do the expensive value vs value test 
> anyway first?
>   

If the problem is that the same value maps to multiple indices, then I 
don't see why -- you get a stable sort by checking index (as long as the 
index relates to the value).

If the problem is that the same index maps to multiple values, then yes, 
you need to check values.

If the problem is that you have non-unique values, which map to 
non-unique indices, but you want an ordering between separate values 
with the same value/index, then using a tie-breaker is one solution.

Sincerely,

jw

Re: [Algorithms] sort and sweep / sweep and prune and just touching objects

[<Pau...@sc...>]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

> In a stable sort, you generally have a tie breaker, such as the "this" 
> pointer of the value in question, in the case of a tie.

Hmmm, wouldn't that mean i'd need to do the expensive value vs value test 
anyway first?
**********************************************************************
This email and any files transmitted with it are confidential and intended 
solely for the use of the individual or entity to whom they are addressed. 
If you have received this email in error please notify pos...@sc...
This footnote also confirms that this email message has been checked for 
all known viruses.
Sony Computer Entertainment Europe Limited
Registered Office: 10 Great Marlborough Street, London W1F 7LP, United 
Kingdom
Registered in England: 3277793
**********************************************************************
P Please consider the environment before printing this e-mail

-----BEGIN PGP SIGNATURE-----
Version: PGP Universal 2.9.1 (Build 287)
Charset: US-ASCII

wsBVAwUBSjpq+HajGqjtoMHxAQjxSwf9FZYsHOhF5iq6fAYKT+3HSwpwlVAiahQG
WlA5GZvrwS8PkmDUjOqwxMCZdT59T7OgGw7RXvmbZiukoLuFI7gcILT+UKDmCgDB
nx+KKSVg67g+EEijKiQnJ1yzX7+hnFdLJAio9IUzAnJGXDbNBzS0ILr5Lf7YoqVK
6yO0jCS4fhef4DKz1I7eQ+RqKhCogIQn5LbICji3Y6yRz61t5zJgyb+uFvuuGzOD
8k8x45n8M8vkjNcBzl50fDqHU4OYl6jkpdwselOp/RUCI7qNz4k5pmnuXlpVSdjC
0dyVDrjrkNjlfqLbGABSmm5SM5edy89zXiaoJPBEYCZ90mW97qx0rQ==
=5OzP
-----END PGP SIGNATURE-----

Re: [Algorithms] sort and sweep / sweep and prune and just touching objects

[Jon W. <jw...@gm...>]

Pau...@sc... wrote:
> So do i need to compare bound values in all cases? Is there another way 
> around this?
>   

In a stable sort, you generally have a tie breaker, such as the "this" 
pointer of the value in question, in the case of a tie.

Sincerely,

jw

[Algorithms] sort and sweep / sweep and prune and just touching objects

[<Pau...@sc...>]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

Hi guys,

I'm running into a few issues with my sort and sweep broad-phase 
algorithm. It comes down to bounds in an axis with identical values.

Most of the stuff i've read about using an array based method for sorting 
your axis values say a good optimisation (for the overlap test) is to 
compare bound indices instead of bound values. But in the case where there 
are identical bound values in the axis, this breaks down since some of 
them would be reported as overlapping and some would not depending on 
where they were in the array. Unfortunately this case comes up a lot in 
our game.

So do i need to compare bound values in all cases? Is there another way 
around this?

Cheers, Paul.
**********************************************************************
This email and any files transmitted with it are confidential and intended 
solely for the use of the individual or entity to whom they are addressed. 
If you have received this email in error please notify pos...@sc...
This footnote also confirms that this email message has been checked for 
all known viruses.
Sony Computer Entertainment Europe Limited
Registered Office: 10 Great Marlborough Street, London W1F 7LP, United 
Kingdom
Registered in England: 3277793
**********************************************************************
P Please consider the environment before printing this e-mail

-----BEGIN PGP SIGNATURE-----
Version: PGP Universal 2.9.1 (Build 287)
Charset: US-ASCII

wsBVAwUBSjpRynajGqjtoMHxAQiZ2gf/ZcIToOT/o1LNU4RKP70AZtIbEek2lObO
g1M7VbLNmgP9vRZUIRcr/4kNi9W/o2IIPguTfNYtOiBWZ5N8cVmgwOzF25DUR2Kq
dhF7zPMK5mAZj+e3PBFEJaBwXZFockqBt44ekTV+z4jA3AZfjgvRr+By+oSXc9QU
ym566w1L3pUIfwZaj3b2X7IKVG6GeFitQ2s/21QlFUUSBlw9W0N7Alsl8SKhgqrP
rHfqSjNKtxjR6at3TApMsS73PMXPZjJJxth7uClwnEy53tEbH3TADVjuFU+EYYIZ
qI9dyiqAklFRjir3lI8uwUqJzthzDb5qQZrgNqegORQGB2Z/75Yosw==
=xzS9
-----END PGP SIGNATURE-----