use std::cmp::Ordering;
use std::collections::VecDeque;

use crate::constants::MIN_CONTOUR_VERTICES_COUNT;
use crate::locatable::Location;
use crate::operations::{
    shrink_collinear_vertices, LocatePointInPointPointPointCircle, Orient,
};
use crate::oriented::Orientation;
use crate::relatable::Relation;
use crate::relating::segment_endpoints;
use crate::traits::{
    Contoural, Elemental, Iterable, Lengthsome, MultisegmentalIndexSegment,
    Multivertexal, MultivertexalIndexVertex, Polygonal, PolygonalIndexHole,
    Segmental, Sequence,
};

use super::mesh::Mesh;
use super::operations::{BoundaryEndpoints, DelaunayTriangulatable};
use super::quad_edge::{to_opposite_edge, QuadEdge, UNDEFINED_QUAD_EDGE};

#[derive(Clone)]
pub(crate) struct ConstrainedDelaunayTriangulation<Endpoint> {
    left_side: QuadEdge,
    mesh: Mesh<Endpoint>,
    polygon_vertices_positions: Vec<Vec<PolygonVertexPosition>>,
    right_side: QuadEdge,
    triangular_holes_indices: Vec<usize>,
}

impl<Endpoint: Clone> BoundaryEndpoints<Endpoint>
    for ConstrainedDelaunayTriangulation<Endpoint>
where
    for<'a> &'a Endpoint: Orient,
{
    fn get_boundary_endpoints(&self) -> Vec<&Endpoint> {
        debug_assert!(
            self.mesh.get_endpoints().len() >= MIN_CONTOUR_VERTICES_COUNT
        );
        let mut result = Vec::new();
        let start = self.left_side;
        let mut edge = start;
        loop {
            result.push(self.mesh.get_start(edge));
            let candidate = self.mesh.to_right_from_end(edge);
            if candidate == start {
                break;
            }
            edge = candidate;
        }
        shrink_collinear_vertices(&result)
    }
}

struct PolygonEndpoint<'a, Endpoint> {
    contour_index: usize,
    vertex_index: usize,
    point: &'a Endpoint,
}

impl<Endpoint: PartialEq> PartialEq for PolygonEndpoint<'_, Endpoint> {
    fn eq(&self, other: &Self) -> bool {
        debug_assert!(self.point.eq(other.point));
        self.contour_index.eq(&other.contour_index)
            && self.vertex_index.eq(&other.vertex_index)
    }
}

impl<Endpoint: PartialOrd> PartialOrd for PolygonEndpoint<'_, Endpoint> {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(match self.point.partial_cmp(other.point)? {
            Ordering::Equal => self.contour_index.cmp(&other.contour_index),
            value => value,
        })
    }
}

impl<Endpoint: Eq> Eq for PolygonEndpoint<'_, Endpoint> {}

impl<Endpoint: Ord> Ord for PolygonEndpoint<'_, Endpoint> {
    fn cmp(&self, other: &Self) -> Ordering {
        match self.point.cmp(other.point) {
            Ordering::Equal => self.contour_index.cmp(&other.contour_index),
            value => value,
        }
    }
}

#[derive(Clone, Copy, Debug)]
struct PolygonVertexPosition {
    contour_index: usize,
    vertex_index: usize,
}

impl<Contour, Endpoint: Clone + Ord + PartialOrd, Polygon> From<&Polygon>
    for ConstrainedDelaunayTriangulation<Endpoint>
where
    Mesh<Endpoint>: DelaunayTriangulatable,
    for<'a, 'b> &'a MultisegmentalIndexSegment<&'b Contour>: Segmental,
    for<'a, 'b> &'a MultivertexalIndexVertex<&'b Contour>: Elemental,
    for<'a, 'b> &'a PolygonalIndexHole<&'b Polygon>: Contoural,
    for<'a, 'b, 'c> &'a MultisegmentalIndexSegment<&'b PolygonalIndexHole<&'c Polygon>>:
        Segmental,
    for<'a, 'b, 'c> &'a MultivertexalIndexVertex<&'b PolygonalIndexHole<&'c Polygon>>:
        Elemental,
    for<'a> &'a Contour: Contoural<IndexVertex = Endpoint>,
    for<'a> &'a Endpoint: LocatePointInPointPointPointCircle + Orient,
    for<'a> &'a Polygon:
        Polygonal<Contour = &'a Contour, IntoIteratorHole = &'a Contour>,
{
    fn from(polygon: &Polygon) -> Self {
        let contours_vertices = {
            let holes = polygon.holes();
            let mut contours_vertices = Vec::with_capacity(1 + holes.len());
            contours_vertices.push(polygon.border().vertices());
            for hole in holes {
                contours_vertices.push(hole.vertices());
            }
            contours_vertices
        };
        let polygon_endpoints = {
            let mut polygon_endpoints = Vec::with_capacity(
                contours_vertices
                    .iter()
                    .map(|vertices| vertices.len())
                    .sum::<usize>(),
            );
            for (contour_index, contour_vertices) in
                contours_vertices.iter().enumerate()
            {
                polygon_endpoints.extend(
                    contour_vertices.iter().enumerate().map(
                        |(vertex_index, point)| PolygonEndpoint {
                            contour_index,
                            vertex_index,
                            point,
                        },
                    ),
                );
            }
            polygon_endpoints.sort();
            polygon_endpoints
        };
        let (polygon_vertices, polygon_vertices_positions) = {
            let mut polygon_vertices_positions =
                Vec::with_capacity(polygon_endpoints.len());
            let mut polygon_vertices =
                Vec::<Endpoint>::with_capacity(polygon_endpoints.len());
            let mut endpoint = &polygon_endpoints[0];
            polygon_vertices.push(endpoint.point.clone());
            polygon_vertices_positions.push(vec![PolygonVertexPosition {
                contour_index: endpoint.contour_index,
                vertex_index: endpoint.vertex_index,
            }]);
            let mut vertex_index = 0usize;
            for next_endpoint in &polygon_endpoints[1..] {
                if next_endpoint.point.eq(endpoint.point) {
                    polygon_vertices_positions[vertex_index].push(
                        PolygonVertexPosition {
                            contour_index: next_endpoint.contour_index,
                            vertex_index: next_endpoint.vertex_index,
                        },
                    );
                } else {
                    vertex_index += 1;
                    polygon_vertices.push(next_endpoint.point.clone());
                    polygon_vertices_positions.push(vec![
                        PolygonVertexPosition {
                            contour_index: next_endpoint.contour_index,
                            vertex_index: next_endpoint.vertex_index,
                        },
                    ]);
                    endpoint = next_endpoint;
                }
            }
            (polygon_vertices, polygon_vertices_positions)
        };
        let mut mesh = Mesh::from(polygon_vertices);
        let (left_side, right_side) = mesh.delaunay_triangulation();
        let triangular_holes_indices = contours_vertices[1..]
            .iter()
            .enumerate()
            .filter(|(_, hole_vertices)| hole_vertices.len() == 3)
            .map(|(hole_index, _)| hole_index + 1)
            .collect();
        let mut result = Self {
            left_side,
            mesh,
            polygon_vertices_positions,
            right_side,
            triangular_holes_indices,
        };
        let contours_sizes = contours_vertices
            .iter()
            .map(|contour| contour.len())
            .collect::<Vec<usize>>();
        result.constrain(&contours_sizes, &contours_vertices);
        result.bound(&contours_sizes);
        result.cut(&contours_vertices);
        result
    }
}

impl<Endpoint> ConstrainedDelaunayTriangulation<Endpoint> {
    pub(crate) fn is_empty(&self) -> bool {
        let result = self.mesh.is_empty();
        debug_assert_eq!(self.left_side == UNDEFINED_QUAD_EDGE, result);
        debug_assert_eq!(self.right_side == UNDEFINED_QUAD_EDGE, result);
        result
    }

    fn delete_edge(&mut self, edge: QuadEdge) {
        if edge == self.right_side || to_opposite_edge(edge) == self.right_side
        {
            self.right_side =
                to_opposite_edge(self.mesh.to_right_from_end(self.right_side));
        }
        if edge == self.left_side || to_opposite_edge(edge) == self.left_side {
            self.left_side = self.mesh.to_left_from_start(self.left_side);
        }
        self.mesh.delete_edge(edge);
    }

    fn to_unique_boundary_edges(&self) -> Vec<QuadEdge> {
        debug_assert!(!self.is_empty());
        let mut result = Vec::new();
        let start = self.left_side;
        let mut edge = start;
        loop {
            result.push(edge);
            let candidate = self.mesh.to_right_from_end(edge);
            if candidate == start {
                break;
            }
            edge = candidate;
        }
        result
    }
}

impl<Endpoint: PartialOrd> ConstrainedDelaunayTriangulation<Endpoint>
where
    for<'a> &'a Endpoint: Orient,
{
    pub(crate) fn to_triangles_vertices(
        &self,
    ) -> impl Iterator<Item = (&Endpoint, &Endpoint, &Endpoint)> + '_ {
        self.mesh
            .to_triangles_base_edges()
            .filter(move |&edge| {
                self.triangular_holes_indices.is_empty()
                    || !are_triangular_hole_vertices(
                        &self.polygon_vertices_positions
                            [self.mesh.to_start_index(edge)],
                        &self.polygon_vertices_positions
                            [self.mesh.to_end_index(edge)],
                        &self.polygon_vertices_positions[self
                            .mesh
                            .to_end_index(self.mesh.to_left_from_start(edge))],
                        &self.triangular_holes_indices,
                    )
            })
            .map(move |edge| self.mesh.triangle_base_to_vertices(edge))
    }
}

impl<Endpoint: PartialOrd> ConstrainedDelaunayTriangulation<Endpoint>
where
    for<'a> &'a Endpoint: LocatePointInPointPointPointCircle + Orient,
{
    fn bound(&mut self, contours_sizes: &[usize]) {
        let mut extraneous_mouths = self
            .to_unique_boundary_edges()
            .into_iter()
            .filter(|edge| {
                !is_polygon_edge(
                    &self.mesh,
                    *edge,
                    contours_sizes,
                    &self.polygon_vertices_positions,
                )
            })
            .collect::<Vec<QuadEdge>>();
        while let Some(mouth) = extraneous_mouths.pop() {
            let (first_candidate, second_candidate) =
                mouth_edge_to_incidents(&self.mesh, mouth);
            self.delete_edge(mouth);
            if !is_polygon_edge(
                &self.mesh,
                first_candidate,
                contours_sizes,
                &self.polygon_vertices_positions,
            ) {
                extraneous_mouths.push(first_candidate);
            }
            if !is_polygon_edge(
                &self.mesh,
                second_candidate,
                contours_sizes,
                &self.polygon_vertices_positions,
            ) {
                extraneous_mouths.push(second_candidate);
            }
        }
    }

    fn constrain<ContourVertices: Sequence<IndexItem = Endpoint>>(
        &mut self,
        contours_sizes: &[usize],
        contours_vertices: &[ContourVertices],
    ) {
        let mut contours_constraints_flags = to_contours_constraints_flags(
            &self.mesh,
            contours_sizes,
            &self.polygon_vertices_positions,
        );
        for edge in self.mesh.to_edges() {
            let start_index = self.mesh.to_start_index(edge);
            for &PolygonVertexPosition {
                contour_index,
                vertex_index,
            } in &self.polygon_vertices_positions[start_index]
            {
                let next_vertex_index =
                    (vertex_index + 1) % contours_sizes[contour_index];
                let constraint_index =
                    to_constraint_index(vertex_index, next_vertex_index);
                if !contours_constraints_flags[contour_index][constraint_index]
                {
                    let vertex_point =
                        &contours_vertices[contour_index][vertex_index];
                    let next_vertex_point =
                        &contours_vertices[contour_index][next_vertex_index];
                    let angle_base_edge = to_angle_containing_constraint_base(
                        &self.mesh,
                        edge,
                        next_vertex_point,
                    );
                    let crossings = detect_crossings(
                        &self.mesh,
                        angle_base_edge,
                        vertex_point,
                        next_vertex_point,
                    );
                    if !crossings.is_empty() {
                        set_constraint(
                            &mut self.mesh,
                            vertex_point,
                            next_vertex_point,
                            crossings,
                        );
                    }
                    contours_constraints_flags[contour_index]
                        [constraint_index] = true;
                }
            }
        }
    }

    fn cut<ContourVertices: Sequence<IndexItem = Endpoint>>(
        &mut self,
        contours_vertices: &[ContourVertices],
    ) {
        for edge in self.mesh.to_unique_edges() {
            if is_edge_inside_hole(
                &self.mesh,
                edge,
                contours_vertices,
                &self.polygon_vertices_positions,
            ) {
                self.delete_edge(edge);
            }
        }
    }
}

fn angle_contains_point<'a, Point>(
    vertex: &'a Point,
    first_ray_point: &'a Point,
    second_ray_point: &'a Point,
    angle_orientation: Orientation,
    point: &'a Point,
) -> bool
where
    &'a Point: Orient,
{
    debug_assert!(angle_orientation != Orientation::Collinear);
    let first_half_orientation = vertex.orient(first_ray_point, point);
    let second_half_orientation = second_ray_point.orient(vertex, point);
    (first_half_orientation == Orientation::Collinear
        || first_half_orientation == angle_orientation)
        && (second_half_orientation == Orientation::Collinear
            || second_half_orientation == angle_orientation)
}

fn are_polygon_edge_indices(
    first_vertex_index: usize,
    second_vertex_index: usize,
    contour_size: usize,
) -> bool {
    first_vertex_index.abs_diff(second_vertex_index) == 1
        || (first_vertex_index == 0 && second_vertex_index == contour_size - 1)
        || (first_vertex_index == contour_size - 1 && second_vertex_index == 0)
}

fn are_triangular_hole_vertices(
    first_positions: &[PolygonVertexPosition],
    second_positions: &[PolygonVertexPosition],
    third_positions: &[PolygonVertexPosition],
    triangular_holes_indices: &[usize],
) -> bool {
    first_positions
        .iter()
        .map(|position| position.contour_index)
        .filter(|contour_index| {
            second_positions
                .iter()
                .any(|position| position.contour_index.eq(contour_index))
                && third_positions
                    .iter()
                    .any(|position| position.contour_index.eq(contour_index))
        })
        .any(|contour_index| triangular_holes_indices.contains(&contour_index))
}

fn detect_crossings<Endpoint: PartialEq + PartialOrd>(
    mesh: &Mesh<Endpoint>,
    base_edge: QuadEdge,
    constraint_start: &Endpoint,
    constraint_end: &Endpoint,
) -> Vec<QuadEdge>
where
    for<'a> &'a Endpoint: Orient,
{
    let mut candidate = mesh.to_left_from_end(base_edge);
    let mut result = Vec::new();
    while mesh.get_start(candidate).ne(constraint_end) {
        let last_crossing = candidate;
        debug_assert_eq!(
            segment_endpoints::relate_to_segment_endpoints(
                (mesh.get_start(last_crossing), mesh.get_end(last_crossing)),
                (constraint_start, constraint_end)
            ),
            Relation::Cross
        );
        result.push(last_crossing);
        candidate = mesh.to_right_from_start(last_crossing);
        if mesh.orient_point_to_edge(candidate, constraint_end)
            != Orientation::Clockwise
            || constraint_start.orient(constraint_end, mesh.get_end(candidate))
                == Orientation::Clockwise
        {
            candidate =
                to_opposite_edge(mesh.to_right_from_end(last_crossing));
        }
    }
    result
}

fn edge_should_be_swapped<Endpoint>(
    mesh: &Mesh<Endpoint>,
    edge: QuadEdge,
) -> bool
where
    for<'a> &'a Endpoint: LocatePointInPointPointPointCircle + Orient,
{
    is_convex_quadrilateral_diagonal(mesh, edge)
        && ((mesh
            .get_end(mesh.to_right_from_start(edge))
            .locate_point_in_point_point_point_circle(
                mesh.get_start(edge),
                mesh.get_end(edge),
                mesh.get_end(mesh.to_left_from_start(edge)),
            )
            == Location::Interior)
            || (mesh
                .get_end(mesh.to_left_from_start(edge))
                .locate_point_in_point_point_point_circle(
                    mesh.get_end(edge),
                    mesh.get_start(edge),
                    mesh.get_end(mesh.to_right_from_start(edge)),
                )
                == Location::Interior))
}

fn intersect_polygon_vertices_positions_slices<const WITH_BORDER: bool>(
    left: &[PolygonVertexPosition],
    right: &[PolygonVertexPosition],
) -> Vec<(PolygonVertexPosition, PolygonVertexPosition)> {
    if left.len() < right.len() {
        intersect_polygon_vertices_positions_slices_impl::<true, WITH_BORDER>(
            left, right,
        )
    } else {
        intersect_polygon_vertices_positions_slices_impl::<false, WITH_BORDER>(
            right, left,
        )
    }
}

fn intersect_polygon_vertices_positions_slices_impl<
    const REVERSE: bool,
    const WITH_BORDER: bool,
>(
    shorter: &[PolygonVertexPosition],
    longer: &[PolygonVertexPosition],
) -> Vec<(PolygonVertexPosition, PolygonVertexPosition)> {
    debug_assert!(shorter.len() <= longer.len());
    let mut result = Vec::with_capacity(shorter.len());
    for shorter_position in shorter {
        if WITH_BORDER || shorter_position.contour_index != 0 {
            if let Some(longer_position) = longer.iter().find(|&candidate| {
                candidate.contour_index == shorter_position.contour_index
            }) {
                result.push(if REVERSE {
                    (*shorter_position, *longer_position)
                } else {
                    (*longer_position, *shorter_position)
                });
            }
        }
    }
    result
}

fn is_edge_inside_hole<
    Endpoint,
    ContourVertices: Sequence<IndexItem = Endpoint>,
>(
    mesh: &Mesh<Endpoint>,
    edge: QuadEdge,
    contours_vertices: &[ContourVertices],
    polygon_vertices_positions: &[Vec<PolygonVertexPosition>],
) -> bool
where
    for<'a> &'a Endpoint: Orient,
{
    let (start_index, end_index) =
        (mesh.to_start_index(edge), mesh.to_end_index(edge));
    debug_assert_ne!(start_index, end_index);
    let (start, end) = {
        let endpoints = mesh.get_endpoints();
        (&endpoints[start_index], &endpoints[end_index])
    };
    let edge_holes_positions_pairs =
        intersect_polygon_vertices_positions_slices::<false>(
            &polygon_vertices_positions[start_index],
            &polygon_vertices_positions[end_index],
        );
    debug_assert!(edge_holes_positions_pairs.len() <= 1);
    if let Some((start_hole_position, end_hole_position)) =
        edge_holes_positions_pairs.first()
    {
        debug_assert_eq!(
            start_hole_position.contour_index,
            end_hole_position.contour_index
        );
        debug_assert_ne!(
            start_hole_position.vertex_index,
            end_hole_position.vertex_index
        );
        let hole_vertices =
            &contours_vertices[start_hole_position.contour_index];
        let hole_size = hole_vertices.len();
        let start_vertex_index = start_hole_position.vertex_index;
        let end_vertex_index = end_hole_position.vertex_index;
        if are_polygon_edge_indices(
            start_vertex_index,
            end_vertex_index,
            hole_size,
        ) {
            return false;
        }
        let prior_to_start_point = &hole_vertices[if start_vertex_index == 0 {
            hole_size - 1
        } else {
            start_vertex_index - 1
        }];
        let prior_to_end_point = &hole_vertices[if end_vertex_index == 0 {
            hole_size - 1
        } else {
            end_vertex_index - 1
        }];
        let next_to_start_point =
            &hole_vertices[(start_vertex_index + 1) % hole_size];
        let next_to_end_point =
            &hole_vertices[(end_vertex_index + 1) % hole_size];
        let start_angle_orientation =
            start.orient(prior_to_start_point, next_to_start_point);
        let end_angle_orientation =
            end.orient(prior_to_end_point, next_to_end_point);
        if ((end_angle_orientation == Orientation::Counterclockwise)
            == angle_contains_point(
                end,
                prior_to_end_point,
                next_to_end_point,
                end_angle_orientation,
                start,
            ))
            && ((start_angle_orientation == Orientation::Counterclockwise)
                == angle_contains_point(
                    start,
                    prior_to_start_point,
                    next_to_start_point,
                    start_angle_orientation,
                    end,
                ))
        {
            return true;
        }
    }
    false
}

fn is_convex_quadrilateral_diagonal<Endpoint>(
    mesh: &Mesh<Endpoint>,
    edge: QuadEdge,
) -> bool
where
    for<'a> &'a Endpoint: Orient,
{
    mesh.orient_point_to_edge(
        mesh.to_left_from_end(edge),
        mesh.get_start(edge),
    ) == Orientation::Counterclockwise
        && mesh.orient_point_to_edge(
            mesh.to_right_from_start(edge),
            mesh.get_end(edge),
        ) == Orientation::Counterclockwise
        && mesh.orient_point_to_edge(
            to_opposite_edge(mesh.to_right_from_end(edge)),
            mesh.get_end(mesh.to_left_from_start(edge)),
        ) == Orientation::Counterclockwise
        && mesh.orient_point_to_edge(
            to_opposite_edge(mesh.to_left_from_start(edge)),
            mesh.get_end(mesh.to_right_from_start(edge)),
        ) == Orientation::Counterclockwise
}

fn is_polygon_edge<Endpoint>(
    mesh: &Mesh<Endpoint>,
    edge: QuadEdge,
    contours_sizes: &[usize],
    polygon_vertices_positions: &[Vec<PolygonVertexPosition>],
) -> bool {
    intersect_polygon_vertices_positions_slices::<true>(
        &polygon_vertices_positions[mesh.to_start_index(edge)],
        &polygon_vertices_positions[mesh.to_end_index(edge)],
    )
    .into_iter()
    .all(|(start_position, end_position)| {
        are_polygon_edge_indices(
            start_position.vertex_index,
            end_position.vertex_index,
            contours_sizes[start_position.contour_index],
        )
    })
}

fn mouth_edge_to_incidents<Endpoint>(
    mesh: &Mesh<Endpoint>,
    edge: QuadEdge,
) -> (QuadEdge, QuadEdge) {
    let left_from_start = mesh.to_left_from_start(edge);
    (left_from_start, mesh.to_right_from_end(left_from_start))
}

fn resolve_crossings<Endpoint: PartialOrd>(
    mesh: &mut Mesh<Endpoint>,
    crossings: Vec<QuadEdge>,
    constraint_start: &Endpoint,
    constraint_end: &Endpoint,
) -> Vec<QuadEdge>
where
    for<'a> &'a Endpoint: Orient,
{
    let mut result = Vec::with_capacity(crossings.len());
    let mut crossings_queue = VecDeque::from(crossings);
    while let Some(edge) = crossings_queue.pop_back() {
        if is_convex_quadrilateral_diagonal(mesh, edge) {
            mesh.swap_diagonal(edge);
            match segment_endpoints::relate_to_segment_endpoints(
                (mesh.get_start(edge), mesh.get_end(edge)),
                (constraint_start, constraint_end),
            ) {
                Relation::Cross => crossings_queue.push_front(edge),
                Relation::Equal => {}
                _ => result.push(edge),
            }
        } else {
            crossings_queue.push_front(edge);
        }
    }
    result
}

fn set_constraint<Endpoint: PartialOrd>(
    mesh: &mut Mesh<Endpoint>,
    constraint_start: &Endpoint,
    constraint_end: &Endpoint,
    crossings: Vec<QuadEdge>,
) where
    for<'a> &'a Endpoint: LocatePointInPointPointPointCircle + Orient,
{
    let new_edges =
        resolve_crossings(mesh, crossings, constraint_start, constraint_end);
    set_criterion(mesh, new_edges);
}

fn set_criterion<Endpoint>(
    mesh: &mut Mesh<Endpoint>,
    mut candidates: Vec<QuadEdge>,
) where
    for<'a> &'a Endpoint: LocatePointInPointPointPointCircle + Orient,
{
    loop {
        let mut next_target_edges = Vec::with_capacity(candidates.capacity());
        let mut edges_to_swap = Vec::with_capacity(candidates.capacity());
        for edge in candidates {
            if edge_should_be_swapped(mesh, edge) {
                edges_to_swap.push(edge);
            } else {
                next_target_edges.push(edge);
            }
        }
        if edges_to_swap.is_empty() {
            break;
        }
        for edge in edges_to_swap {
            mesh.swap_diagonal(edge);
        }
        candidates = next_target_edges;
    }
}

fn to_angle_containing_constraint_base<Endpoint: PartialEq>(
    mesh: &Mesh<Endpoint>,
    mut edge: QuadEdge,
    constraint_end: &Endpoint,
) -> QuadEdge
where
    for<'a> &'a Endpoint: Orient,
{
    if mesh.get_end(edge).ne(constraint_end) {
        let mut orientation = mesh.orient_point_to_edge(edge, constraint_end);
        if orientation == Orientation::Counterclockwise {
            loop {
                let candidate = mesh.to_left_from_start(edge);
                orientation =
                    mesh.orient_point_to_edge(candidate, constraint_end);
                if orientation == Orientation::Clockwise {
                    break;
                }
                edge = candidate;
            }
        } else {
            loop {
                edge = mesh.to_right_from_start(edge);
                orientation = mesh.orient_point_to_edge(edge, constraint_end);
                if orientation != Orientation::Clockwise {
                    break;
                }
            }
        }
    }
    edge
}

fn to_constraint_index(
    first_vertex_index: usize,
    second_vertex_index: usize,
) -> usize {
    if first_vertex_index.abs_diff(second_vertex_index) == 1 {
        first_vertex_index.max(second_vertex_index)
    } else {
        0
    }
}

fn to_contours_constraints_flags<Endpoint>(
    mesh: &Mesh<Endpoint>,
    contours_sizes: &[usize],
    polygon_vertices_positions: &[Vec<PolygonVertexPosition>],
) -> Vec<Vec<bool>> {
    let mut are_constraints_satisfied: Vec<Vec<bool>> = contours_sizes
        .iter()
        .map(|contour_size| vec![false; *contour_size])
        .collect();
    for edge in mesh.iter_unique_edges() {
        for (start_position, end_position) in
            intersect_polygon_vertices_positions_slices::<true>(
                &polygon_vertices_positions[mesh.to_start_index(edge)],
                &polygon_vertices_positions[mesh.to_end_index(edge)],
            )
        {
            debug_assert_eq!(
                start_position.contour_index,
                end_position.contour_index
            );
            let contour_index = start_position.contour_index;
            let start_index = start_position.vertex_index;
            let end_index = end_position.vertex_index;
            if are_polygon_edge_indices(
                start_index,
                end_index,
                contours_sizes[contour_index],
            ) {
                are_constraints_satisfied[contour_index]
                    [to_constraint_index(start_index, end_index)] = true;
            }
        }
    }
    are_constraints_satisfied
}
