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.