Next: Domain Discretization Up: Elimination of Cyclic Violation Dependency Previous: Safe Violation


Simplex Formation

The creation of a new simplex inside the domain is used as the last resort to get rid of all the violations associated with the constraining facets used to form the simplex. Assuming that each constraining facet corresponds to the outer boundary of the domain to be discretized, once it is used to form , it can be removed from the set of constraining facets. The new simplex is then temporarily considered to be out of the domain and its newly created boundary facets are appended to the set of constraining facets. The dependency graph is then updated to account for these new facets. Similarly, any existing point used to form is removed from set if it is not incident to any constraining facet in . If a new point was established to form (recall, that the constrained Delaunay triangulation may not exist for given and ), the point is added to and the dependency graph is updated. Since any safe violation can generally become again unsafe after the new point is introduced, there is a strong tendency to use only existing points, whenever possible, to form . Should this effort fail, all the safe violations are declared as unsafe and their classification as safe has to be verified again.

The new simplex creation is performed using the standard AFT. The position of the ideal point forming the ideal simplex is calculated. Then the neighbourhood of the ideal point is searched to identify already existing points in its vicinity. The best from the candidates in the neighbourhood or the ideal point, if there are no candidates, is taken to form a tentative simplex. If the tentative simplex does not mutually intersect with any already existing simplex or constraining facet, the point is accepted and the new simplex is constructed. Otherwise another point is searched for and the procedure is repeated.



Next: Domain Discretization Up: Elimination of Cyclic Violation Dependency Previous: Safe Violation

Daniel Rypl
2005-11-06