# Make tris out of 2d set of points

## Recommended Posts

Im currently looking for some easy explanation of this algorithm for now i see that this pseudocode just removes newly created triangle from list making empty triangle list, i am not quite sure if that pseudocode could even work

For now what i get

Having a set of point get min and max if y and x then create big triangle that covers whole pointset area make a circumcircle out of that tri.

Add that tri to the output tri list

Then loop through all verts for int i loop

If a vertex is inside circumcircle of that super tri add that tri to badtri list

Now for each edge in bad tri

Check whenever other bad tri shares an edge if not add this not shared edge to some outputpolygon, so in first iteration it adds supertriangle to outputtrilist

Now remove that bad triangle from tri list

Now for each edge in outputpolygon form triangle to vert[ i ]

Now if that newly formed triangle contains a vetex from super triangle remove that triangle ---- now thats where my brain blows off you just added a triangle only to remove it damn.

Heres pseducode and below a link to code

 BowyerWatson (pointList)
// pointList is a set of coordinates defining the points to be triangulated
triangulation := empty triangle mesh data structure
add super-triangle to triangulation // must be large enough to completely contain all the points in pointList
for each point in pointList do // add all the points one at a time to the triangulation
for each triangle in triangulation do // first find all the triangles that are no longer valid due to the insertion
if point is inside circumcircle of triangle
polygon := empty set
for each triangle in badTriangles do // find the boundary of the polygonal hole
for each edge in triangle do
if edge is not shared by any other triangles in badTriangles
for each triangle in badTriangles do // remove them from the data structure
remove triangle from triangulation
for each edge in polygon do // re-triangulate the polygonal hole
newTri := form a triangle from edge to point
for each triangle in triangulation // done inserting points, now clean up
if triangle contains a vertex from original super-triangle
remove triangle from triangulation
return triangulation

This just doesnt make any sense...

x_X

##### Share on other sites
1 hour ago, WiredCat said:

Now if that newly formed triangle contains a vetex from super triangle remove that triangle ---- now thats where my brain blows off you just added a triangle only to remove it damn.

Notice that those step is done after all the points are added. So it does not remove the triangle just added, because any addition has been done much earlier in the previous loop. (Look at the indentation level.)

The step is just there to get rid of all those wrong triangles that were build with the super triangle's corners. This is because the corners of the super triangle are build artificially; in other words, those points are not part of the original set of point. Hence also none of the edges and none of the triangles that use those points belong to the result.

Edited by haegarr

##### Share on other sites

But since within first iteration we apply super triangle to outputpolygon and then use its edges to form new triangles they always contain a point within supertriangle...

##### Share on other sites
15 hours ago, WiredCat said:

But since within first iteration we apply super triangle to outputpolygon and then use its edges to form new triangles they always contain a point within supertriangle...

Yes, the first iteration does produce only triangles that use an edge (and hence 2 vertices) of the super triangle. Also the second and (I think) third iterations uses such vertices. The third iteration is the first one where a triangle occurs that is uncoupled from super-triangle vertices. That's fine, because you need to have at least 3 vertices in your original set to have at least 1 triangle as output.

Look at the picture sequence of wikipedia's entry to Bowyer-Watson. Notice the red triangles: They are generated as needed but are rubbish in the end. The algorithm removes them in the last step. The blue triangles are all that remain as outcome.

Edited by haegarr

## Create an account

Register a new account

1. 1
Rutin
33
2. 2
3. 3
4. 4
5. 5

• 13
• 9
• 9
• 9
• 9
• ### Forum Statistics

• Total Topics
633330
• Total Posts
3011388
• ### Who's Online (See full list)

There are no registered users currently online

×