Grid generation for an complex polygon

[Kumar K]

Hi ,

I have got a polygon with n sides where all the edges are parallel to the coordinate axis(XZ)
this polygon form a floor with these edges and , i need to genrate the grid/Mesh for the polygon. I will try to illustrate the polygon clearly with my key board art.

   |-----|    |-----------------|
   |     |    |                 |
   |     |----|                 |
   |                      |-----|
   |                      |      
   |         |-----|      |      
   |         |     |      |-----|
   |         |     |            |
   ----------|     |------------|

The above fig describes a polygon, I need to fill the polygon with the grid cell size P X q.The cells need to be present only with in the surface.

Can any one help me to design the algorihm.

Thanks
kumar.k

[Kumar K]

sorry my polygon art became worst after submittion. Think of the room and how the room can be and tht is my polygon with n sides. need to genrate the gird for the floor of the room

kumar.k

[ZbuffeR]

Do you absolutely need a grid, or a mesh of triangles will be enougth ?

For triangles, just divide your complex polygon in several convex polygons, then create triangles from the first vertice of each simple polygon to each edge of this polygon.

For a grid, if your original polygons if well aligned to the grid, it should be pretty simple.

[lxnyce]

What it seems is that you have a polygon and want to digitize it on a grid. This is the same thing pretty much as rasterizing a polygon onto your display. There are a couple methods around it.

The easiest solution would be to use the point in polygon test. For every grid point of your surface, test the grids 2D position to see if it lies inside the polygon. Here is a link for the polygon intersection alrogithm :
http://astronomy.swin.edu.au/~pbourk...ry/insidepoly/

Another method is polygon scan conversion. This is the second easiest approach, as you also use the polygon in its original form. Think of this as filling your grid with the polygon one line at a time. Just look up polygon scan conversion in google to find out more.

As ZbuffeR said, you can always tesselate the polygon to get the individual triangles, then scan convert each one or use the point in poly approach explained above. However tesselation is not a trivial matter. So unless you happen to have something for tesselation handy and are familar with it, I would suggest you use the above two methods.

For your purposes, I think the first step might be best. Its not too fast, but this is a one time thing I am assuming and will go unnoticed really (even for a complex poly).

[Kumar K]

Here i dont want triangles , grid generation is not my actual requirement.I need to tile the floor which is an n sided polygon.
I need to get the coordinates of each tile/cell on it starting from some fixed location. The tile size can be pXq

ALL THE POLYGON EDGES LIE ON THE SAME PLANE

Think of the floor of the room like this

http://www.alistairmackintosh.co.uk/Media/images/WW%20Trav%20B\'Room.JPG