b'\n_START_ARTICLE_\nAlgoritmo de Bowyer-Watson\n_START_SECTION_\nDescripci\xc3\xb3n del algoritmo\n_START_PARAGRAPH_\nEl algoritmo de Bowyer-Watson emplea un m\xc3\xa9todo incremental, donde se parte de una triangulaci\xc3\xb3n de Delaunay trivial (generalmente un tri\xc3\xa1ngulo o un par de tri\xc3\xa1ngulos que forman una caja contenedora) a la que se a\xc3\xb1aden uno a uno los puntos. Despu\xc3\xa9s de cada inserci\xc3\xb3n, se eliminan aquellos tri\xc3\xa1ngulos cuyo circunc\xc3\xadrculo contengan al punto reci\xc3\xa9n introducido. El agujero resultante tiene forma de pol\xc3\xadgono estrellado simple, el cual puede ser retriangulado alrededor del punto reci\xc3\xa9n insertado._NEWLINE_Si nuestra estructura de datos dispone de informaci\xc3\xb3n de conectividad entre tri\xc3\xa1ngulos, el algoritmo tiene orden O(N log N) operaciones para triangular N puntos, a pesar de que existen casos degenerados especiales donde puede tomar O(N2). El orden en que se insertan los v\xc3\xa9rtices tiene una gran influencia en el tiempo de ejecuci\xc3\xb3n del algoritmo, por lo que a veces se realiza una ordenaci\xc3\xb3n previa de los mismos acorde a una curva de Hilbert.\xe2\x80\x8b_NEWLINE_Este algoritmo puede ser sensible a datos de entrada degenerados, como puntos situados en patrones regulares que hacen que la resoluci\xc3\xb3n de si un punto est\xc3\xa1 dentro o fuera del circunc\xc3\xadrculo de un tri\xc3\xa1ngulo dependa de decimales por debajo del umbral de precisi\xc3\xb3n de la representaci\xc3\xb3n en coma flotante. Por ello, es recomendable emplear alg\xc3\xban test robusto en lugar de comparar distancias eucl\xc3\xaddeas entre puntos._NEWLINE_\xe2\x80\x8b\n_START_SECTION_\nPseudoc\xc3\xb3digo\n_START_PARAGRAPH_\nfunction BowyerWatson (pointList)_NEWLINE_      // pointList es una lista de coordenadas de los puntos de entrada_NEWLINE_      triangulation := super-triangle // Crea un tri\xc3\xa1ngulo suficientemente grande como para contener todos los puntos de entrada_NEWLINE__NEWLINE_      for each point in pointList do // A\xc3\xb1ade los puntos uno a uno_NEWLINE__NEWLINE_         badTriangles := empty set_NEWLINE_         for each triangle in triangulation do // busca los tri\xc3\xa1ngulos que van a dejar de ser v\xc3\xa1lidos_NEWLINE_            if point is inside circumcircle of triangle_NEWLINE_               add triangle to badTriangles_NEWLINE__NEWLINE_         for each triangle in badTriangles do // Elimina los tri\xc3\xa1ngulos de la estructura, creando un hueco_NEWLINE_            remove triangle from triangulation_NEWLINE__NEWLINE_         polygon := empty set_NEWLINE_         for each triangle in badTriangles do // Calcula la frontera del hueco creado por bad_triangles_NEWLINE_            for each edge in triangle do_NEWLINE_               if edge is not shared by any other triangles in badTriangles_NEWLINE_                  add edge to polygon_NEWLINE__NEWLINE_         for each edge in polygon do // re-triangula el hueco usando el nuevo punto._NEWLINE_            newTri := form a triangle from edge to point_NEWLINE_            add newTri to triangulation_NEWLINE__NEWLINE_      for each triangle in triangulation // Limpieza de los tri\xc3\xa1ngulos externos a la lista de v\xc3\xa9rtices._NEWLINE_         if triangle contains a vertex from original super-triangle_NEWLINE_            remove triangle from triangulation_NEWLINE_      return triangulation'