I need to come up with an algorithm which is outside my normal area of expertise and I could really do with some help. Perhaps you already know a solution or just some ideas or insights to help me get on the right track.
I have a rectangular area with a number of points randomly distributed across it. I need to completely cover the area with a network of non-overlapping triangles, using all the points plus the for corners as vertices. For those familiar with the networks of triangulation points cartographers used to survey, the result should be something similar.
My feeble observations so far include:
- no point may be inside any triangle
- all points will be a vertex in > 1 triangle
- each side of the rectangle will act as an edge connecting adjacent corners in one triangle.
All suggestions gratefully received.
