boostvoronoi 0.12.1

// todo: regenerate the test data with better precision
use boostvoronoi::prelude as BV;
use boostvoronoi::prelude::*;

mod common;
use approx::abs_diff_eq;
use common::{to_points, to_segments};

type I = i32;

pub fn almost_equal(x1: f64, x2: f64, y1: f64, y2: f64) -> bool {
    let epsilon = 0.0001;
    abs_diff_eq!(x1, x2, epsilon = epsilon) && abs_diff_eq!(y1, y2, epsilon = epsilon)
}

fn retrieve_point<T: InputType>(
    point_data_: &[Point<T>],
    segment_data_: &[Line<T>],
    source: (BV::SourceIndex, SourceCategory),
) -> Point<T> {
    let source_index: usize = source.0.usize();
    match source.1 {
        SourceCategory::SinglePoint => point_data_[source_index],
        SourceCategory::SegmentStart => segment_data_[source_index - point_data_.len()].start,
        SourceCategory::Segment | SourceCategory::SegmentEnd => {
            segment_data_[source_index - point_data_.len()].end
        }
    }
}

#[test]
fn single_segment_1() -> Result<(), BvError> {
    let output = {
        let _s = [Line::<I>::new(
            Point { x: 10, y: 10 },
            Point { x: 50, y: 50 },
        )];
        Builder::<I>::default().with_segments(_s.iter())?.build()?
    };
    // results verified against c++ boost
    assert_eq!(output.cells().len(), 3);
    let cell = output.cells()[0];
    assert_eq!(cell.id(), 0);
    assert_eq!(cell.source_index(), 0);
    let cell = output.cells()[1];
    assert_eq!(cell.id(), 1);
    assert_eq!(cell.source_index(), 0);
    let cell = output.cells()[2];
    assert_eq!(cell.id(), 2);
    assert_eq!(cell.source_index(), 0);
    assert_eq!(output.vertices().len(), 0);
    assert_eq!(output.edges().len(), 4);
    assert_eq!(output.edges().first().unwrap().cell()?, 0);
    assert!(output.edges().first().unwrap().vertex0().is_none());
    assert_eq!(output.edges().first().unwrap().twin()?, 1);
    assert_eq!(output.edges().first().unwrap().next()?, 0);
    assert_eq!(output.edges().first().unwrap().prev()?, 0);
    assert_eq!(output.edges().get(1).unwrap().cell()?, 1);
    assert!(output.edges().get(1).unwrap().vertex0().is_none());
    assert_eq!(output.edges().get(1).unwrap().twin()?, 0);
    assert_eq!(output.edges().get(1).unwrap().next()?, 2);
    assert_eq!(output.edges().get(1).unwrap().prev()?, 2);
    assert_eq!(output.edges().get(2).unwrap().cell()?, 1);
    assert!(output.edges().get(2).unwrap().vertex0().is_none());
    assert_eq!(output.edges().get(2).unwrap().twin()?, 3);
    assert_eq!(output.edges().get(2).unwrap().next()?, 1);
    assert_eq!(output.edges().get(2).unwrap().prev()?, 1);
    assert_eq!(output.edges().get(3).unwrap().cell()?, 2);
    assert!(output.edges().get(3).unwrap().vertex0().is_none());
    assert_eq!(output.edges().get(3).unwrap().twin()?, 2);
    assert_eq!(output.edges().get(3).unwrap().next()?, 3);
    assert_eq!(output.edges().get(3).unwrap().prev()?, 3);
    assert_eq!(output.edges().get(3).unwrap().next()?, 3);
    assert_eq!(output.edges().get(3).unwrap().prev()?, 3);
    Ok(())
}

#[test]
fn single_segment_2() -> Result<(), BvError> {
    let output = {
        let _s = [Line::new(Point { x: 10, y: 10 }, Point { x: 50, y: 50 })];
        Builder::<I>::default().with_segments(_s.iter())?.build()?
    };
    assert_eq!(output.cells().len(), 3);
    let cell = output.cells()[0];
    assert_eq!(cell.id(), 0);
    assert_eq!(cell.source_index(), 0);
    let cell = output.cells()[1];
    assert_eq!(cell.id(), 1);
    assert_eq!(cell.source_index(), 0);
    let cell = output.cells()[2];
    assert_eq!(cell.id(), 2);
    assert_eq!(cell.source_index(), 0);
    assert_eq!(output.vertices().len(), 0);
    assert_eq!(output.edges().len(), 4);
    assert_eq!(output.edges().first().unwrap().cell()?, 0);
    assert!(output.edges().first().unwrap().vertex0().is_none());
    assert_eq!(output.edges().first().unwrap().twin()?, 1);
    assert_eq!(output.edges().first().unwrap().next()?, 0);
    assert_eq!(output.edges().first().unwrap().prev()?, 0);
    assert_eq!(output.edges().get(1).unwrap().cell()?, 1);
    assert!(output.edges().get(1).unwrap().vertex0().is_none());
    assert_eq!(output.edges().get(1).unwrap().twin()?, 0);
    assert_eq!(output.edges().get(1).unwrap().next()?, 2);
    assert_eq!(output.edges().get(1).unwrap().prev()?, 2);
    assert_eq!(output.edges().get(2).unwrap().cell()?, 1);
    assert!(output.edges().get(2).unwrap().vertex0().is_none());
    assert_eq!(output.edges().get(2).unwrap().twin()?, 3);
    assert_eq!(output.edges().get(2).unwrap().next()?, 1);
    assert_eq!(output.edges().get(2).unwrap().prev()?, 1);
    assert_eq!(output.edges().get(3).unwrap().cell()?, 2);
    assert!(output.edges().get(3).unwrap().vertex0().is_none());
    assert_eq!(output.edges().get(3).unwrap().twin()?, 2);
    assert_eq!(output.edges().get(3).unwrap().next()?, 3);
    assert_eq!(output.edges().get(3).unwrap().prev()?, 3);
    Ok(())
}

#[test]
fn single_segment_3() -> Result<(), BvError> {
    let output = {
        let _s = [Line::new(Point { x: 10, y: 10 }, Point { x: 50, y: 10 })];
        Builder::<I>::default().with_segments(_s.iter())?.build()?
    };
    assert_eq!(output.cells().len(), 3);
    let cell = output.cells()[0];
    assert_eq!(cell.id(), 0);
    assert_eq!(cell.source_index(), 0);
    let cell = output.cells()[1];
    assert_eq!(cell.id(), 1);
    assert_eq!(cell.source_index(), 0);
    let cell = output.cells()[2];
    assert_eq!(cell.id(), 2);
    assert_eq!(cell.source_index(), 0);
    assert_eq!(output.vertices().len(), 0);
    assert_eq!(output.edges().len(), 4);
    assert_eq!(output.edges().first().unwrap().cell()?, 0);
    assert!(output.edges().first().unwrap().vertex0().is_none());
    assert_eq!(output.edges().first().unwrap().twin()?, 1);
    assert_eq!(output.edges().first().unwrap().next()?, 0);
    assert_eq!(output.edges().first().unwrap().prev()?, 0);
    assert_eq!(output.edges().get(1).unwrap().cell()?, 1);
    assert!(output.edges().get(1).unwrap().vertex0().is_none());
    assert_eq!(output.edges().get(1).unwrap().twin()?, 0);
    assert_eq!(output.edges().get(1).unwrap().next()?, 2);
    assert_eq!(output.edges().get(1).unwrap().prev()?, 2);
    assert_eq!(output.edges().get(2).unwrap().cell()?, 1);
    assert!(output.edges().get(2).unwrap().vertex0().is_none());
    assert_eq!(output.edges().get(2).unwrap().twin()?, 3);
    assert_eq!(output.edges().get(2).unwrap().next()?, 1);
    assert_eq!(output.edges().get(2).unwrap().prev()?, 1);
    assert_eq!(output.edges().get(3).unwrap().cell()?, 2);
    assert!(output.edges().get(3).unwrap().vertex0().is_none());
    assert_eq!(output.edges().get(3).unwrap().twin()?, 2);
    assert_eq!(output.edges().get(3).unwrap().next()?, 3);
    assert_eq!(output.edges().get(3).unwrap().prev()?, 3);
    Ok(())
}

#[test]
fn single_segment_4() -> Result<(), BvError> {
    let output = {
        let _s = [Line::new(Point { x: 50, y: 10 }, Point { x: 10, y: 10 })];
        Builder::<I>::default().with_segments(_s.iter())?.build()?
    };
    assert_eq!(output.cells().len(), 3);
    let cell = output.cells()[0];
    assert_eq!(cell.id(), 0);
    assert_eq!(cell.source_index(), 0);
    let cell = output.cells()[1];
    assert_eq!(cell.id(), 1);
    assert_eq!(cell.source_index(), 0);
    let cell = output.cells()[2];
    assert_eq!(cell.id(), 2);
    assert_eq!(cell.source_index(), 0);
    assert_eq!(output.vertices().len(), 0);
    assert_eq!(output.edges().len(), 4);
    assert_eq!(output.edges().first().unwrap().cell()?, 0);
    assert!(output.edges().first().unwrap().vertex0().is_none());
    assert_eq!(output.edges().first().unwrap().twin()?, 1);
    assert_eq!(output.edges().first().unwrap().next()?, 0);
    assert_eq!(output.edges().first().unwrap().prev()?, 0);
    assert_eq!(output.edges().get(1).unwrap().cell()?, 1);
    assert!(output.edges().get(1).unwrap().vertex0().is_none());
    assert_eq!(output.edges().get(1).unwrap().twin()?, 0);
    assert_eq!(output.edges().get(1).unwrap().next()?, 2);
    assert_eq!(output.edges().get(1).unwrap().prev()?, 2);
    assert_eq!(output.edges().get(2).unwrap().cell()?, 1);
    assert!(output.edges().get(2).unwrap().vertex0().is_none());
    assert_eq!(output.edges().get(2).unwrap().twin()?, 3);
    assert_eq!(output.edges().get(2).unwrap().next()?, 1);
    assert_eq!(output.edges().get(2).unwrap().prev()?, 1);
    assert_eq!(output.edges().get(3).unwrap().cell()?, 2);
    assert!(output.edges().get(3).unwrap().vertex0().is_none());
    assert_eq!(output.edges().get(3).unwrap().twin()?, 2);
    assert_eq!(output.edges().get(3).unwrap().next()?, 3);
    assert_eq!(output.edges().get(3).unwrap().prev()?, 3);
    Ok(())
}

#[test]
///Two segments
fn two_segments_1() -> Result<(), BvError> {
    let output = {
        let _s = [
            Line::new(Point { x: 1, y: 2 }, Point { x: 3, y: 4 }),
            Line::new(Point { x: 2, y: 2 }, Point { x: 5, y: 4 }),
        ];
        Builder::<I>::default().with_segments(_s.iter())?.build()?
    };
    assert_eq!(output.cells().len(), 6);
    let cell = output.cells()[0];
    assert_eq!(cell.id(), 0);
    assert_eq!(cell.source_index(), 0);
    //assert_eq!(cell.source_category().0, 1);
    assert!(cell.contains_point());
    assert!(!cell.contains_segment());
    let cell = output.cells()[1];
    assert_eq!(cell.id(), 1);
    assert_eq!(cell.source_index(), 0);
    //assert_eq!(cell.source_category().0, 8);
    assert!(!cell.contains_point());
    assert!(cell.contains_segment());
    let cell = output.cells()[2];
    assert_eq!(cell.id(), 2);
    assert_eq!(cell.source_index(), 1);
    //assert_eq!(cell.source_category().0, 1);
    assert!(cell.contains_point());
    assert!(!cell.contains_segment());
    let cell = output.cells()[3];
    assert_eq!(cell.id(), 3);
    assert_eq!(cell.source_index(), 1);
    //assert_eq!(cell.source_category().0, 8);
    assert!(!cell.contains_point());
    assert!(cell.contains_segment());
    let cell = output.cells()[4];
    assert_eq!(cell.id(), 4);
    assert_eq!(cell.source_index(), 0);
    //assert_eq!(cell.source_category().0, 2);
    assert!(cell.contains_point());
    assert!(!cell.contains_segment());
    let cell = output.cells()[5];
    assert_eq!(cell.id(), 5);
    assert_eq!(cell.source_index(), 1);
    //assert_eq!(cell.source_category().0, 2);
    assert!(cell.contains_point());
    assert!(!cell.contains_segment());
    assert_eq!(output.vertices().len(), 4);
    assert_eq!(output.edges().len(), 18);
    let v = output.vertices()[0];
    assert!(almost_equal(v.x(), 1.80196, v.y(), 2.29706));
    let v = output.vertices()[1];
    assert!(almost_equal(v.x(), 1.5, v.y(), 1.5));
    let v = output.vertices()[2];
    assert!(almost_equal(v.x(), 3.39608, v.y(), 3.60392));
    let v = output.vertices()[3];
    assert!(almost_equal(v.x(), 4.0, v.y(), 5.5));
    assert_eq!(output.edges().first().unwrap().cell()?, 0);
    assert_eq!(output.edges().first().unwrap().vertex0().unwrap(), 1);
    assert_eq!(output.edges().first().unwrap().twin()?, 1);
    assert_eq!(output.edges().first().unwrap().next()?, 8);
    assert_eq!(output.edges().first().unwrap().prev()?, 8);
    assert_eq!(output.edges().get(1).unwrap().cell()?, 1);
    assert!(output.edges().get(1).unwrap().vertex0().is_none());
    assert_eq!(output.edges().get(1).unwrap().twin()?, 0);
    assert_eq!(output.edges().get(1).unwrap().next()?, 2);
    assert_eq!(output.edges().get(1).unwrap().prev()?, 10);
    assert_eq!(output.edges().get(2).unwrap().cell()?, 1);
    assert_eq!(output.edges().get(2).unwrap().vertex0().unwrap(), 1);
    assert_eq!(output.edges().get(2).unwrap().twin()?, 3);
    assert_eq!(output.edges().get(2).unwrap().next()?, 7);
    assert_eq!(output.edges().get(2).unwrap().prev()?, 1);
    assert_eq!(output.edges().get(3).unwrap().cell()?, 2);
    assert_eq!(output.edges().get(3).unwrap().vertex0().unwrap(), 0);
    assert_eq!(output.edges().get(3).unwrap().twin()?, 2);
    assert_eq!(output.edges().get(3).unwrap().next()?, 9);
    assert_eq!(output.edges().get(3).unwrap().prev()?, 4);
    assert_eq!(output.edges().get(4).unwrap().cell()?, 2);
    assert!(output.edges().get(4).unwrap().vertex0().is_none());
    assert_eq!(output.edges().get(4).unwrap().twin()?, 5);
    assert_eq!(output.edges().get(4).unwrap().next()?, 3);
    assert_eq!(output.edges().get(4).unwrap().prev()?, 9);
    assert_eq!(output.edges().get(5).unwrap().cell()?, 3);
    assert_eq!(output.edges().get(5).unwrap().vertex0().unwrap(), 0);
    assert_eq!(output.edges().get(5).unwrap().twin()?, 4);
    assert_eq!(output.edges().get(5).unwrap().next()?, 14);
    assert_eq!(output.edges().get(5).unwrap().prev()?, 6);
    assert_eq!(output.edges().get(6).unwrap().cell()?, 3);
    assert_eq!(output.edges().get(6).unwrap().vertex0().unwrap(), 2);
    assert_eq!(output.edges().get(6).unwrap().twin()?, 7);
    assert_eq!(output.edges().get(6).unwrap().next()?, 5);
    assert_eq!(output.edges().get(6).unwrap().prev()?, 12);
    assert_eq!(output.edges().get(7).unwrap().cell()?, 1);
    assert_eq!(output.edges().get(7).unwrap().vertex0().unwrap(), 0);
    assert_eq!(output.edges().get(7).unwrap().twin()?, 6);
    assert_eq!(output.edges().get(7).unwrap().next()?, 10);
    assert_eq!(output.edges().get(7).unwrap().prev()?, 2);
    assert_eq!(output.edges().get(8).unwrap().cell()?, 0);
    assert!(output.edges().get(8).unwrap().vertex0().is_none());
    assert_eq!(output.edges().get(8).unwrap().twin()?, 9);
    assert_eq!(output.edges().get(8).unwrap().next()?, 0);
    assert_eq!(output.edges().get(8).unwrap().prev()?, 0);
    assert_eq!(output.edges().get(9).unwrap().cell()?, 2);
    assert_eq!(output.edges().get(9).unwrap().vertex0().unwrap(), 1);
    assert_eq!(output.edges().get(9).unwrap().twin()?, 8);
    assert_eq!(output.edges().get(9).unwrap().next()?, 4);
    assert_eq!(output.edges().get(9).unwrap().prev()?, 3);
    assert_eq!(output.edges().get(10).unwrap().cell()?, 1);
    assert_eq!(output.edges().get(10).unwrap().vertex0().unwrap(), 2);
    assert_eq!(output.edges().get(10).unwrap().twin()?, 11);
    assert_eq!(output.edges().get(10).unwrap().next()?, 1);
    assert_eq!(output.edges().get(10).unwrap().prev()?, 7);
    assert_eq!(output.edges().get(11).unwrap().cell()?, 4);
    assert!(output.edges().get(11).unwrap().vertex0().is_none());
    assert_eq!(output.edges().get(11).unwrap().twin()?, 10);
    assert_eq!(output.edges().get(11).unwrap().next()?, 13);
    assert_eq!(output.edges().get(11).unwrap().prev()?, 17);
    assert_eq!(output.edges().get(12).unwrap().cell()?, 3);
    assert_eq!(output.edges().get(12).unwrap().vertex0().unwrap(), 3);
    assert_eq!(output.edges().get(12).unwrap().twin()?, 13);
    assert_eq!(output.edges().get(12).unwrap().next()?, 6);
    assert_eq!(output.edges().get(12).unwrap().prev()?, 14);
    assert_eq!(output.edges().get(13).unwrap().cell()?, 4);
    assert_eq!(output.edges().get(13).unwrap().vertex0().unwrap(), 2);
    assert_eq!(output.edges().get(13).unwrap().twin()?, 12);
    assert_eq!(output.edges().get(13).unwrap().next()?, 17);
    assert_eq!(output.edges().get(13).unwrap().prev()?, 11);
    assert_eq!(output.edges().get(14).unwrap().cell()?, 3);
    assert!(output.edges().get(14).unwrap().vertex0().is_none());
    assert_eq!(output.edges().get(14).unwrap().twin()?, 15);
    assert_eq!(output.edges().get(14).unwrap().next()?, 12);
    assert_eq!(output.edges().get(14).unwrap().prev()?, 5);
    assert_eq!(output.edges().get(15).unwrap().cell()?, 5);
    assert_eq!(output.edges().get(15).unwrap().vertex0().unwrap(), 3);
    assert_eq!(output.edges().get(15).unwrap().twin()?, 14);
    assert_eq!(output.edges().get(15).unwrap().next()?, 16);
    assert_eq!(output.edges().get(15).unwrap().prev()?, 16);
    assert_eq!(output.edges().get(16).unwrap().cell()?, 5);
    assert!(output.edges().get(16).unwrap().vertex0().is_none());
    assert_eq!(output.edges().get(16).unwrap().twin()?, 17);
    assert_eq!(output.edges().get(16).unwrap().next()?, 15);
    assert_eq!(output.edges().get(16).unwrap().prev()?, 15);
    assert_eq!(output.edges().get(17).unwrap().cell()?, 4);
    assert_eq!(output.edges().get(17).unwrap().vertex0().unwrap(), 3);
    assert_eq!(output.edges().get(17).unwrap().twin()?, 16);
    assert_eq!(output.edges().get(17).unwrap().next()?, 11);
    assert_eq!(output.edges().get(17).unwrap().prev()?, 13);
    Ok(())
}

#[test]
/// two segments and one point
fn two_segments_2() -> Result<(), BvError> {
    let output = {
        let _v = [Point { x: 10, y: 11 }];
        let _s = [
            Line::new(Point { x: 1, y: 2 }, Point { x: 3, y: 4 }),
            Line::new(Point { x: 2, y: 2 }, Point { x: 5, y: 4 }),
        ];
        Builder::<I>::default()
            .with_vertices(_v.iter())?
            .with_segments(_s.iter())?
            .build()?
    };
    assert_eq!(output.cells().len(), 7);
    let cell = output.cells()[0];
    assert_eq!(cell.id(), 0);
    assert_eq!(cell.source_index(), 1);
    assert!(!cell.is_degenerate());
    assert!(cell.contains_point());
    assert!(!cell.contains_segment());
    let cell = output.cells()[1];
    assert_eq!(cell.id(), 1);
    assert_eq!(cell.source_index(), 1);
    assert!(!cell.is_degenerate());
    assert!(!cell.contains_point());
    assert!(cell.contains_segment());
    let cell = output.cells()[2];
    assert_eq!(cell.id(), 2);
    assert_eq!(cell.source_index(), 2);
    assert!(!cell.is_degenerate());
    assert!(cell.contains_point());
    assert!(!cell.contains_segment());
    let cell = output.cells()[3];
    assert_eq!(cell.id(), 3);
    assert_eq!(cell.source_index(), 2);
    assert!(!cell.is_degenerate());
    assert!(!cell.contains_point());
    assert!(cell.contains_segment());
    let cell = output.cells()[4];
    assert_eq!(cell.id(), 4);
    assert_eq!(cell.source_index(), 1);
    assert!(!cell.is_degenerate());
    assert!(cell.contains_point());
    assert!(!cell.contains_segment());
    let cell = output.cells()[5];
    assert_eq!(cell.id(), 5);
    assert_eq!(cell.source_index(), 2);
    assert!(!cell.is_degenerate());
    assert!(cell.contains_point());
    assert!(!cell.contains_segment());
    let cell = output.cells()[6];
    assert_eq!(cell.id(), 6);
    assert_eq!(cell.source_index(), 0);
    assert!(!cell.is_degenerate());
    assert!(cell.contains_point());
    assert!(!cell.contains_segment());
    assert_eq!(output.vertices().len(), 5);
    assert_eq!(output.edges().len(), 22);
    let v = output.vertices()[0];
    assert!(almost_equal(v.x(), 1.80196, v.y(), 2.29706));
    assert_eq!(v.get_incident_edge()?, 7);
    let v = output.vertices()[1];
    assert!(almost_equal(v.x(), 1.50000, v.y(), 1.50000));
    assert_eq!(v.get_incident_edge()?, 9);
    let v = output.vertices()[2];
    assert!(almost_equal(v.x(), 3.39608, v.y(), 3.60392));
    assert_eq!(v.get_incident_edge()?, 13);
    let v = output.vertices()[3];
    assert!(almost_equal(v.x(), 4.00000, v.y(), 5.50000));
    assert_eq!(v.get_incident_edge()?, 17);
    let v = output.vertices()[4];
    assert!(almost_equal(v.x(), 4.00000, v.y(), 10.0000));
    assert_eq!(v.get_incident_edge()?, 21);
    assert_eq!(output.edges().first().unwrap().cell()?, 0);
    assert_eq!(output.edges().first().unwrap().vertex0().unwrap(), 1);
    assert_eq!(output.edges().first().unwrap().twin()?, 1);
    assert_eq!(output.edges().first().unwrap().next()?, 8);
    assert_eq!(output.edges().first().unwrap().prev()?, 8);
    let e = output.edges()[0];
    assert!(output.edge_get_vertex1(e.id())?.is_none());
    assert_eq!(output.edge_rot_next(e.id()).unwrap(), 9);
    assert!(!output.edge_is_finite(e.id())?);
    assert!(output.edge_is_infinite(e.id())?);
    assert!(e.is_linear());
    assert!(!e.is_curved());
    assert!(!e.is_primary());
    assert!(e.is_secondary());
    assert_eq!(output.edges().get(1).unwrap().cell()?, 1);
    assert!(output.edges().get(1).unwrap().vertex0().is_none());
    assert_eq!(output.edges().get(1).unwrap().twin()?, 0);
    assert_eq!(output.edges().get(1).unwrap().next()?, 2);
    assert_eq!(output.edges().get(1).unwrap().prev()?, 10);
    let e = output.edges()[1];
    assert_eq!(output.edge_get_vertex1(e.id())?.unwrap(), 1);
    assert_eq!(output.edge_rot_next(e.id()).unwrap(), 11);
    assert!(!output.edge_is_finite(e.id())?);
    assert!(output.edge_is_infinite(e.id())?);
    assert!(e.is_linear());
    assert!(!e.is_curved());
    assert!(!e.is_primary());
    assert!(e.is_secondary());
    assert_eq!(output.edges().get(2).unwrap().cell()?, 1);
    assert_eq!(output.edges().get(2).unwrap().vertex0().unwrap(), 1);
    assert_eq!(output.edges().get(2).unwrap().twin()?, 3);
    assert_eq!(output.edges().get(2).unwrap().next()?, 7);
    assert_eq!(output.edges().get(2).unwrap().prev()?, 1);
    let e = output.edges()[2];
    assert_eq!(output.edge_get_vertex1(e.id())?.unwrap(), 0);
    assert_eq!(output.edge_rot_next(e.id()).unwrap(), 0);
    assert!(output.edge_is_finite(e.id())?);
    assert!(!output.edge_is_infinite(e.id())?);
    assert!(!e.is_linear());
    assert!(e.is_curved());
    assert!(e.is_primary());
    assert!(!e.is_secondary());
    assert_eq!(output.edges().get(3).unwrap().cell()?, 2);
    assert_eq!(output.edges().get(3).unwrap().vertex0().unwrap(), 0);
    assert_eq!(output.edges().get(3).unwrap().twin()?, 2);
    assert_eq!(output.edges().get(3).unwrap().next()?, 9);
    assert_eq!(output.edges().get(3).unwrap().prev()?, 4);
    let e = output.edges()[3];
    assert_eq!(output.edge_get_vertex1(e.id())?.unwrap(), 1);
    assert_eq!(output.edge_rot_next(e.id()).unwrap(), 5);
    assert!(output.edge_is_finite(e.id())?);
    assert!(!output.edge_is_infinite(e.id())?);
    assert!(!e.is_linear());
    assert!(e.is_curved());
    assert!(e.is_primary());
    assert!(!e.is_secondary());
    assert_eq!(output.edges().get(4).unwrap().cell()?, 2);
    assert!(output.edges().get(4).unwrap().vertex0().is_none());
    assert_eq!(output.edges().get(4).unwrap().twin()?, 5);
    assert_eq!(output.edges().get(4).unwrap().next()?, 3);
    assert_eq!(output.edges().get(4).unwrap().prev()?, 9);
    let e = output.edges()[4];
    assert_eq!(output.edge_get_vertex1(e.id())?.unwrap(), 0);
    assert_eq!(output.edge_rot_next(e.id()).unwrap(), 8);
    assert!(!output.edge_is_finite(e.id())?);
    assert!(output.edge_is_infinite(e.id())?);
    assert!(e.is_linear());
    assert!(!e.is_curved());
    assert!(!e.is_primary());
    assert!(e.is_secondary());
    assert_eq!(output.edges().get(5).unwrap().cell()?, 3);
    assert_eq!(output.edges().get(5).unwrap().vertex0().unwrap(), 0);
    assert_eq!(output.edges().get(5).unwrap().twin()?, 4);
    assert_eq!(output.edges().get(5).unwrap().next()?, 14);
    assert_eq!(output.edges().get(5).unwrap().prev()?, 6);
    let e = output.edges()[5];
    assert!(output.edge_get_vertex1(e.id())?.is_none());
    assert_eq!(output.edge_rot_next(e.id()).unwrap(), 7);
    assert!(!output.edge_is_finite(e.id())?);
    assert!(output.edge_is_infinite(e.id())?);
    assert!(e.is_linear());
    assert!(!e.is_curved());
    assert!(!e.is_primary());
    assert!(e.is_secondary());
    assert_eq!(output.edges().get(6).unwrap().cell()?, 3);
    assert_eq!(output.edges().get(6).unwrap().vertex0().unwrap(), 2);
    assert_eq!(output.edges().get(6).unwrap().twin()?, 7);
    assert_eq!(output.edges().get(6).unwrap().next()?, 5);
    assert_eq!(output.edges().get(6).unwrap().prev()?, 12);
    let e = output.edges()[6];
    assert_eq!(output.edge_get_vertex1(e.id())?.unwrap(), 0);
    assert_eq!(output.edge_rot_next(e.id()).unwrap(), 13);
    assert!(output.edge_is_finite(e.id())?);
    assert!(!output.edge_is_infinite(e.id())?);
    assert!(e.is_linear());
    assert!(!e.is_curved());
    assert!(e.is_primary());
    assert!(!e.is_secondary());
    assert_eq!(output.edges().get(7).unwrap().cell()?, 1);
    assert_eq!(output.edges().get(7).unwrap().vertex0().unwrap(), 0);
    assert_eq!(output.edges().get(7).unwrap().twin()?, 6);
    assert_eq!(output.edges().get(7).unwrap().next()?, 10);
    assert_eq!(output.edges().get(7).unwrap().prev()?, 2);
    let e = output.edges()[7];
    assert_eq!(output.edge_get_vertex1(e.id())?.unwrap(), 2);
    assert_eq!(output.edge_rot_next(e.id()).unwrap(), 3);
    assert!(output.edge_is_finite(e.id())?);
    assert!(!output.edge_is_infinite(e.id())?);
    assert!(e.is_linear());
    assert!(!e.is_curved());
    assert!(e.is_primary());
    assert!(!e.is_secondary());
    assert_eq!(output.edges().get(8).unwrap().cell()?, 0);
    assert!(output.edges().get(8).unwrap().vertex0().is_none());
    assert_eq!(output.edges().get(8).unwrap().twin()?, 9);
    assert_eq!(output.edges().get(8).unwrap().next()?, 0);
    assert_eq!(output.edges().get(8).unwrap().prev()?, 0);
    let e = output.edges()[8];
    assert_eq!(output.edge_get_vertex1(e.id())?.unwrap(), 1);
    assert_eq!(output.edge_rot_next(e.id()).unwrap(), 1);
    assert!(!output.edge_is_finite(e.id())?);
    assert!(output.edge_is_infinite(e.id())?);
    assert!(e.is_linear());
    assert!(!e.is_curved());
    assert!(e.is_primary());
    assert!(!e.is_secondary());
    assert_eq!(output.edges().get(9).unwrap().cell()?, 2);
    assert_eq!(output.edges().get(9).unwrap().vertex0().unwrap(), 1);
    assert_eq!(output.edges().get(9).unwrap().twin()?, 8);
    assert_eq!(output.edges().get(9).unwrap().next()?, 4);
    assert_eq!(output.edges().get(9).unwrap().prev()?, 3);
    let e = output.edges()[9];
    assert!(output.edge_get_vertex1(e.id())?.is_none());
    assert_eq!(output.edge_rot_next(e.id()).unwrap(), 2);
    assert!(!output.edge_is_finite(e.id())?);
    assert!(output.edge_is_infinite(e.id())?);
    assert!(e.is_linear());
    assert!(!e.is_curved());
    assert!(e.is_primary());
    assert!(!e.is_secondary());
    assert_eq!(output.edges().get(10).unwrap().cell()?, 1);
    assert_eq!(output.edges().get(10).unwrap().vertex0().unwrap(), 2);
    assert_eq!(output.edges().get(10).unwrap().twin()?, 11);
    assert_eq!(output.edges().get(10).unwrap().next()?, 1);
    assert_eq!(output.edges().get(10).unwrap().prev()?, 7);
    let e = output.edges()[10];
    assert!(output.edge_get_vertex1(e.id())?.is_none());
    assert_eq!(output.edge_rot_next(e.id()).unwrap(), 6);
    assert!(!output.edge_is_finite(e.id())?);
    assert!(output.edge_is_infinite(e.id())?);
    assert!(e.is_linear());
    assert!(!e.is_curved());
    assert!(!e.is_primary());
    assert!(e.is_secondary());
    assert_eq!(output.edges().get(11).unwrap().cell()?, 4);
    assert!(output.edges().get(11).unwrap().vertex0().is_none());
    assert_eq!(output.edges().get(11).unwrap().twin()?, 10);
    assert_eq!(output.edges().get(11).unwrap().next()?, 13);
    assert_eq!(output.edges().get(11).unwrap().prev()?, 18);
    let e = output.edges()[11];
    assert_eq!(output.edge_get_vertex1(e.id())?.unwrap(), 2);
    assert_eq!(output.edge_rot_next(e.id()).unwrap(), 19);
    assert!(!output.edge_is_finite(e.id())?);
    assert!(output.edge_is_infinite(e.id())?);
    assert!(e.is_linear());
    assert!(!e.is_curved());
    assert!(!e.is_primary());
    assert!(e.is_secondary());
    assert_eq!(output.edges().get(12).unwrap().cell()?, 3);
    assert_eq!(output.edges().get(12).unwrap().vertex0().unwrap(), 3);
    assert_eq!(output.edges().get(12).unwrap().twin()?, 13);
    assert_eq!(output.edges().get(12).unwrap().next()?, 6);
    assert_eq!(output.edges().get(12).unwrap().prev()?, 14);
    let e = output.edges()[12];
    assert_eq!(output.edge_get_vertex1(e.id())?.unwrap(), 2);
    assert_eq!(output.edge_rot_next(e.id()).unwrap(), 15);
    assert!(output.edge_is_finite(e.id())?);
    assert!(!output.edge_is_infinite(e.id())?);
    assert!(!e.is_linear());
    assert!(e.is_curved());
    assert!(e.is_primary());
    assert!(!e.is_secondary());
    assert_eq!(output.edges().get(13).unwrap().cell()?, 4);
    assert_eq!(output.edges().get(13).unwrap().vertex0().unwrap(), 2);
    assert_eq!(output.edges().get(13).unwrap().twin()?, 12);
    assert_eq!(output.edges().get(13).unwrap().next()?, 17);
    assert_eq!(output.edges().get(13).unwrap().prev()?, 11);
    let e = output.edges()[13];
    assert_eq!(output.edge_get_vertex1(e.id())?.unwrap(), 3);
    assert_eq!(output.edge_rot_next(e.id()).unwrap(), 10);
    assert!(output.edge_is_finite(e.id())?);
    assert!(!output.edge_is_infinite(e.id())?);
    assert!(!e.is_linear());
    assert!(e.is_curved());
    assert!(e.is_primary());
    assert!(!e.is_secondary());
    assert_eq!(output.edges().get(14).unwrap().cell()?, 3);
    assert!(output.edges().get(14).unwrap().vertex0().is_none());
    assert_eq!(output.edges().get(14).unwrap().twin()?, 15);
    assert_eq!(output.edges().get(14).unwrap().next()?, 12);
    assert_eq!(output.edges().get(14).unwrap().prev()?, 5);
    let e = output.edges()[14];
    assert_eq!(output.edge_get_vertex1(e.id())?.unwrap(), 3);
    assert_eq!(output.edge_rot_next(e.id()).unwrap(), 4);
    assert!(!output.edge_is_finite(e.id())?);
    assert!(output.edge_is_infinite(e.id())?);
    assert!(e.is_linear());
    assert!(!e.is_curved());
    assert!(!e.is_primary());
    assert!(e.is_secondary());
    assert_eq!(output.edges().get(15).unwrap().cell()?, 5);
    assert_eq!(output.edges().get(15).unwrap().vertex0().unwrap(), 3);
    assert_eq!(output.edges().get(15).unwrap().twin()?, 14);
    assert_eq!(output.edges().get(15).unwrap().next()?, 20);
    assert_eq!(output.edges().get(15).unwrap().prev()?, 16);
    let e = output.edges()[15];
    assert!(output.edge_get_vertex1(e.id())?.is_none());
    assert_eq!(output.edge_rot_next(e.id()).unwrap(), 17);
    assert!(!output.edge_is_finite(e.id())?);
    assert!(output.edge_is_infinite(e.id())?);
    assert!(e.is_linear());
    assert!(!e.is_curved());
    assert!(!e.is_primary());
    assert!(e.is_secondary());
    assert_eq!(output.edges().get(16).unwrap().cell()?, 5);
    assert_eq!(output.edges().get(16).unwrap().vertex0().unwrap(), 4);
    assert_eq!(output.edges().get(16).unwrap().twin()?, 17);
    assert_eq!(output.edges().get(16).unwrap().next()?, 15);
    assert_eq!(output.edges().get(16).unwrap().prev()?, 20);
    let e = output.edges()[16];
    assert_eq!(output.edge_get_vertex1(e.id())?.unwrap(), 3);
    assert_eq!(output.edge_rot_next(e.id()).unwrap(), 21);
    assert!(output.edge_is_finite(e.id())?);
    assert!(!output.edge_is_infinite(e.id())?);
    assert!(e.is_linear());
    assert!(!e.is_curved());
    assert!(e.is_primary());
    assert!(!e.is_secondary());
    assert_eq!(output.edges().get(17).unwrap().cell()?, 4);
    assert_eq!(output.edges().get(17).unwrap().vertex0().unwrap(), 3);
    assert_eq!(output.edges().get(17).unwrap().twin()?, 16);
    assert_eq!(output.edges().get(17).unwrap().next()?, 18);
    assert_eq!(output.edges().get(17).unwrap().prev()?, 13);
    let e = output.edges()[17];
    assert_eq!(output.edge_get_vertex1(e.id())?.unwrap(), 4);
    assert_eq!(output.edge_rot_next(e.id()).unwrap(), 12);
    assert!(output.edge_is_finite(e.id())?);
    assert!(!output.edge_is_infinite(e.id())?);
    assert!(e.is_linear());
    assert!(!e.is_curved());
    assert!(e.is_primary());
    assert!(!e.is_secondary());
    assert_eq!(output.edges().get(18).unwrap().cell()?, 4);
    assert_eq!(output.edges().get(18).unwrap().vertex0().unwrap(), 4);
    assert_eq!(output.edges().get(18).unwrap().twin()?, 19);
    assert_eq!(output.edges().get(18).unwrap().next()?, 11);
    assert_eq!(output.edges().get(18).unwrap().prev()?, 17);
    let e = output.edges()[18];
    assert!(output.edge_get_vertex1(e.id())?.is_none());
    assert_eq!(output.edge_rot_next(e.id()).unwrap(), 16);
    assert!(!output.edge_is_finite(e.id())?);
    assert!(output.edge_is_infinite(e.id())?);
    assert!(e.is_linear());
    assert!(!e.is_curved());
    assert!(e.is_primary());
    assert!(!e.is_secondary());
    assert_eq!(output.edges().get(19).unwrap().cell()?, 6);
    assert!(output.edges().get(19).unwrap().vertex0().is_none());
    assert_eq!(output.edges().get(19).unwrap().twin()?, 18);
    assert_eq!(output.edges().get(19).unwrap().next()?, 21);
    assert_eq!(output.edges().get(19).unwrap().prev()?, 21);
    let e = output.edges()[19];
    assert_eq!(output.edge_get_vertex1(e.id())?.unwrap(), 4);
    assert_eq!(output.edge_rot_next(e.id()).unwrap(), 20);
    assert!(!output.edge_is_finite(e.id())?);
    assert!(output.edge_is_infinite(e.id())?);
    assert!(e.is_linear());
    assert!(!e.is_curved());
    assert!(e.is_primary());
    assert!(!e.is_secondary());
    assert_eq!(output.edges().get(20).unwrap().cell()?, 5);
    assert!(output.edges().get(20).unwrap().vertex0().is_none());
    assert_eq!(output.edges().get(20).unwrap().twin()?, 21);
    assert_eq!(output.edges().get(20).unwrap().next()?, 16);
    assert_eq!(output.edges().get(20).unwrap().prev()?, 15);
    let e = output.edges()[20];
    assert_eq!(output.edge_get_vertex1(e.id())?.unwrap(), 4);
    assert_eq!(output.edge_rot_next(e.id()).unwrap(), 14);
    assert!(!output.edge_is_finite(e.id())?);
    assert!(output.edge_is_infinite(e.id())?);
    assert!(e.is_linear());
    assert!(!e.is_curved());
    assert!(e.is_primary());
    assert!(!e.is_secondary());
    assert_eq!(output.edges().get(21).unwrap().cell()?, 6);
    assert_eq!(output.edges().get(21).unwrap().vertex0().unwrap(), 4);
    assert_eq!(output.edges().get(21).unwrap().twin()?, 20);
    assert_eq!(output.edges().get(21).unwrap().next()?, 19);
    assert_eq!(output.edges().get(21).unwrap().prev()?, 19);
    let e = output.edges()[21];
    assert!(output.edge_get_vertex1(e.id())?.is_none());
    assert_eq!(output.edge_rot_next(e.id()).unwrap(), 18);
    assert!(!output.edge_is_finite(e.id())?);
    assert!(output.edge_is_infinite(e.id())?);
    assert!(e.is_linear());
    assert!(!e.is_curved());
    assert!(e.is_primary());
    assert!(!e.is_secondary());
    Ok(())
}

#[allow(clippy::excessive_precision)]
#[test]
/// two segments and two points
fn two_segments_3() -> Result<(), BvError> {
    let output = {
        let _v = [Point { x: 4, y: 3 }, Point { x: 1, y: 1 }];
        let _s = [
            Line::new(Point { x: 1, y: 2 }, Point { x: 3, y: 4 }),
            Line::new(Point { x: 2, y: 2 }, Point { x: 5, y: 4 }),
        ];
        Builder::<I>::default()
            .with_vertices(_v.iter())?
            .with_segments(_s.iter())?
            .build()?
    };
    assert_eq!(output.cells().len(), 8);
    let cell = output.cells()[0];
    assert_eq!(cell.id(), 0);
    let (_source_index, _cat) = cell.source_index_2();
    assert_eq!(_cat, SourceCategory::SinglePoint);
    assert!(!cell.is_degenerate());
    assert!(cell.contains_point());
    assert!(!cell.contains_segment());
    let cell = output.cells()[1];
    assert_eq!(cell.id(), 1);
    let (_source_index, _cat) = cell.source_index_2();
    assert!(!cell.is_degenerate());
    assert!(cell.contains_point());
    assert!(!cell.contains_segment());
    let cell = output.cells()[2];
    assert_eq!(cell.id(), 2);
    let (_source_index, _cat) = cell.source_index_2();
    assert_eq!(_cat, SourceCategory::Segment);
    assert!(!cell.is_degenerate());
    assert!(!cell.contains_point());
    assert!(cell.contains_segment());
    let cell = output.cells()[3];
    assert_eq!(cell.id(), 3);
    let (_source_index, _cat) = cell.source_index_2();
    assert!(!cell.is_degenerate());
    assert!(cell.contains_point());
    assert!(!cell.contains_segment());
    let cell = output.cells()[4];
    assert_eq!(cell.id(), 4);
    let (_source_index, _cat) = cell.source_index_2();
    assert_eq!(_cat, SourceCategory::Segment);
    assert!(!cell.is_degenerate());
    assert!(!cell.contains_point());
    assert!(cell.contains_segment());
    let cell = output.cells()[5];
    assert_eq!(cell.id(), 5);
    let (_source_index, _cat) = cell.source_index_2();
    assert!(!cell.is_degenerate());
    assert!(cell.contains_point());
    assert!(!cell.contains_segment());
    let cell = output.cells()[6];
    assert_eq!(cell.id(), 6);
    let (_source_index, _cat) = cell.source_index_2();
    assert_eq!(_cat, SourceCategory::SinglePoint);
    assert!(!cell.is_degenerate());
    assert!(cell.contains_point());
    assert!(!cell.contains_segment());
    let cell = output.cells()[7];
    assert_eq!(cell.id(), 7);
    let (_source_index, _cat) = cell.source_index_2();
    assert!(!cell.is_degenerate());
    assert!(cell.contains_point());
    assert!(!cell.contains_segment());
    assert_eq!(output.vertices().len(), 7);
    assert_eq!(output.edges().len(), 28);
    let v = output.vertices()[0];
    assert!(almost_equal(v.x(), 1.8019610, v.y(), 2.2970585));
    assert_eq!(v.get_incident_edge()?, 9);
    let v = output.vertices()[1];
    assert!(almost_equal(v.x(), 1.5000000, v.y(), 1.5000000));
    assert_eq!(v.get_incident_edge()?, 11);
    let v = output.vertices()[2];
    assert!(almost_equal(v.x(), 3.3960781, v.y(), 3.6039219));
    assert_eq!(v.get_incident_edge()?, 15);
    let v = output.vertices()[3];
    assert!(almost_equal(v.x(), 4.0000000, v.y(), 5.5000000));
    assert_eq!(v.get_incident_edge()?, 21);
    let v = output.vertices()[4];
    assert!(almost_equal(v.x(), 4.0000000, v.y(), -1.0000000));
    assert_eq!(v.get_incident_edge()?, 23);
    let v = output.vertices()[5];
    assert!(almost_equal(v.x(), 7.0000000, v.y(), 1.0000000));
    assert_eq!(v.get_incident_edge()?, 25);
    let v = output.vertices()[6];
    assert!(almost_equal(v.x(), 5.6730769, v.y(), -2.7596154));
    assert_eq!(v.get_incident_edge()?, 27);
    Ok(())
}

#[allow(clippy::excessive_precision)]
#[test]
/// two segments and four points
fn two_segments_5() -> Result<(), BvError> {
    let output = {
        let v: [[I; 2]; 4] = [[582, 779], [683, 1329], [741, 1155], [1239, 1102]];
        let s: [[I; 4]; 2] = [[1394, 1470, 982, 1594], [1047, 1427, 1155, 1228]];

        Builder::<I>::default()
            .with_vertices(v.iter())?
            .with_segments(s.iter())?
            .build()?
    };
    assert_eq!(output.cells().len(), 10);
    let cell = output.cells()[0];
    assert_eq!(cell.id(), 0);
    assert_eq!(cell.source_index(), 0);
    assert!(!cell.is_degenerate());
    assert!(cell.contains_point());
    assert!(!cell.contains_segment());
    let cell = output.cells()[1];
    assert_eq!(cell.id(), 1);
    assert_eq!(cell.source_index(), 1);
    assert!(!cell.is_degenerate());
    assert!(cell.contains_point());
    assert!(!cell.contains_segment());
    let cell = output.cells()[2];
    assert_eq!(cell.id(), 2);
    assert_eq!(cell.source_index(), 2);
    assert!(!cell.is_degenerate());
    assert!(cell.contains_point());
    assert!(!cell.contains_segment());
    let cell = output.cells()[3];
    assert_eq!(cell.id(), 3);
    assert_eq!(cell.source_index(), 4);
    assert!(!cell.is_degenerate());
    assert!(cell.contains_point());
    assert!(!cell.contains_segment());
    let cell = output.cells()[4];
    assert_eq!(cell.id(), 4);
    assert_eq!(cell.source_index(), 4);
    assert!(!cell.is_degenerate());
    assert!(!cell.contains_point());
    assert!(cell.contains_segment());
    let cell = output.cells()[5];
    assert_eq!(cell.id(), 5);
    assert_eq!(cell.source_index(), 5);
    assert!(!cell.is_degenerate());
    assert!(cell.contains_point());
    assert!(!cell.contains_segment());
    let cell = output.cells()[6];
    assert_eq!(cell.id(), 6);
    assert_eq!(cell.source_index(), 5);
    assert!(!cell.is_degenerate());
    assert!(!cell.contains_point());
    assert!(cell.contains_segment());
    let cell = output.cells()[7];
    assert_eq!(cell.id(), 7);
    assert_eq!(cell.source_index(), 5);
    assert!(!cell.is_degenerate());
    assert!(cell.contains_point());
    assert!(!cell.contains_segment());
    let cell = output.cells()[8];
    assert_eq!(cell.id(), 8);
    assert_eq!(cell.source_index(), 3);
    assert!(!cell.is_degenerate());
    assert!(cell.contains_point());
    assert!(!cell.contains_segment());
    let cell = output.cells()[9];
    assert_eq!(cell.id(), 9);
    assert_eq!(cell.source_index(), 4);
    assert!(!cell.is_degenerate());
    assert!(cell.contains_point());
    assert!(!cell.contains_segment());
    assert_eq!(output.vertices().len(), 12);
    assert_eq!(output.edges().len(), 42);
    let v = output.vertices()[0];
    assert!(almost_equal(v.x(), 320.1025791, v.y(), 1111.3675264));
    assert_eq!(v.get_incident_edge()?, 5);
    let v = output.vertices()[1];
    assert!(almost_equal(v.x(), 846.8907651, v.y(), 1445.2628726));
    assert_eq!(v.get_incident_edge()?, 15);
    let v = output.vertices()[2];
    assert!(almost_equal(v.x(), 949.2219808, v.y(), 1485.0923877));
    assert_eq!(v.get_incident_edge()?, 17);
    let v = output.vertices()[3];
    assert!(almost_equal(v.x(), 876.6922428, v.y(), 1334.5716695));
    assert_eq!(v.get_incident_edge()?, 19);
    let v = output.vertices()[4];
    assert!(almost_equal(v.x(), 884.4954950, v.y(), 1299.4984983));
    assert_eq!(v.get_incident_edge()?, 21);
    let v = output.vertices()[5];
    assert!(almost_equal(v.x(), 960.2050792, v.y(), 1122.2821535));
    assert_eq!(v.get_incident_edge()?, 25);
    let v = output.vertices()[6];
    assert!(almost_equal(v.x(), 1119.5619154, v.y(), 1466.3803360));
    assert_eq!(v.get_incident_edge()?, 27);
    let v = output.vertices()[7];
    assert!(almost_equal(v.x(), 978.3728386, v.y(), 1019.2485591));
    assert_eq!(v.get_incident_edge()?, 31);
    let v = output.vertices()[8];
    assert!(almost_equal(v.x(), 959.4051795, v.y(), 841.0241395));
    assert_eq!(v.get_incident_edge()?, 33);
    let v = output.vertices()[9];
    assert!(almost_equal(v.x(), 1309.5034594, v.y(), 1311.8511237));
    assert_eq!(v.get_incident_edge()?, 37);
    let v = output.vertices()[10];
    assert!(almost_equal(v.x(), 1338.5456162, v.y(), 1285.7483377));
    assert_eq!(v.get_incident_edge()?, 39);
    let v = output.vertices()[11];
    assert!(almost_equal(v.x(), 1354.4950042, v.y(), 1269.9966694));
    assert_eq!(v.get_incident_edge()?, 41);
    Ok(())
}

#[allow(clippy::excessive_precision)]
#[test]
/// two problematic segments
fn two_segments_6() -> Result<(), BvError> {
    let output = {
        let v: [[I; 2]; 0] = [];
        let s: [[I; 4]; 2] = [[442, 215, 438, 355], [129, 559, 141, 60]];

        Builder::<I>::default()
            .with_vertices(v.iter())?
            .with_segments(s.iter())?
            .build()?
    };
    assert_eq!(output.cells().len(), 6);
    let cell = output.cells()[0];
    assert_eq!(cell.id(), 0);
    assert_eq!(cell.source_index(), 1);
    assert!(!cell.is_degenerate());
    assert!(cell.contains_point());
    assert!(!cell.contains_segment());
    let cell = output.cells()[1];
    assert_eq!(cell.id(), 1);
    assert_eq!(cell.source_index(), 1);
    assert!(!cell.is_degenerate());
    assert!(!cell.contains_point());
    assert!(cell.contains_segment());
    let cell = output.cells()[2];
    assert_eq!(cell.id(), 2);
    assert_eq!(cell.source_index(), 1);
    assert!(!cell.is_degenerate());
    assert!(cell.contains_point());
    assert!(!cell.contains_segment());
    let cell = output.cells()[3];
    assert_eq!(cell.id(), 3);
    assert_eq!(cell.source_index(), 0);
    assert!(!cell.is_degenerate());
    assert!(cell.contains_point());
    assert!(!cell.contains_segment());
    let cell = output.cells()[4];
    assert_eq!(cell.id(), 4);
    assert_eq!(cell.source_index(), 0);
    assert!(!cell.is_degenerate());
    assert!(!cell.contains_point());
    assert!(cell.contains_segment());
    let cell = output.cells()[5];
    assert_eq!(cell.id(), 5);
    assert_eq!(cell.source_index(), 0);
    assert!(!cell.is_degenerate());
    assert!(cell.contains_point());
    assert!(!cell.contains_segment());
    assert_eq!(output.vertices().len(), 4);
    assert_eq!(output.edges().len(), 18);
    let v = output.vertices()[0];
    assert!(almost_equal(v.x(), 286.0580800, v.y(), 350.6588023));
    assert_eq!(v.get_incident_edge()?, 9);
    let v = output.vertices()[1];
    assert!(almost_equal(v.x(), 289.7416658, v.y(), 210.6497619));
    assert_eq!(v.get_incident_edge()?, 13);
    let v = output.vertices()[2];
    assert!(almost_equal(v.x(), 329.0795415, v.y(), 64.5229549));
    assert_eq!(v.get_incident_edge()?, 15);
    let v = output.vertices()[3];
    assert!(almost_equal(v.x(), 354.4186453, v.y(), 564.4208893));
    assert_eq!(v.get_incident_edge()?, 17);
    assert_eq!(output.edges().first().unwrap().cell()?, 0);
    assert!(output.edges().first().unwrap().vertex0().is_none());
    assert_eq!(output.edges().first().unwrap().twin()?, 1);
    assert_eq!(output.edges().first().unwrap().next()?, 17);
    assert_eq!(output.edges().first().unwrap().prev()?, 17);
    let e = output.edges()[0];
    assert_eq!(output.edge_get_vertex1(e.id())?.unwrap(), 3);
    assert_eq!(output.edge_rot_next(e.id()).unwrap(), 16);
    assert_eq!(output.edge_rot_prev(e.id()).unwrap(), 2);
    assert!(!output.edge_is_finite(e.id())?);
    assert!(output.edge_is_infinite(e.id())?);
    assert!(e.is_linear());
    assert!(!e.is_curved());
    assert!(!e.is_primary());
    assert!(e.is_secondary());
    assert_eq!(output.edges().get(1).unwrap().cell()?, 1);
    assert_eq!(output.edges().get(1).unwrap().vertex0().unwrap(), 3);
    assert_eq!(output.edges().get(1).unwrap().twin()?, 0);
    assert_eq!(output.edges().get(1).unwrap().next()?, 2);
    assert_eq!(output.edges().get(1).unwrap().prev()?, 4);
    let e = output.edges()[1];
    assert!(output.edge_get_vertex1(e.id())?.is_none());
    assert_eq!(output.edge_rot_next(e.id()).unwrap(), 5);
    assert_eq!(output.edge_rot_prev(e.id()).unwrap(), 17);
    assert!(!output.edge_is_finite(e.id())?);
    assert!(output.edge_is_infinite(e.id())?);
    assert!(e.is_linear());
    assert!(!e.is_curved());
    assert!(!e.is_primary());
    assert!(e.is_secondary());
    assert_eq!(output.edges().get(2).unwrap().cell()?, 1);
    assert!(output.edges().get(2).unwrap().vertex0().is_none());
    assert_eq!(output.edges().get(2).unwrap().twin()?, 3);
    assert_eq!(output.edges().get(2).unwrap().next()?, 12);
    assert_eq!(output.edges().get(2).unwrap().prev()?, 1);
    let e = output.edges()[2];
    assert_eq!(output.edge_get_vertex1(e.id())?.unwrap(), 2);
    assert_eq!(output.edge_rot_next(e.id()).unwrap(), 0);
    assert_eq!(output.edge_rot_prev(e.id()).unwrap(), 14);
    assert!(!output.edge_is_finite(e.id())?);
    assert!(output.edge_is_infinite(e.id())?);
    assert!(e.is_linear());
    assert!(!e.is_curved());
    assert!(!e.is_primary());
    assert!(e.is_secondary());
    assert_eq!(output.edges().get(3).unwrap().cell()?, 2);
    assert_eq!(output.edges().get(3).unwrap().vertex0().unwrap(), 2);
    assert_eq!(output.edges().get(3).unwrap().twin()?, 2);
    assert_eq!(output.edges().get(3).unwrap().next()?, 14);
    assert_eq!(output.edges().get(3).unwrap().prev()?, 14);
    let e = output.edges()[3];
    assert!(output.edge_get_vertex1(e.id())?.is_none());
    assert_eq!(output.edge_rot_next(e.id()).unwrap(), 15);
    assert_eq!(output.edge_rot_prev(e.id()).unwrap(), 12);
    assert!(!output.edge_is_finite(e.id())?);
    assert!(output.edge_is_infinite(e.id())?);
    assert!(e.is_linear());
    assert!(!e.is_curved());
    assert!(!e.is_primary());
    assert!(e.is_secondary());
    assert_eq!(output.edges().get(4).unwrap().cell()?, 1);
    assert_eq!(output.edges().get(4).unwrap().vertex0().unwrap(), 0);
    assert_eq!(output.edges().get(4).unwrap().twin()?, 5);
    assert_eq!(output.edges().get(4).unwrap().next()?, 1);
    assert_eq!(output.edges().get(4).unwrap().prev()?, 8);
    let e = output.edges()[4];
    assert_eq!(output.edge_get_vertex1(e.id())?.unwrap(), 3);
    assert_eq!(output.edge_rot_next(e.id()).unwrap(), 9);
    assert_eq!(output.edge_rot_prev(e.id()).unwrap(), 6);
    assert!(output.edge_is_finite(e.id())?);
    assert!(!output.edge_is_infinite(e.id())?);
    assert!(!e.is_linear());
    assert!(e.is_curved());
    assert!(e.is_primary());
    assert!(!e.is_secondary());
    assert_eq!(output.edges().get(5).unwrap().cell()?, 3);
    assert_eq!(output.edges().get(5).unwrap().vertex0().unwrap(), 3);
    assert_eq!(output.edges().get(5).unwrap().twin()?, 4);
    assert_eq!(output.edges().get(5).unwrap().next()?, 6);
    assert_eq!(output.edges().get(5).unwrap().prev()?, 16);
    let e = output.edges()[5];
    assert_eq!(output.edge_get_vertex1(e.id())?.unwrap(), 0);
    assert_eq!(output.edge_rot_next(e.id()).unwrap(), 17);
    assert_eq!(output.edge_rot_prev(e.id()).unwrap(), 1);
    assert!(output.edge_is_finite(e.id())?);
    assert!(!output.edge_is_infinite(e.id())?);
    assert!(!e.is_linear());
    assert!(e.is_curved());
    assert!(e.is_primary());
    assert!(!e.is_secondary());
    assert_eq!(output.edges().get(6).unwrap().cell()?, 3);
    assert_eq!(output.edges().get(6).unwrap().vertex0().unwrap(), 0);
    assert_eq!(output.edges().get(6).unwrap().twin()?, 7);
    assert_eq!(output.edges().get(6).unwrap().next()?, 16);
    assert_eq!(output.edges().get(6).unwrap().prev()?, 5);
    let e = output.edges()[6];
    assert!(output.edge_get_vertex1(e.id())?.is_none());
    assert_eq!(output.edge_rot_next(e.id()).unwrap(), 4);
    assert_eq!(output.edge_rot_prev(e.id()).unwrap(), 9);
    assert!(!output.edge_is_finite(e.id())?);
    assert!(output.edge_is_infinite(e.id())?);
    assert!(e.is_linear());
    assert!(!e.is_curved());
    assert!(!e.is_primary());
    assert!(e.is_secondary());
    assert_eq!(output.edges().get(7).unwrap().cell()?, 4);
    assert!(output.edges().get(7).unwrap().vertex0().is_none());
    assert_eq!(output.edges().get(7).unwrap().twin()?, 6);
    assert_eq!(output.edges().get(7).unwrap().next()?, 9);
    assert_eq!(output.edges().get(7).unwrap().prev()?, 10);
    let e = output.edges()[7];
    assert_eq!(output.edge_get_vertex1(e.id())?.unwrap(), 0);
    assert_eq!(output.edge_rot_next(e.id()).unwrap(), 11);
    assert_eq!(output.edge_rot_prev(e.id()).unwrap(), 16);
    assert!(!output.edge_is_finite(e.id())?);
    assert!(output.edge_is_infinite(e.id())?);
    assert!(e.is_linear());
    assert!(!e.is_curved());
    assert!(!e.is_primary());
    assert!(e.is_secondary());
    assert_eq!(output.edges().get(8).unwrap().cell()?, 1);
    assert_eq!(output.edges().get(8).unwrap().vertex0().unwrap(), 1);
    assert_eq!(output.edges().get(8).unwrap().twin()?, 9);
    assert_eq!(output.edges().get(8).unwrap().next()?, 4);
    assert_eq!(output.edges().get(8).unwrap().prev()?, 12);
    let e = output.edges()[8];
    assert_eq!(output.edge_get_vertex1(e.id())?.unwrap(), 0);
    assert_eq!(output.edge_rot_next(e.id()).unwrap(), 13);
    assert_eq!(output.edge_rot_prev(e.id()).unwrap(), 10);
    assert!(output.edge_is_finite(e.id())?);
    assert!(!output.edge_is_infinite(e.id())?);
    assert!(e.is_linear());
    assert!(!e.is_curved());
    assert!(e.is_primary());
    assert!(!e.is_secondary());
    assert_eq!(output.edges().get(9).unwrap().cell()?, 4);
    assert_eq!(output.edges().get(9).unwrap().vertex0().unwrap(), 0);
    assert_eq!(output.edges().get(9).unwrap().twin()?, 8);
    assert_eq!(output.edges().get(9).unwrap().next()?, 10);
    assert_eq!(output.edges().get(9).unwrap().prev()?, 7);
    let e = output.edges()[9];
    assert_eq!(output.edge_get_vertex1(e.id())?.unwrap(), 1);
    assert_eq!(output.edge_rot_next(e.id()).unwrap(), 6);
    assert_eq!(output.edge_rot_prev(e.id()).unwrap(), 4);
    assert!(output.edge_is_finite(e.id())?);
    assert!(!output.edge_is_infinite(e.id())?);
    assert!(e.is_linear());
    assert!(!e.is_curved());
    assert!(e.is_primary());
    assert!(!e.is_secondary());
    assert_eq!(output.edges().get(10).unwrap().cell()?, 4);
    assert_eq!(output.edges().get(10).unwrap().vertex0().unwrap(), 1);
    assert_eq!(output.edges().get(10).unwrap().twin()?, 11);
    assert_eq!(output.edges().get(10).unwrap().next()?, 7);
    assert_eq!(output.edges().get(10).unwrap().prev()?, 9);
    let e = output.edges()[10];
    assert!(output.edge_get_vertex1(e.id())?.is_none());
    assert_eq!(output.edge_rot_next(e.id()).unwrap(), 8);
    assert_eq!(output.edge_rot_prev(e.id()).unwrap(), 13);
    assert!(!output.edge_is_finite(e.id())?);
    assert!(output.edge_is_infinite(e.id())?);
    assert!(e.is_linear());
    assert!(!e.is_curved());
    assert!(!e.is_primary());
    assert!(e.is_secondary());
    assert_eq!(output.edges().get(11).unwrap().cell()?, 5);
    assert!(output.edges().get(11).unwrap().vertex0().is_none());
    assert_eq!(output.edges().get(11).unwrap().twin()?, 10);
    assert_eq!(output.edges().get(11).unwrap().next()?, 13);
    assert_eq!(output.edges().get(11).unwrap().prev()?, 15);
    let e = output.edges()[11];
    assert_eq!(output.edge_get_vertex1(e.id())?.unwrap(), 1);
    assert_eq!(output.edge_rot_next(e.id()).unwrap(), 14);
    assert_eq!(output.edge_rot_prev(e.id()).unwrap(), 7);
    assert!(!output.edge_is_finite(e.id())?);
    assert!(output.edge_is_infinite(e.id())?);
    assert!(e.is_linear());
    assert!(!e.is_curved());
    assert!(!e.is_primary());
    assert!(e.is_secondary());
    assert_eq!(output.edges().get(12).unwrap().cell()?, 1);
    assert_eq!(output.edges().get(12).unwrap().vertex0().unwrap(), 2);
    assert_eq!(output.edges().get(12).unwrap().twin()?, 13);
    assert_eq!(output.edges().get(12).unwrap().next()?, 8);
    assert_eq!(output.edges().get(12).unwrap().prev()?, 2);
    let e = output.edges()[12];
    assert_eq!(output.edge_get_vertex1(e.id())?.unwrap(), 1);
    assert_eq!(output.edge_rot_next(e.id()).unwrap(), 3);
    assert_eq!(output.edge_rot_prev(e.id()).unwrap(), 15);
    assert!(output.edge_is_finite(e.id())?);
    assert!(!output.edge_is_infinite(e.id())?);
    assert!(!e.is_linear());
    assert!(e.is_curved());
    assert!(e.is_primary());
    assert!(!e.is_secondary());
    assert_eq!(output.edges().get(13).unwrap().cell()?, 5);
    assert_eq!(output.edges().get(13).unwrap().vertex0().unwrap(), 1);
    assert_eq!(output.edges().get(13).unwrap().twin()?, 12);
    assert_eq!(output.edges().get(13).unwrap().next()?, 15);
    assert_eq!(output.edges().get(13).unwrap().prev()?, 11);
    let e = output.edges()[13];
    assert_eq!(output.edge_get_vertex1(e.id())?.unwrap(), 2);
    assert_eq!(output.edge_rot_next(e.id()).unwrap(), 10);
    assert_eq!(output.edge_rot_prev(e.id()).unwrap(), 8);
    assert!(output.edge_is_finite(e.id())?);
    assert!(!output.edge_is_infinite(e.id())?);
    assert!(!e.is_linear());
    assert!(e.is_curved());
    assert!(e.is_primary());
    assert!(!e.is_secondary());
    assert_eq!(output.edges().get(14).unwrap().cell()?, 2);
    assert!(output.edges().get(14).unwrap().vertex0().is_none());
    assert_eq!(output.edges().get(14).unwrap().twin()?, 15);
    assert_eq!(output.edges().get(14).unwrap().next()?, 3);
    assert_eq!(output.edges().get(14).unwrap().prev()?, 3);
    let e = output.edges()[14];
    assert_eq!(output.edge_get_vertex1(e.id())?.unwrap(), 2);
    assert_eq!(output.edge_rot_next(e.id()).unwrap(), 2);
    assert_eq!(output.edge_rot_prev(e.id()).unwrap(), 11);
    assert!(!output.edge_is_finite(e.id())?);
    assert!(output.edge_is_infinite(e.id())?);
    assert!(e.is_linear());
    assert!(!e.is_curved());
    assert!(e.is_primary());
    assert!(!e.is_secondary());
    assert_eq!(output.edges().get(15).unwrap().cell()?, 5);
    assert_eq!(output.edges().get(15).unwrap().vertex0().unwrap(), 2);
    assert_eq!(output.edges().get(15).unwrap().twin()?, 14);
    assert_eq!(output.edges().get(15).unwrap().next()?, 11);
    assert_eq!(output.edges().get(15).unwrap().prev()?, 13);
    let e = output.edges()[15];
    assert!(output.edge_get_vertex1(e.id())?.is_none());
    assert_eq!(output.edge_rot_next(e.id()).unwrap(), 12);
    assert_eq!(output.edge_rot_prev(e.id()).unwrap(), 3);
    assert!(!output.edge_is_finite(e.id())?);
    assert!(output.edge_is_infinite(e.id())?);
    assert!(e.is_linear());
    assert!(!e.is_curved());
    assert!(e.is_primary());
    assert!(!e.is_secondary());
    assert_eq!(output.edges().get(16).unwrap().cell()?, 3);
    assert!(output.edges().get(16).unwrap().vertex0().is_none());
    assert_eq!(output.edges().get(16).unwrap().twin()?, 17);
    assert_eq!(output.edges().get(16).unwrap().next()?, 5);
    assert_eq!(output.edges().get(16).unwrap().prev()?, 6);
    let e = output.edges()[16];
    assert_eq!(output.edge_get_vertex1(e.id())?.unwrap(), 3);
    assert_eq!(output.edge_rot_next(e.id()).unwrap(), 7);
    assert_eq!(output.edge_rot_prev(e.id()).unwrap(), 0);
    assert!(!output.edge_is_finite(e.id())?);
    assert!(output.edge_is_infinite(e.id())?);
    assert!(e.is_linear());
    assert!(!e.is_curved());
    assert!(e.is_primary());
    assert!(!e.is_secondary());
    assert_eq!(output.edges().get(17).unwrap().cell()?, 0);
    assert_eq!(output.edges().get(17).unwrap().vertex0().unwrap(), 3);
    assert_eq!(output.edges().get(17).unwrap().twin()?, 16);
    assert_eq!(output.edges().get(17).unwrap().next()?, 0);
    assert_eq!(output.edges().get(17).unwrap().prev()?, 0);
    let e = output.edges()[17];
    assert!(output.edge_get_vertex1(e.id())?.is_none());
    assert_eq!(output.edge_rot_next(e.id()).unwrap(), 1);
    assert_eq!(output.edge_rot_prev(e.id()).unwrap(), 5);
    assert!(!output.edge_is_finite(e.id())?);
    assert!(output.edge_is_infinite(e.id())?);
    assert!(e.is_linear());
    assert!(!e.is_curved());
    assert!(e.is_primary());
    assert!(!e.is_secondary());
    Ok(())
}

#[allow(clippy::excessive_precision)]
#[test]
/// two problematic segments
fn two_segments_7() -> Result<(), BvError> {
    let output = {
        let v: [[I; 2]; 0] = [];
        let s: [[I; 4]; 2] = [[498, 224, 475, 335], [250, 507, 60, 77]];

        Builder::<I>::default()
            .with_vertices(v.iter())?
            .with_segments(s.iter())?
            .build()?
    };
    assert_eq!(output.cells().len(), 6);
    let cell = output.cells()[0];
    assert_eq!(cell.id(), 0);
    assert_eq!(cell.source_index(), 1);
    assert!(!cell.is_degenerate());
    assert!(cell.contains_point());
    assert!(!cell.contains_segment());
    let cell = output.cells()[1];
    assert_eq!(cell.id(), 1);
    assert_eq!(cell.source_index(), 1);
    assert!(!cell.is_degenerate());
    assert!(!cell.contains_point());
    assert!(cell.contains_segment());
    let cell = output.cells()[2];
    assert_eq!(cell.id(), 2);
    assert_eq!(cell.source_index(), 1);
    assert!(!cell.is_degenerate());
    assert!(cell.contains_point());
    assert!(!cell.contains_segment());
    let cell = output.cells()[3];
    assert_eq!(cell.id(), 3);
    assert_eq!(cell.source_index(), 0);
    assert!(!cell.is_degenerate());
    assert!(cell.contains_point());
    assert!(!cell.contains_segment());
    let cell = output.cells()[4];
    assert_eq!(cell.id(), 4);
    assert_eq!(cell.source_index(), 0);
    assert!(!cell.is_degenerate());
    assert!(!cell.contains_point());
    assert!(cell.contains_segment());
    let cell = output.cells()[5];
    assert_eq!(cell.id(), 5);
    assert_eq!(cell.source_index(), 0);
    assert!(!cell.is_degenerate());
    assert!(cell.contains_point());
    assert!(!cell.contains_segment());
    assert_eq!(output.vertices().len(), 4);
    assert_eq!(output.edges().len(), 18);
    let v = output.vertices()[0];
    assert!(almost_equal(v.x(), 326.3534001, v.y(), 304.1993532));
    assert_eq!(v.get_incident_edge()?, 9);
    let v = output.vertices()[1];
    assert!(almost_equal(v.x(), 313.7737689, v.y(), 185.8269972));
    assert_eq!(v.get_incident_edge()?, 13);
    let v = output.vertices()[2];
    assert!(almost_equal(v.x(), 383.2375415, v.y(), 448.1275979));
    assert_eq!(v.get_incident_edge()?, 15);
    let v = output.vertices()[3];
    assert!(almost_equal(v.x(), 346.0943520, v.y(), -49.4137834));
    assert_eq!(v.get_incident_edge()?, 17);
    assert_eq!(output.edges().first().unwrap().cell()?, 0);
    assert_eq!(output.edges().first().unwrap().vertex0().unwrap(), 3);
    assert_eq!(output.edges().first().unwrap().twin()?, 1);
    assert_eq!(output.edges().first().unwrap().next()?, 16);
    assert_eq!(output.edges().first().unwrap().prev()?, 16);
    let e = output.edges()[0];
    assert!(output.edge_get_vertex1(e.id())?.is_none());
    assert_eq!(output.edge_rot_next(e.id()).unwrap(), 17);
    assert_eq!(output.edge_rot_prev(e.id()).unwrap(), 12);
    assert!(!output.edge_is_finite(e.id())?);
    assert!(output.edge_is_infinite(e.id())?);
    assert!(e.is_linear());
    assert!(!e.is_curved());
    assert!(!e.is_primary());
    assert!(e.is_secondary());
    assert_eq!(output.edges().get(1).unwrap().cell()?, 1);
    assert!(output.edges().get(1).unwrap().vertex0().is_none());
    assert_eq!(output.edges().get(1).unwrap().twin()?, 0);
    assert_eq!(output.edges().get(1).unwrap().next()?, 12);
    assert_eq!(output.edges().get(1).unwrap().prev()?, 2);
    let e = output.edges()[1];
    assert_eq!(output.edge_get_vertex1(e.id())?.unwrap(), 3);
    assert_eq!(output.edge_rot_next(e.id()).unwrap(), 3);
    assert_eq!(output.edge_rot_prev(e.id()).unwrap(), 16);
    assert!(!output.edge_is_finite(e.id())?);
    assert!(output.edge_is_infinite(e.id())?);
    assert!(e.is_linear());
    assert!(!e.is_curved());
    assert!(!e.is_primary());
    assert!(e.is_secondary());
    assert_eq!(output.edges().get(2).unwrap().cell()?, 1);
    assert_eq!(output.edges().get(2).unwrap().vertex0().unwrap(), 2);
    assert_eq!(output.edges().get(2).unwrap().twin()?, 3);
    assert_eq!(output.edges().get(2).unwrap().next()?, 1);
    assert_eq!(output.edges().get(2).unwrap().prev()?, 4);
    let e = output.edges()[2];
    assert!(output.edge_get_vertex1(e.id())?.is_none());
    assert_eq!(output.edge_rot_next(e.id()).unwrap(), 5);
    assert_eq!(output.edge_rot_prev(e.id()).unwrap(), 15);
    assert!(!output.edge_is_finite(e.id())?);
    assert!(output.edge_is_infinite(e.id())?);
    assert!(e.is_linear());
    assert!(!e.is_curved());
    assert!(!e.is_primary());
    assert!(e.is_secondary());
    assert_eq!(output.edges().get(3).unwrap().cell()?, 2);
    assert!(output.edges().get(3).unwrap().vertex0().is_none());
    assert_eq!(output.edges().get(3).unwrap().twin()?, 2);
    assert_eq!(output.edges().get(3).unwrap().next()?, 15);
    assert_eq!(output.edges().get(3).unwrap().prev()?, 15);
    let e = output.edges()[3];
    assert_eq!(output.edge_get_vertex1(e.id())?.unwrap(), 2);
    assert_eq!(output.edge_rot_next(e.id()).unwrap(), 14);
    assert_eq!(output.edge_rot_prev(e.id()).unwrap(), 1);
    assert!(!output.edge_is_finite(e.id())?);
    assert!(output.edge_is_infinite(e.id())?);
    assert!(e.is_linear());
    assert!(!e.is_curved());
    assert!(!e.is_primary());
    assert!(e.is_secondary());
    assert_eq!(output.edges().get(4).unwrap().cell()?, 1);
    assert_eq!(output.edges().get(4).unwrap().vertex0().unwrap(), 0);
    assert_eq!(output.edges().get(4).unwrap().twin()?, 5);
    assert_eq!(output.edges().get(4).unwrap().next()?, 2);
    assert_eq!(output.edges().get(4).unwrap().prev()?, 8);
    let e = output.edges()[4];
    assert_eq!(output.edge_get_vertex1(e.id())?.unwrap(), 2);
    assert_eq!(output.edge_rot_next(e.id()).unwrap(), 9);
    assert_eq!(output.edge_rot_prev(e.id()).unwrap(), 6);
    assert!(output.edge_is_finite(e.id())?);
    assert!(!output.edge_is_infinite(e.id())?);
    assert!(!e.is_linear());
    assert!(e.is_curved());
    assert!(e.is_primary());
    assert!(!e.is_secondary());
    assert_eq!(output.edges().get(5).unwrap().cell()?, 3);
    assert_eq!(output.edges().get(5).unwrap().vertex0().unwrap(), 2);
    assert_eq!(output.edges().get(5).unwrap().twin()?, 4);
    assert_eq!(output.edges().get(5).unwrap().next()?, 6);
    assert_eq!(output.edges().get(5).unwrap().prev()?, 14);
    let e = output.edges()[5];
    assert_eq!(output.edge_get_vertex1(e.id())?.unwrap(), 0);
    assert_eq!(output.edge_rot_next(e.id()).unwrap(), 15);
    assert_eq!(output.edge_rot_prev(e.id()).unwrap(), 2);
    assert!(output.edge_is_finite(e.id())?);
    assert!(!output.edge_is_infinite(e.id())?);
    assert!(!e.is_linear());
    assert!(e.is_curved());
    assert!(e.is_primary());
    assert!(!e.is_secondary());
    assert_eq!(output.edges().get(6).unwrap().cell()?, 3);
    assert_eq!(output.edges().get(6).unwrap().vertex0().unwrap(), 0);
    assert_eq!(output.edges().get(6).unwrap().twin()?, 7);
    assert_eq!(output.edges().get(6).unwrap().next()?, 14);
    assert_eq!(output.edges().get(6).unwrap().prev()?, 5);
    let e = output.edges()[6];
    assert!(output.edge_get_vertex1(e.id())?.is_none());
    assert_eq!(output.edge_rot_next(e.id()).unwrap(), 4);
    assert_eq!(output.edge_rot_prev(e.id()).unwrap(), 9);
    assert!(!output.edge_is_finite(e.id())?);
    assert!(output.edge_is_infinite(e.id())?);
    assert!(e.is_linear());
    assert!(!e.is_curved());
    assert!(!e.is_primary());
    assert!(e.is_secondary());
    assert_eq!(output.edges().get(7).unwrap().cell()?, 4);
    assert!(output.edges().get(7).unwrap().vertex0().is_none());
    assert_eq!(output.edges().get(7).unwrap().twin()?, 6);
    assert_eq!(output.edges().get(7).unwrap().next()?, 9);
    assert_eq!(output.edges().get(7).unwrap().prev()?, 10);
    let e = output.edges()[7];
    assert_eq!(output.edge_get_vertex1(e.id())?.unwrap(), 0);
    assert_eq!(output.edge_rot_next(e.id()).unwrap(), 11);
    assert_eq!(output.edge_rot_prev(e.id()).unwrap(), 14);
    assert!(!output.edge_is_finite(e.id())?);
    assert!(output.edge_is_infinite(e.id())?);
    assert!(e.is_linear());
    assert!(!e.is_curved());
    assert!(!e.is_primary());
    assert!(e.is_secondary());
    assert_eq!(output.edges().get(8).unwrap().cell()?, 1);
    assert_eq!(output.edges().get(8).unwrap().vertex0().unwrap(), 1);
    assert_eq!(output.edges().get(8).unwrap().twin()?, 9);
    assert_eq!(output.edges().get(8).unwrap().next()?, 4);
    assert_eq!(output.edges().get(8).unwrap().prev()?, 12);
    let e = output.edges()[8];
    assert_eq!(output.edge_get_vertex1(e.id())?.unwrap(), 0);
    assert_eq!(output.edge_rot_next(e.id()).unwrap(), 13);
    assert_eq!(output.edge_rot_prev(e.id()).unwrap(), 10);
    assert!(output.edge_is_finite(e.id())?);
    assert!(!output.edge_is_infinite(e.id())?);
    assert!(e.is_linear());
    assert!(!e.is_curved());
    assert!(e.is_primary());
    assert!(!e.is_secondary());
    assert_eq!(output.edges().get(9).unwrap().cell()?, 4);
    assert_eq!(output.edges().get(9).unwrap().vertex0().unwrap(), 0);
    assert_eq!(output.edges().get(9).unwrap().twin()?, 8);
    assert_eq!(output.edges().get(9).unwrap().next()?, 10);
    assert_eq!(output.edges().get(9).unwrap().prev()?, 7);
    let e = output.edges()[9];
    assert_eq!(output.edge_get_vertex1(e.id())?.unwrap(), 1);
    assert_eq!(output.edge_rot_next(e.id()).unwrap(), 6);
    assert_eq!(output.edge_rot_prev(e.id()).unwrap(), 4);
    assert!(output.edge_is_finite(e.id())?);
    assert!(!output.edge_is_infinite(e.id())?);
    assert!(e.is_linear());
    assert!(!e.is_curved());
    assert!(e.is_primary());
    assert!(!e.is_secondary());
    assert_eq!(output.edges().get(10).unwrap().cell()?, 4);
    assert_eq!(output.edges().get(10).unwrap().vertex0().unwrap(), 1);
    assert_eq!(output.edges().get(10).unwrap().twin()?, 11);
    assert_eq!(output.edges().get(10).unwrap().next()?, 7);
    assert_eq!(output.edges().get(10).unwrap().prev()?, 9);
    let e = output.edges()[10];
    assert!(output.edge_get_vertex1(e.id())?.is_none());
    assert_eq!(output.edge_rot_next(e.id()).unwrap(), 8);
    assert_eq!(output.edge_rot_prev(e.id()).unwrap(), 13);
    assert!(!output.edge_is_finite(e.id())?);
    assert!(output.edge_is_infinite(e.id())?);
    assert!(e.is_linear());
    assert!(!e.is_curved());
    assert!(!e.is_primary());
    assert!(e.is_secondary());
    assert_eq!(output.edges().get(11).unwrap().cell()?, 5);
    assert!(output.edges().get(11).unwrap().vertex0().is_none());
    assert_eq!(output.edges().get(11).unwrap().twin()?, 10);
    assert_eq!(output.edges().get(11).unwrap().next()?, 13);
    assert_eq!(output.edges().get(11).unwrap().prev()?, 17);
    let e = output.edges()[11];
    assert_eq!(output.edge_get_vertex1(e.id())?.unwrap(), 1);
    assert_eq!(output.edge_rot_next(e.id()).unwrap(), 16);
    assert_eq!(output.edge_rot_prev(e.id()).unwrap(), 7);
    assert!(!output.edge_is_finite(e.id())?);
    assert!(output.edge_is_infinite(e.id())?);
    assert!(e.is_linear());
    assert!(!e.is_curved());
    assert!(!e.is_primary());
    assert!(e.is_secondary());
    assert_eq!(output.edges().get(12).unwrap().cell()?, 1);
    assert_eq!(output.edges().get(12).unwrap().vertex0().unwrap(), 3);
    assert_eq!(output.edges().get(12).unwrap().twin()?, 13);
    assert_eq!(output.edges().get(12).unwrap().next()?, 8);
    assert_eq!(output.edges().get(12).unwrap().prev()?, 1);
    let e = output.edges()[12];
    assert_eq!(output.edge_get_vertex1(e.id())?.unwrap(), 1);
    assert_eq!(output.edge_rot_next(e.id()).unwrap(), 0);
    assert_eq!(output.edge_rot_prev(e.id()).unwrap(), 17);
    assert!(output.edge_is_finite(e.id())?);
    assert!(!output.edge_is_infinite(e.id())?);
    assert!(!e.is_linear());
    assert!(e.is_curved());
    assert!(e.is_primary());
    assert!(!e.is_secondary());
    assert_eq!(output.edges().get(13).unwrap().cell()?, 5);
    assert_eq!(output.edges().get(13).unwrap().vertex0().unwrap(), 1);
    assert_eq!(output.edges().get(13).unwrap().twin()?, 12);
    assert_eq!(output.edges().get(13).unwrap().next()?, 17);
    assert_eq!(output.edges().get(13).unwrap().prev()?, 11);
    let e = output.edges()[13];
    assert_eq!(output.edge_get_vertex1(e.id())?.unwrap(), 3);
    assert_eq!(output.edge_rot_next(e.id()).unwrap(), 10);
    assert_eq!(output.edge_rot_prev(e.id()).unwrap(), 8);
    assert!(output.edge_is_finite(e.id())?);
    assert!(!output.edge_is_infinite(e.id())?);
    assert!(!e.is_linear());
    assert!(e.is_curved());
    assert!(e.is_primary());
    assert!(!e.is_secondary());
    assert_eq!(output.edges().get(14).unwrap().cell()?, 3);
    assert!(output.edges().get(14).unwrap().vertex0().is_none());
    assert_eq!(output.edges().get(14).unwrap().twin()?, 15);
    assert_eq!(output.edges().get(14).unwrap().next()?, 5);
    assert_eq!(output.edges().get(14).unwrap().prev()?, 6);
    let e = output.edges()[14];
    assert_eq!(output.edge_get_vertex1(e.id())?.unwrap(), 2);
    assert_eq!(output.edge_rot_next(e.id()).unwrap(), 7);
    assert_eq!(output.edge_rot_prev(e.id()).unwrap(), 3);
    assert!(!output.edge_is_finite(e.id())?);
    assert!(output.edge_is_infinite(e.id())?);
    assert!(e.is_linear());
    assert!(!e.is_curved());
    assert!(e.is_primary());
    assert!(!e.is_secondary());
    assert_eq!(output.edges().get(15).unwrap().cell()?, 2);
    assert_eq!(output.edges().get(15).unwrap().vertex0().unwrap(), 2);
    assert_eq!(output.edges().get(15).unwrap().twin()?, 14);
    assert_eq!(output.edges().get(15).unwrap().next()?, 3);
    assert_eq!(output.edges().get(15).unwrap().prev()?, 3);
    let e = output.edges()[15];
    assert!(output.edge_get_vertex1(e.id())?.is_none());
    assert_eq!(output.edge_rot_next(e.id()).unwrap(), 2);
    assert_eq!(output.edge_rot_prev(e.id()).unwrap(), 5);
    assert!(!output.edge_is_finite(e.id())?);
    assert!(output.edge_is_infinite(e.id())?);
    assert!(e.is_linear());
    assert!(!e.is_curved());
    assert!(e.is_primary());
    assert!(!e.is_secondary());
    assert_eq!(output.edges().get(16).unwrap().cell()?, 0);
    assert!(output.edges().get(16).unwrap().vertex0().is_none());
    assert_eq!(output.edges().get(16).unwrap().twin()?, 17);
    assert_eq!(output.edges().get(16).unwrap().next()?, 0);
    assert_eq!(output.edges().get(16).unwrap().prev()?, 0);
    let e = output.edges()[16];
    assert_eq!(output.edge_get_vertex1(e.id())?.unwrap(), 3);
    assert_eq!(output.edge_rot_next(e.id()).unwrap(), 1);
    assert_eq!(output.edge_rot_prev(e.id()).unwrap(), 11);
    assert!(!output.edge_is_finite(e.id())?);
    assert!(output.edge_is_infinite(e.id())?);
    assert!(e.is_linear());
    assert!(!e.is_curved());
    assert!(e.is_primary());
    assert!(!e.is_secondary());
    assert_eq!(output.edges().get(17).unwrap().cell()?, 5);
    assert_eq!(output.edges().get(17).unwrap().vertex0().unwrap(), 3);
    assert_eq!(output.edges().get(17).unwrap().twin()?, 16);
    assert_eq!(output.edges().get(17).unwrap().next()?, 11);
    assert_eq!(output.edges().get(17).unwrap().prev()?, 13);
    let e = output.edges()[17];
    assert!(output.edge_get_vertex1(e.id())?.is_none());
    assert_eq!(output.edge_rot_next(e.id()).unwrap(), 12);
    assert_eq!(output.edge_rot_prev(e.id()).unwrap(), 0);
    assert!(!output.edge_is_finite(e.id())?);
    assert!(output.edge_is_infinite(e.id())?);
    assert!(e.is_linear());
    assert!(!e.is_curved());
    assert!(e.is_primary());
    assert!(!e.is_secondary());
    Ok(())
}

#[test]
/// four segments in a loop
fn two_segments_8() -> Result<(), BvError> {
    let (output, _v, _s) = {
        let c: I = 300;
        let points = to_points::<I>(&[]);
        let segments = to_segments::<I>(&[
            [c, c, c, 200 + c],
            [c, 200 + c, 200 + c, 200 + c],
            [200 + c, 200 + c, 200 + c, c],
            [200 + c, c, c, c],
        ]);

        (
            Builder::<I>::default()
                .with_vertices(points.iter())?
                .with_segments(segments.iter())?
                .build()?,
            points,
            segments,
        )
    };

    assert_eq!(output.cells().len(), 8);
    let cell = output.cells()[0];
    assert_eq!(cell.id(), 0);
    let (source_index, cat) = cell.source_index_2();
    let p = retrieve_point(&_v, &_s, (source_index, cat));
    assert_eq!(p, Point { x: 300, y: 300 });
    assert!(!cell.is_degenerate());
    assert!(cell.contains_point());
    assert!(!cell.contains_segment());
    let cell = output.cells()[1];
    assert_eq!(cell.id(), 1);
    let (source_index, cat) = cell.source_index_2();
    assert_eq!(cat, SourceCategory::Segment);
    let p = retrieve_point(&_v, &_s, (source_index, cat));
    assert_eq!(p, Point { x: 300, y: 500 });
    assert!(!cell.is_degenerate());
    assert!(!cell.contains_point());
    assert!(cell.contains_segment());
    let cell = output.cells()[2];
    assert_eq!(cell.id(), 2);
    let (source_index, cat) = cell.source_index_2();
    let p = retrieve_point(&_v, &_s, (source_index, cat));
    assert_eq!(p, Point { x: 300, y: 500 });
    assert!(!cell.is_degenerate());
    assert!(cell.contains_point());
    assert!(!cell.contains_segment());
    let cell = output.cells()[3];
    assert_eq!(cell.id(), 3);
    let (source_index, cat) = cell.source_index_2();
    assert_eq!(cat, SourceCategory::Segment);
    let p = retrieve_point(&_v, &_s, (source_index, cat));
    assert_eq!(p, Point { x: 300, y: 300 });
    assert!(!cell.is_degenerate());
    assert!(!cell.contains_point());
    assert!(cell.contains_segment());
    let cell = output.cells()[4];
    assert_eq!(cell.id(), 4);
    let (source_index, cat) = cell.source_index_2();
    assert_eq!(cat, SourceCategory::Segment);
    let p = retrieve_point(&_v, &_s, (source_index, cat));
    assert_eq!(p, Point { x: 500, y: 500 });
    assert!(!cell.is_degenerate());
    assert!(!cell.contains_point());
    assert!(cell.contains_segment());
    let cell = output.cells()[5];
    assert_eq!(cell.id(), 5);
    let (source_index, cat) = cell.source_index_2();
    let p = retrieve_point(&_v, &_s, (source_index, cat));
    assert_eq!(p, Point { x: 500, y: 300 });
    assert!(!cell.is_degenerate());
    assert!(cell.contains_point());
    assert!(!cell.contains_segment());
    let cell = output.cells()[6];
    assert_eq!(cell.id(), 6);
    let (source_index, cat) = cell.source_index_2();
    assert_eq!(cat, SourceCategory::Segment);
    let p = retrieve_point(&_v, &_s, (source_index, cat));
    assert_eq!(p, Point { x: 500, y: 300 });
    assert!(!cell.is_degenerate());
    assert!(!cell.contains_point());
    assert!(cell.contains_segment());
    let cell = output.cells()[7];
    assert_eq!(cell.id(), 7);
    let (source_index, cat) = cell.source_index_2();
    let p = retrieve_point(&_v, &_s, (source_index, cat));
    assert_eq!(p, Point { x: 500, y: 500 });
    assert!(!cell.is_degenerate());
    assert!(cell.contains_point());
    assert!(!cell.contains_segment());
    assert_eq!(output.vertices().len(), 5);
    assert_eq!(output.edges().len(), 24);
    let v = output.vertices()[0];
    assert!(almost_equal(v.x(), 300.0000000, v.y(), 300.0000000));
    assert_eq!(v.get_incident_edge()?, 7);
    let v = output.vertices()[1];
    assert!(almost_equal(v.x(), 300.0000000, v.y(), 500.0000000));
    assert_eq!(v.get_incident_edge()?, 11);
    let v = output.vertices()[2];
    assert!(almost_equal(v.x(), 500.0000000, v.y(), 300.0000000));
    assert_eq!(v.get_incident_edge()?, 17);
    let v = output.vertices()[3];
    assert!(almost_equal(v.x(), 400.0000000, v.y(), 400.0000000));
    assert_eq!(v.get_incident_edge()?, 19);
    let v = output.vertices()[4];
    assert!(almost_equal(v.x(), 500.0000000, v.y(), 500.0000000));
    assert_eq!(v.get_incident_edge()?, 23);
    Ok(())
}