Does anyone know of a (good) algorithm to tesselate a 2D polygon?

At least I think tesselation is what I'm after - what I want to do is
distributing points evenly inside a polygon with a certain maximum distance
to each other (that is, tesselate(d) should fill the polygon with enogh
points so that no points are more separated by more than d distance), and
then make a triangular mesh out of it.

Any ideas?

Post a reply to this message

Martin Magnusson wrote:
> 
> Does anyone know of a (good) algorithm to tesselate a 2D polygon?
> 
> At least I think tesselation is what I'm after - what I want to do is
> distributing points evenly inside a polygon with a certain maximum distance
> to each other (that is, tesselate(d) should fill the polygon with enogh
> points so that no points are more separated by more than d distance), and
> then make a triangular mesh out of it.
> 
> Any ideas?

You might find something useful at one of the sites listed here:
http://www.povray.org/links/3D_Resources/3D_solid_construction_methods/

-- 
Ken Tyler -  1200+ Povray, Graphics, 3D Rendering, and Raytracing Links:
http://home.pacbell.net/tylereng/index.html http://www.povray.org/links/

Post a reply to this message

On Thu, 18 Nov 1999 15:37:55 -0700, "Martin Magnusson"
<mar### [at] studentuuse> wrote:

>Does anyone know of a (good) algorithm to tesselate a 2D polygon?
>
>At least I think tesselation is what I'm after - what I want to do is
>distributing points evenly inside a polygon with a certain maximum distance
>to each other (that is, tesselate(d) should fill the polygon with enogh
>points so that no points are more separated by more than d distance), and
>then make a triangular mesh out of it.
>
>Any ideas?

Ideas, yes. Solution, no. That's how I usually proceed, anyway :)

Using baricentric coordinates you can place a number of points in the
polygon. Now set up a simple repulsive force among them and the edges
of the poly and either calculate a preset amount of "time" or until
the speed of all particles drops below a certain value. There *might*
be a procedural approach, and if there is, Ken will have most probably
found the link to it by the time I post this message. Oh well...


Peter Popov
ICQ: 15002700

Post a reply to this message

>Using baricentric coordinates
Say what?

>Now set up a simple repulsive force among them and the edges
That sounds like a good approach. It might take some time with 10000 or so
points, but then again, any algorithm will probably have to take some time.

Post a reply to this message

Martin Magnusson wrote:
> 
> >Using baricentric coordinates
> Say what?

Barycentric \Bar`y*cen"tric\, a. [Gr. ? heavy + ? center.] Of or pertaining
to the center of gravity. 

-- 
Ken Tyler -  1200+ Povray, Graphics, 3D Rendering, and Raytracing Links:
http://home.pacbell.net/tylereng/index.html http://www.povray.org/links/

Post a reply to this message

>> >Using baricentric coordinates
>> Say what?
>Barycentric \Bar`y*cen"tric\, a. [Gr. ? heavy + ? center.] Of or pertaining
>to the center of gravity.

Ah, thanks!

Post a reply to this message

Martin Magnusson wrote:
> 
> Does anyone know of a (good) algorithm to tesselate a 2D polygon?
> 
> At least I think tesselation is what I'm after - what I want to do is
> distributing points evenly inside a polygon with a certain maximum distance
> to each other (that is, tesselate(d) should fill the polygon with enogh
> points so that no points are more separated by more than d distance), and
> then make a triangular mesh out of it.
> 
> Any ideas?

http://xfactor.wpi.edu/Works/DCubanski/mva93h/subsection3_3_2.html

-- 
Ken Tyler -  1200+ Povray, Graphics, 3D Rendering, and Raytracing Links:
http://home.pacbell.net/tylereng/index.html http://www.povray.org/links/

Post a reply to this message

Thanks a lot for your help. I love you guys!

Post a reply to this message