CODEWITHSUNDEEP
c#algorithmpath-finding
Delusional Logic
Delusional Logic

Reputation: 828

Creating a equilateral triangular grid over geometry

I need to create a equilateral triangular grid that fits a given geometry.

I have an image containing the geometry, it might include holes or thin paths. and i need to create a grid similar to this image:

http://neutrinodata.s3.amazonaws.com/theage-education/cmsimages/web/b3c5925e-34de-11e0-99f6-005056b06a0e-4535326.jpg

The circles are variable in diameter, and need to cover the entire geometry. the points does not have to be on the geometry.

Upvotes: 0

Views: 1040

Answers (2)

Olivier Jacot-Descombes
Olivier Jacot-Descombes

Reputation: 112612

You can think of the triangular grid as being an oblique rectangular grid

enter image description here

This enables you to store the state of each circle in a 2-dimensional matrix, for instance, and to use simple nested loops for processing. Of cause then you will have to translate these logical coordinates to the geometry plane coordinates for drawing.

const double Sin30 = 0.5;
static readonly double Cos30 = Math.Cos(30*Math.PI/180); 

for (int xLogical = 0; xLogical < NX; xLogical++) {
    for (int yLogical = 0; yLogical < NY; yLogical++) {
        double xGeo = GridDistance * xLogical * Cos30;
        double yGeo = GridDistance * (yLogical + xLogical * Sin30);
        ...
    }
}

Upvotes: 3

MoonKnight
MoonKnight

Reputation: 23831

I am assuming this is to create a 2D meshing tool. If it is, and it is homework, I suggest doing it yourself as you will get alot out of it. If it is not a meshing problem what I will have to say should help you regardless...

To do this, use the grid node centres to generate your equilaterals. If you don't have the centre points to start with you will need to look at first selecting an orientation for your object and then creating these (rectangular based) grid nodes (you will have to work out a way of testing whether these points actually lie inside your object boundaries). You can then construct your equilateral triangles using these points. Note. You again will have to deal with edge detection to get half decent accuracy.

To go a bit further that just equilaterals, and get a more accurate mesh, you will have to look into anisotropic mesh adaptation (AMA) using triangulation. This will be a lot harder than the basic approach outlined above - but fun!

Check out this link to a 2D tet-mesh generator using AMA. The paper this code is based on is:

  1. V. Dolejsi: Anisotropic mesh adaptation for finite volume and finite element methods on triangular meshes Computing and Visualisation in Science, 1:165-178, 1998.

Upvotes: 0

Related Questions