gistfile1.txt

Flip_Reason cpm_edge_should_flip(Constrained_Path_Mesh const& cpm, Path_Mesh_Data const& mesh_data, Edge const& edge)
{
    Flip_Reason result;

    // --- Check for exterior edge
    if (edge_is_on_hull(edge))
    {
        result.should_flip = false;
        result.no = Flip_Reason::No::EXTERIOR;
        return result;
    }

    // --- Check for constraint
    Edge const& edge_twin = cpm.edges[edge.e_twin];
    {
        Edge_Data edge_data;
        edge_data.p0 = cpm.verts[edge.v_start];
        edge_data.p1 = cpm.verts[edge_twin.v_start];

        bool is_constrained = (Lookup(mesh_data.edges, edge_data) != nullptr);
        if (is_constrained)
        {
            result.should_flip = false;
            result.no = Flip_Reason::No::CONSTRAINED;
            return result;
        }
    }

    // Check for concave shape (chevron)
    Vert const* vert_twin_tip;
    Vert const* vert_tip;
    {
        Edge const& edge_next = cpm.edges[edge.e_next];
        Edge const& edge_next_next = cpm.edges[edge_next.e_next];
        vert_tip = cpm.verts + edge_next_next.v_start;

        Edge const& edge_twin_next = cpm.edges[edge_twin.e_next];
        Edge const& edge_twin_next_next = cpm.edges[edge_twin_next.e_next];
        vert_twin_tip = cpm.verts + edge_twin_next_next.v_start;

        Vert tip_to_tip = *vert_tip - *vert_twin_tip;
        Vert start_to_tip = *vert_tip - cpm.verts[edge.v_start];
        Vert end_to_tip = *vert_tip - cpm.verts[edge_twin.v_start];

        bool is_on_same_side =
            (vec_cross_xy(tip_to_tip, start_to_tip).z > num_t(0)) ==
            (vec_cross_xy(tip_to_tip, end_to_tip).z > num_t(0));

        if (is_on_same_side)
        {
            result.should_flip = false;
            result.no = Flip_Reason::No::CONCAVE;
            return result;
        }
    }

    // --- Check for constraint on flipped version of edge
    {
        Edge_Data edge_flipped_data;
        edge_flipped_data.p0 = *vert_tip;
        edge_flipped_data.p1 = *vert_twin_tip;
        bool is_flip_constrained = (Lookup(mesh_data.edges, edge_flipped_data) != nullptr);
        if (is_flip_constrained)
        {
            result.should_flip = true;
            result.yes = Flip_Reason::Yes::CONSTRAINED;
            return result;
        }
    }

    // --- Check Delaunay condition
    Tri const& tri = cpm.tris[edge.t_ccw];
    num_t dx = vert_twin_tip->x - tri.circumcenter.x;
    num_t dy = vert_twin_tip->y - tri.circumcenter.y;
    num_t dist_sq = dx * dx + dy * dy;

    // @HACK - fixed point error can lead to permanent flipping. Is this a good epsilon value?
    num_t constexpr EPSILON(0.35f);
    bool should_flip = dist_sq + EPSILON < tri.circumradius_sq;

    result.should_flip = should_flip;
    if (result.should_flip)     result.yes = Flip_Reason::Yes::DELAUNAY;
    else                        result.no = Flip_Reason::No::DELAUNAY;

    return result;
}