Function earclip_cell

pub fn earclip_cell<T: CoordsFloat>(
    cmap: &mut CMap2<T>,
    face_id: FaceIdType,
    new_darts: &[DartIdType],
) -> Result<(), TriangulateError>

Triangulates a face using the ear clipping method.

This function triangulates a cell (face) of a 2D combinatorial map by iteratively clipping ears (triangles) from the polygon until only a single triangle remains.

Note that:

• the function assumes that the polygon is simple (no self-intersections or holes) and that the interior is lcoated on the LEFT SIDE of the cross-product.
• the implementation might need adjustments for parallel operations or when working with identifiers not greater than existing ones.

Arguments

• cmap: &mut CMap2 - A mutable reference to the modified CMap2.
• face_id: FaceIdentifier - Identifier of the face to triangulate within the map.
• new_darts: &[DartIdentifier] - Identifiers of pre-allocated darts for the new edges; the slice length should match the expected number of edges created by the triangulation. For an n-sided polygon, the number of created edge is n-3, so the number of dart is (n-3)*2.

Behavior

• The function begins by checking if the face has 3 or fewer vertices, in which case it’s already triangulated or cannot be further processed.
• It ensures that the number of new darts provided matches the triangulation requirement.
• Iteratively finds an ‘ear’ of the polygon, where an ear is defined by three consecutive vertices where the triangle formed by these vertices is inside the original polygon.
• Clips this ear by updating the combinatorial map’s structure, effectively removing one vertex from the polygon per iteration.
• Updates the list of darts and vertices accordingly after each ear clip.
• Continues until the polygon is reduced to a triangle.

Errors

This function will return an error if the face wasn’t triangulated. There can be multiple reason for this:

• The face is incompatible with the operation (made of 1, 2 or 3 vertices)
• The number of pre-allocated darts did not match the expected number (see [#arguments])
• The face contains one or more undefined vertices
• The face does not contain an ear

Note that in all cases except the last, the face will remain the same as it was before the function call.

Because the ear clipping algorithm works iteratively, the face may be modified a few times before reaching a state where no ear can be found. Note, however, that this cannot occur if the face satisfies requirements mentionned above because of the Two ears theorem.