//! Comprehensive tests for tangent-based rightmost edge selection
//!
//! This module contains extensive tests for the enhanced cycle detection algorithm
//! that properly handles tangent directions for both arcs and line segments.
use super::find_cycles::*;
use togo::prelude::*;
#[cfg(test)]
mod tangent_direction_tests {
use super::*;
#[test]
fn test_arc_tangent_calculation_basic() {
// Test basic arc tangent calculation with a simple circular arc
let start_point = point(10.0, 0.0);
let end_point = point(0.0, 10.0);
let center = point(0.0, 0.0);
// Create an arc from (10,0) to (0,10) with center at origin and radius 10
let arc_segment = arc(start_point, end_point, center, 10.0);
let tangents = arc_segment.tangents();
// At start (right side), tangent should point roughly upward
// At end (top), tangent should point roughly leftward
assert!(tangents[0].y > 0.0, "Start tangent should point upward");
assert!(tangents[1].x < 0.0, "End tangent should point leftward");
}
#[test]
fn test_arc_tangent_vs_line_tangent() {
// Create an arc and a line segment that meet at the same point
let meeting_point = point(10.0, 0.0);
// Circular arc - quarter circle from (10,0) to (0,10)
let arc_segment = arc(meeting_point, point(0.0, 10.0), point(0.0, 0.0), 10.0);
// Line segment from (10,0) going horizontally right
let line = arcseg(meeting_point, point(20.0, 0.0));
let arc_tangents = arc_segment.tangents();
let line_tangents = line.tangents();
// Arc tangent at start should be roughly vertical (pointing up)
assert!(arc_tangents[0].y > 0.0, "Arc start tangent should point upward");
assert!(arc_tangents[0].x.abs() < 0.1, "Arc start tangent should be mostly vertical");
// Line tangent should be horizontal (pointing right)
assert!(line_tangents[0].x > 0.0, "Line tangent should point right");
assert!(line_tangents[0].y.abs() < 1e-10, "Line tangent should be horizontal");
}
#[test]
fn test_rightmost_selection_arc_vs_line() {
// Test scenario where an arc and line segment meet at a vertex
// and we need to select the rightmost one
let vertex = point(10.0, 10.0);
let arcs = vec![
// Line going left from vertex
arcseg(vertex, point(0.0, 10.0)),
// Line going up from vertex
arcseg(vertex, point(10.0, 20.0)),
// Line going right from vertex
arcseg(vertex, point(20.0, 10.0)),
// Line going down from vertex to potentially close cycle
arcseg(point(20.0, 10.0), point(20.0, 0.0)),
arcseg(point(20.0, 0.0), point(0.0, 0.0)),
arcseg(point(0.0, 0.0), point(0.0, 10.0)),
];
let cycles = find_non_intersecting_cycles(&arcs);
// Should find some valid cycles using proper tangent-based selection
assert!(!cycles.is_empty(), "Should find cycles with proper tangent selection");
for cycle in &cycles {
assert!(cycle.len() >= 3, "Each cycle should have at least 3 arcs");
}
}
#[test]
fn test_clockwise_vs_counterclockwise_arcs() {
// Test arcs with different orientations meeting at a point
let center = point(0.0, 0.0);
let meeting_point = point(10.0, 0.0);
let arcs = vec![
// Create some arcs to form cycles
arc(meeting_point, point(0.0, 10.0), center, 10.0), // quarter circle
arcseg(point(0.0, 10.0), point(-10.0, 0.0)), // line
arc(point(-10.0, 0.0), meeting_point, center, 10.0), // quarter circle back
];
let cycles = find_non_intersecting_cycles(&arcs);
// The algorithm should handle both orientations correctly
for cycle in &cycles {
assert!(cycle.len() >= 3, "Each cycle should have at least 3 arcs");
}
}
#[test]
fn test_mixed_arcs_and_segments_cycle() {
// Test cycle with both actual arcs and line segments
let arcs = vec![
// Start with an arc
arc(point(5.0, 0.0), point(0.0, 5.0), point(0.0, 0.0), 5.0),
// Line segment
arcseg(point(0.0, 5.0), point(-5.0, 0.0)),
// Another arc
arc(point(-5.0, 0.0), point(0.0, -5.0), point(0.0, 0.0), 5.0),
// Close with line segment
arcseg(point(0.0, -5.0), point(5.0, 0.0)),
];
let cycles = find_non_intersecting_cycles(&arcs);
// Should find the mixed arc/segment cycle
assert!(!cycles.is_empty(), "Should find cycle with mixed arc types");
for cycle in &cycles {
assert!(cycle.len() >= 3, "Each cycle should have at least 3 arcs");
}
}
#[test]
fn test_semicircle_arcs() {
// Test with semicircle arcs
let arcs = vec![
// Upper semicircle
arc(point(-5.0, 0.0), point(5.0, 0.0), point(0.0, 0.0), 5.0),
// Lower semicircle (completing the circle)
arc(point(5.0, 0.0), point(-5.0, 0.0), point(0.0, 0.0), 5.0),
];
let cycles = find_non_intersecting_cycles(&arcs);
// Should find the complete circle as a cycle
if !cycles.is_empty() {
assert!(cycles[0].len() >= 2, "Circle should have at least 2 arcs");
}
}
#[test]
fn test_multiple_arcs_same_vertex_tangent_ordering() {
// Test case with multiple arcs meeting at the same vertex
// to verify tangent-based rightmost selection
let vertex = point(0.0, 0.0);
let arcs = vec![
// Line going east
arcseg(vertex, point(10.0, 0.0)),
// Line going north
arcseg(vertex, point(0.0, 10.0)),
// Line going west
arcseg(vertex, point(-10.0, 0.0)),
// Line going south to complete a cycle
arcseg(vertex, point(0.0, -10.0)),
// Connect the endpoints
arcseg(point(10.0, 0.0), point(0.0, 10.0)),
arcseg(point(0.0, 10.0), point(-10.0, 0.0)),
arcseg(point(-10.0, 0.0), point(0.0, -10.0)),
arcseg(point(0.0, -10.0), point(10.0, 0.0)),
];
let cycles = find_non_intersecting_cycles(&arcs);
// Should be able to find cycles with proper tangent-based ordering
for cycle in &cycles {
assert!(cycle.len() >= 3);
}
}
}
#[cfg(test)]
mod complex_intersection_tests {
use super::*;
#[test]
fn test_star_intersection_with_arcs() {
// Create a star pattern with both arcs and line segments
let center = point(0.0, 0.0);
let radius = 10.0;
let arcs = vec![
// Lines radiating from center
arcseg(center, point(radius, 0.0)),
arcseg(center, point(0.0, radius)),
arcseg(center, point(-radius, 0.0)),
arcseg(center, point(0.0, -radius)),
// Connect outer points to form cycles
arcseg(point(radius, 0.0), point(0.0, radius)),
arcseg(point(0.0, radius), point(-radius, 0.0)),
arcseg(point(-radius, 0.0), point(0.0, -radius)),
arcseg(point(0.0, -radius), point(radius, 0.0)),
];
let cycles = find_non_intersecting_cycles(&arcs);
// Should find multiple cycles in this complex pattern
assert!(!cycles.is_empty(), "Should find cycles in star pattern");
for cycle in &cycles {
assert!(cycle.len() >= 3, "Each cycle should have at least 3 arcs");
}
}
#[test]
fn test_figure_eight_with_curved_segments() {
// Create a figure-8 pattern using actual arcs
let arcs = vec![
// Left loop with arcs
arc(point(0.5, 0.5), point(1.0, 0.0), point(0.5, 0.0), 5.0), // top arc
arcseg(point(1.0, 0.0), point(0.0, 0.0)), // shared segment
arc(point(0.0, 0.0), point(0.5, 0.5), point(0.5, 0.0), 5.0), // bottom arc
// Right loop with arcs
arc(point(1.0, 0.0), point(1.5, 0.5), point(1.5, 0.0), 5.0), // top arc
arcseg(point(1.5, 0.5), point(2.0, 0.0)), // side segment
arc(point(2.0, 0.0), point(1.0, 0.0), point(1.5, 0.0), 5.0), // bottom arc
];
let cycles = find_non_intersecting_cycles(&arcs);
// Should find cycles in the figure-8 pattern with actual arcs
assert!(!cycles.is_empty(), "Should find cycles in curved figure-8");
for cycle in &cycles {
assert!(cycle.len() >= 3, "Each cycle should have at least 3 arcs");
}
}
#[test]
fn test_multiple_concentric_arcs() {
// Test with multiple concentric circular arcs
let center = point(0.0, 0.0);
let arcs = vec![
// Inner circle with 4 arcs
arc(point(2.0, 0.0), point(0.0, 2.0), center),
arc(point(0.0, 2.0), point(-2.0, 0.0), center),
arc(point(-2.0, 0.0), point(0.0, -2.0), center),
arc(point(0.0, -2.0), point(2.0, 0.0), center),
// Outer circle with 4 arcs
arc(point(4.0, 0.0), point(0.0, 4.0), center),
arc(point(0.0, 4.0), point(-4.0, 0.0), center),
arc(point(-4.0, 0.0), point(0.0, -4.0), center),
arc(point(0.0, -4.0), point(4.0, 0.0), center),
];
let cycles = find_non_intersecting_cycles(&arcs);
// Should find both circular cycles
assert!(!cycles.is_empty(), "Should find cycles in concentric arcs");
for cycle in &cycles {
assert!(cycle.len() >= 3, "Each cycle should have at least 3 arcs");
}
}
#[test]
fn test_mixed_arc_types_complex_junction() {
// Test a complex junction with different types of arcs
let junction = point(0.0, 0.0);
let arcs = vec![
// Line segments radiating from junction
arcseg(junction, point(10.0, 0.0)),
arcseg(junction, point(-10.0, 0.0)),
arcseg(junction, point(0.0, 10.0)),
arcseg(junction, point(0.0, -10.0)),
// Connect endpoints to form potential cycles
arcseg(point(10.0, 0.0), point(0.0, 10.0)),
arcseg(point(0.0, 10.0), point(-10.0, 0.0)),
arcseg(point(-10.0, 0.0), point(0.0, -10.0)),
arcseg(point(0.0, -10.0), point(10.0, 0.0)),
];
let cycles = find_non_intersecting_cycles(&arcs);
// Complex junction should produce some cycles
for cycle in &cycles {
assert!(cycle.len() >= 3, "Each cycle should have at least 3 arcs");
}
}
}
#[cfg(test)]
mod edge_case_tests {
use super::*;
#[test]
fn test_nearly_collinear_tangents() {
// Test case where tangents are nearly collinear
// This is important for numerical stability
let arcs = vec![
arcseg(point(0.0, 0.0), point(1.0, 0.001)), // Nearly horizontal
arcseg(point(0.0, 0.0), point(1.0, -0.001)), // Nearly horizontal, opposite side
arcseg(point(0.0, 0.0), point(-1.0, 0.0)), // Exactly horizontal
];
let cycles = find_non_intersecting_cycles(&arcs);
// Should handle nearly collinear tangents without crashing
// May or may not find cycles depending on the exact geometry
for cycle in &cycles {
assert!(cycle.len() >= 3);
}
}
#[test]
fn test_zero_radius_arc() {
// Test degenerate case with a simple square
let arcs = vec![
arcseg(point(0.0, 0.0), point(1.0, 0.0)),
arcseg(point(1.0, 0.0), point(1.0, 1.0)),
arcseg(point(1.0, 1.0), point(0.0, 1.0)),
arcseg(point(0.0, 1.0), point(0.0, 0.0)),
];
let cycles = find_non_intersecting_cycles(&arcs);
// Should handle basic square geometry gracefully
assert!(!cycles.is_empty(), "Should find the square cycle");
for cycle in &cycles {
assert!(cycle.len() >= 3);
}
}
#[test]
fn test_full_circle_arc() {
// Test a simple cycle with circular arcs
let arcs = vec![
arc(point(1.0, 0.0), point(0.0, 1.0), point(0.0, 0.0), 5.0),
arc(point(0.0, 1.0), point(-1.0, 0.0), point(0.0, 0.0), 5.0),
arc(point(-1.0, 0.0), point(0.0, -1.0), point(0.0, 0.0), 5.0),
arc(point(0.0, -1.0), point(1.0, 0.0), point(0.0, 0.0), 5.0),
];
let cycles = find_non_intersecting_cycles(&arcs);
// Should form a circular cycle
assert!(!cycles.is_empty(), "Should find the circular cycle");
for cycle in &cycles {
assert!(cycle.len() >= 3, "Cycle should have at least 3 segments");
}
}
#[test]
fn test_arc_tangent_direction_edge_cases() {
// Test edge cases where arc tangents might be challenging to compute
let arcs = vec![
// Very small arc
arc(point(1.0, 0.0), point(0.999, 0.045), point(1.0, 0.0), 5.0),
// Nearly straight arc
arc(point(0.0, 0.0), point(2.0, 0.001), point(1.0, 1000.0), 5.0),
];
let cycles = find_non_intersecting_cycles(&arcs);
// Should handle edge cases without crashing
for cycle in &cycles {
assert!(cycle.len() >= 3);
}
}
#[test]
fn test_overlapping_arcs_different_radii() {
// Test arcs that could represent different sized shapes
let center = point(0.0, 0.0);
let arcs = vec![
// Inner square
arcseg(point(-1.0, -1.0), point(1.0, -1.0)),
arcseg(point(1.0, -1.0), point(1.0, 1.0)),
arcseg(point(1.0, 1.0), point(-1.0, 1.0)),
arcseg(point(-1.0, 1.0), point(-1.0, -1.0)),
// Outer square
arcseg(point(-2.0, -2.0), point(2.0, -2.0)),
arcseg(point(2.0, -2.0), point(2.0, 2.0)),
arcseg(point(2.0, 2.0), point(-2.0, 2.0)),
arcseg(point(-2.0, 2.0), point(-2.0, -2.0)),
];
let cycles = find_non_intersecting_cycles(&arcs);
// Should handle nested squares
for cycle in &cycles {
assert!(cycle.len() >= 3);
}
}
#[test]
fn test_very_small_arcs() {
// Test with very small arcs to check numerical precision
let epsilon = 1e-6; // Use larger epsilon for better numerical stability
let arcs = vec![
arcseg(point(0.0, 0.0), point(1.0, 0.0)),
arcseg(point(1.0, 0.0), point(1.0, epsilon)),
arcseg(point(1.0, epsilon), point(0.0, epsilon)),
arcseg(point(0.0, epsilon), point(0.0, 0.0)),
];
let cycles = find_non_intersecting_cycles(&arcs);
// Should handle very small arcs without numerical issues
for cycle in &cycles {
assert!(cycle.len() >= 3);
}
}
}
#[cfg(test)]
mod performance_tests {
use super::*;
#[test]
fn test_large_number_of_intersecting_arcs() {
// Test performance with many arcs intersecting at a central point
let center = point(0.0, 0.0);
let mut arcs = Vec::new();
// Create many lines radiating from center
for i in 0..8 { // Reduced number for simpler test
let angle = 2.0 * std::f64::consts::PI * (i as f64) / 8.0;
let endpoint = point(10.0 * angle.cos(), 10.0 * angle.sin());
arcs.push(arcseg(center, endpoint));
}
// Add some connecting segments to form potential cycles
for i in 0..8 {
let angle1 = 2.0 * std::f64::consts::PI * (i as f64) / 8.0;
let angle2 = 2.0 * std::f64::consts::PI * ((i + 1) as f64) / 8.0;
let point1 = point(10.0 * angle1.cos(), 10.0 * angle1.sin());
let point2 = point(10.0 * angle2.cos(), 10.0 * angle2.sin());
arcs.push(arcseg(point1, point2));
}
let start_time = std::time::Instant::now();
let cycles = find_non_intersecting_cycles(&arcs);
let duration = start_time.elapsed();
// Should complete in reasonable time (less than 1 second for this size)
assert!(duration < std::time::Duration::from_secs(1),
"Algorithm should complete quickly for moderately complex graphs");
for cycle in &cycles {
assert!(cycle.len() >= 3);
}
}
#[test]
fn test_deeply_nested_cycles() {
// Test with multiple nested cycles to verify algorithm correctness
let mut arcs = Vec::new();
// Create concentric squares
for &radius in [2.0, 4.0, 6.0, 8.0].iter() {
arcs.push(arcseg(point(-radius, -radius), point(radius, -radius)));
arcs.push(arcseg(point(radius, -radius), point(radius, radius)));
arcs.push(arcseg(point(radius, radius), point(-radius, radius)));
arcs.push(arcseg(point(-radius, radius), point(-radius, -radius)));
}
let cycles = find_non_intersecting_cycles(&arcs);
// Should find multiple independent cycles
assert!(!cycles.is_empty(), "Should find cycles in nested squares");
for cycle in &cycles {
assert!(cycle.len() >= 4, "Each square cycle should have 4 sides");
}
}
}
#[cfg(test)]
mod regression_tests {
use super::*;
#[test]
fn test_original_figure_eight_still_works() {
// Ensure the original figure-8 test case still works after our changes
let arcs = vec![
// Left square
arcseg(point(0.0, 0.0), point(1.0, 0.0)),
arcseg(point(1.0, 0.0), point(1.0, 1.0)),
arcseg(point(1.0, 1.0), point(0.0, 1.0)),
arcseg(point(0.0, 1.0), point(0.0, 0.0)),
// Right square (shares edge with left)
arcseg(point(1.0, 0.0), point(2.0, 0.0)),
arcseg(point(2.0, 0.0), point(2.0, 1.0)),
arcseg(point(2.0, 1.0), point(1.0, 1.0)),
];
let cycles = find_non_intersecting_cycles(&arcs);
assert!(!cycles.is_empty(), "Should still find cycles in figure-8");
for cycle in &cycles {
assert!(cycle.len() >= 3);
}
}
#[test]
fn test_simple_triangle_still_works() {
// Test that basic functionality still works
let arcs = vec![
arcseg(point(0.0, 0.0), point(1.0, 0.0)),
arcseg(point(1.0, 0.0), point(0.5, 1.0)),
arcseg(point(0.5, 1.0), point(0.0, 0.0)),
];
let cycles = find_non_intersecting_cycles(&arcs);
assert_eq!(cycles.len(), 1, "Should find exactly one triangle cycle");
assert_eq!(cycles[0].len(), 3, "Triangle should have 3 sides");
}
#[test]
fn test_simple_square_still_works() {
// Test that basic functionality still works
let arcs = vec![
arcseg(point(0.0, 0.0), point(1.0, 0.0)),
arcseg(point(1.0, 0.0), point(1.0, 1.0)),
arcseg(point(1.0, 1.0), point(0.0, 1.0)),
arcseg(point(0.0, 1.0), point(0.0, 0.0)),
];
let cycles = find_non_intersecting_cycles(&arcs);
assert_eq!(cycles.len(), 1, "Should find exactly one square cycle");
assert_eq!(cycles[0].len(), 4, "Square should have 4 sides");
}
#[test]
fn test_premature_edge_marking_regression() {
// Regression test for bug where edges were marked as used before cycle completion
// Create a diamond pattern where early marking would prevent finding cycles
let mut arcs = Vec::new();
arcs.push(arcseg(point(0.0, 0.0), point(1.0, 1.0))); // top-left
arcs.push(arcseg(point(1.0, 1.0), point(2.0, 0.0))); // top-right
arcs.push(arcseg(point(2.0, 0.0), point(1.0, -1.0))); // bottom-right
arcs.push(arcseg(point(1.0, -1.0), point(0.0, 0.0))); // bottom-left
// This should find exactly one cycle
let cycles = find_non_intersecting_cycles(&arcs);
assert_eq!(cycles.len(), 1, "Should find exactly one cycle");
assert_eq!(cycles[0].len(), 4, "Cycle should have 4 edges");
}
#[test]
fn test_circular_arc_regression() {
// Test that circular arcs work correctly in cycles
let arcs = vec![
// Half circle top
arc(point(-2.0, 0.0), point(2.0, 0.0), point(0.0, 0.0), 5.0),
// Half circle bottom to complete the circle
arc(point(2.0, 0.0), point(-2.0, 0.0), point(0.0, 0.0), 5.0),
];
let cycles = find_non_intersecting_cycles(&arcs);
// Should find the circular cycle
if !cycles.is_empty() {
assert!(cycles[0].len() >= 2, "Circle should have at least 2 arcs");
}
}
}