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