problem with triangulation delaunay points for autocad points

[Giuliano64]

Hello, everyone.

are struggling with a problem of 3d reconstruction of a topographic relief.
with a couple of days (and nights!) of work, I managed to write a macro in vba that builds the triangles of delaunay on the horizontal plane, used subsequently to determine the solid with the upper surface corresponding to the top relief top.

the fact is that the algorithm I thought doesn't seem to be particularly efficient, since some applet java found on the internet make the triangulation in real-time while my program also puts us a few hours for 300 points.. .

Do any of you have any suggestions to give me?

Thank you all.

 

[GP.]

...some of you have any suggestions to give me?

for your macro no, but if you don't want to waste any more time you can use this:http://www.cad3d.it/forum1/showthread.php?t=1005

 

[Tristan]

there are fior fior of plugins both free and paid that do this. Didn't you google first?

 

[Giuliano64]

Maybe I used to google first.
But the thing is, I was buzzing in my head a solution... And I tried it.

 

[giovanni.a]

Can you tell us?

 

[Giuliano64]

Okay.

about the triangulation of delaunay, in my research on the web I learned that it is used precisely to define the best mesh of representation of objects such as, for example, in the calculation of finite elements, and there is the problem to 3 dimensions and also to n dimensions.

in my case is a 2-dimensional problem.
the cloud of points is given by the topographic tool.
the triangulation of delaunay has a series of mathematical characteristics (which I do not know exactly) and on the floor can be obtained according to the following property:
- for each valid triangle the circumscribed circle contains only three vertices of the triangle and contains no other points.
if there are other points on the edge of the circle it is not possible to uniquely determine the best triangle.

before discovering this fundamental characteristic I have engaged myself in a series of attempts that however did not fully build the triangulation.
after that it was very easy.

with the macro in vba I proceeded like this:
- scanning of entities to determine the number of entities "points";
- acquisition of all points in an array;
- scan the array for the determination of the triangles and solids below:
> for each summit1 from 1 to 2 points
> > for each summit1+1 to number points-1
>> > for each summit3 from summit2+1 to number points
>>> calculates the area of the triangle
If the area is different from zero
>>> > determines the equation of the straight oriented 1-2
> > > > determines the equation of the 1-3
>> > > determines the intersection point between normal to 1-2 and normal to 1-3
(center of the circumscribed circle)
>>> > determines the distance c-1 (route of the circumscribed circle)
> > > for all points except summit1 summit2 summit3
>>> > > calculates the distance from c and controls that is higher than the radius
Next item
>>> if you have not found points within the circle
>>>> > > draws a 2d polyline closed between 1-2-3 and zero
>>> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
>>>> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
>>>> > > > > > > > > > > cuts the extruded solid using a step-by-step 1-2-3
(to know which part of solid keep on makes use of the sign of the calculated area before)
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
> > > I close the se
> next summit
Next summit
next summit
(if two triangles with common side 1-2 were already produced during the top 2 scan, no further points are required).

made this act manually to clean the solid group from those triangles that do not belong to the relief, then I join all the prisms in a single solid with which, for example, I also realize the level curves to work at the table.