Preparing a list of points on convex hull for triangulation

I attach a drawing showing points from a corridor survey (which was given originally as an excel file which was converted to a lisp file with a simple manupulation). I wish to carry out triangulation of these points. The algorithm recommended by some uni students and professors is first to prepare the convex hull (the points on the periphery as I understand it)and then start with the shortest base. My problem is how to prepare the list of those points in the convex hull.

Any help would be very much appreciated.

Aloy

Convex_hull.dwg

I recommend using the Graham Scan algorithm, as I demonstrate here.

And I am also interested in an algorithm that creates 3D terrain model with 3DFACE entities. Any suggestions?

Lee Mac,

Thanks for the reply. However the convexhull did not work on the list attached. It says too few arguments. What can be the reason?

regards,

Aloy

pointlist.lsp

...the convexhull did not work on the list attached. It says too few arguments. What can be the reason?

How are you calling the function?

I loaded the list of points, then the fuction and called using (LM:ConvexHull) and enter.

Regards

Thanks Lee Mac, it works when I enter (LM:Convexhull lst). Will be in touch with you soon.

Regards,

Aloy

Lee Mac,

It does not seem to work properly. Try the list given earlier and generate the points using :

(mapcar '(lambda(thePoint) (command "_INSERT" pointblock (car ptlist) 1 1 0))

ptlist)

We have to define "pointBlock" seperately.

We get the drawing given in my first posting. We use the same list with the LM:ConvexHull function and you should get only thirteen points, which is not correct. Perhaps we have to adopt a devide and conqure approach.

Regards,

Aloy

My function works exactly as described and intended to return the Convex Hull of a point set.

The mistake is in your code or your misunderstanding of a convex hull.

Lee Mac,

My aim is to do a triangulation using the method given in the following link:

http://www.univ-valenciennes.fr/congres/3D2006/Abstracts/159-Shojaee.pdf

using the method 2 which is step by step method, first getting the covexhull then selecting the shortest base.

My understanding of the convex hull is from above and the following Wikypedia site:

http://en.wikipedia.org/wiki/Convex_hull_algorithms

using a set of points on a polygon, and using a simple algorithm which I discovered independantly before looking at the algorithm for simple polygon.

I think you, too, have done something like that, how ever I attemted using all the points given in the drawing of my above posting with your code instead of giving only the points in the polygon.

So, my question is how to get the polygon first?.

Thanks,

Aloy Hett..

I have searched the internet and found a routine given by Pedro Ferreira of Lisbao given below, it handles points given one at a time. I modified it to take on a list containing few points, but not a very large number as given in one of my previous posts. That modified version is also given below and works well with vectors and not lines as in the original version. When the vectors are changed to lines, they criscross and give error messages. Can anyone give a clue as to why this happens?.

Triangulation.lsp

TriangulationWithVectors.lsp

TriangulationWithLines.lsp

NewPointlist.lsp

Download TopoGraph.zip (DTM.lsp) and see if it helps.

http://www.freecadapps.com/swdetails.php?page=search&value=&orgvalue=&review=4366&rowcolor=ffffcc

Important information for triangulation, can also be find here:

http://paulbourke.net/papers/triangulate/

http://www.theswamp.org/index.php?PHPSESSID=0pq2vs5tce34tjfkvn3po8gj50&topic=9042.0;nowap

http://www.behance.net/gallery/Delaunay-triangulation-with-AutoLisp/4237467

http://www.cadtutor.net/forum/showthread.php?53184-topography-survey-points

And with this, it has solved the triangulation.

or

http://www.glamsen.se/CadTools.htm