Jump to content

# Preparing a list of points on convex hull for triangulation

## Recommended Posts

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

##### Share on other sites

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

##### Share on other sites

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

##### Share on other sites

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

##### Share on other sites

...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?

##### Share on other sites

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

Regards

##### Share on other sites

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

Regards,

Aloy

##### Share on other sites

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

##### Share on other sites

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.

##### Share on other sites

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..

Edited by aloy
##### Share on other sites

• 1 month later...

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

Edited by aloy
Attach another file
##### Share on other sites

• 3 weeks later...
• 8 months later...

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.

Unfortunately, your content contains terms that we do not allow. Please edit your content to remove the highlighted words below.
Reply to this topic...

×   Pasted as rich text.   Restore formatting

Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×
×
×
• Create New...