#!/usr/bin/perl
use strict;
use warnings;
use Math::Trig;

# Function to evaluate a point on a cubic Bezier curve at parameter t
sub evaluate_bezier {
    my ($p0, $p1, $p2, $p3, $t) = @_;
    my $mt = 1 - $t;
    my $mt2 = $mt * $mt;
    my $mt3 = $mt2 * $mt;
    my $t2 = $t * $t;
    my $t3 = $t2 * $t;
    
    my $x = $mt3 * $p0->[0] + 3 * $mt2 * $t * $p1->[0] + 3 * $mt * $t2
+ * $p2->[0] + $t3 * $p3->[0];
    my $y = $mt3 * $p0->[1] + 3 * $mt2 * $t * $p1->[1] + 3 * $mt * $t2
+ * $p2->[1] + $t3 * $p3->[1];
    
    return [$x, $y];
}

# Function to find circle passing through three points
sub find_circle_from_three_points {
    my ($p1, $p2, $p3) = @_;
    
    # Check if points are collinear (or too close to collinear)
    my $D = 2 * ($p1->[0] * ($p2->[1] - $p3->[1]) + 
                 $p2->[0] * ($p3->[1] - $p1->[1]) + 
                 $p3->[0] * ($p1->[1] - $p2->[1]));
    
    if (abs($D) < 1e-10) {
        # Points are collinear, can't form a unique circle
        return (undef, undef);
    }
    
    # Calculate squared distances
    my $p1_sq = $p1->[0]**2 + $p1->[1]**2;
    my $p2_sq = $p2->[0]**2 + $p2->[1]**2;
    my $p3_sq = $p3->[0]**2 + $p3->[1]**2;
    
    # Calculate circle center
    my $cx = ($p1_sq * ($p2->[1] - $p3->[1]) + 
              $p2_sq * ($p3->[1] - $p1->[1]) + 
              $p3_sq * ($p1->[1] - $p2->[1])) / $D;
    
    my $cy = ($p1_sq * ($p3->[0] - $p2->[0]) + 
              $p2_sq * ($p1->[0] - $p3->[0]) + 
              $p3_sq * ($p2->[0] - $p1->[0])) / $D;
    
    # Calculate radius
    my $center = [$cx, $cy];
    my $radius = sqrt(($p1->[0] - $cx)**2 + ($p1->[1] - $cy)**2);
    
    return ($center, $radius);
}

# Function to compute arc angles for the circular arc
sub compute_arc_angles {
    my ($center, $start_point, $end_point) = @_;
    
    # Calculate angles from center to points
    my $start_angle = atan2($start_point->[1] - $center->[1], 
                            $start_point->[0] - $center->[0]);
    my $end_angle = atan2($end_point->[1] - $center->[1], 
                          $end_point->[0] - $center->[0]);
    
    # Ensure proper orientation (counter-clockwise)
    if ($start_angle > $end_angle) {
        $end_angle += 2 * pi if ($end_angle - $start_angle) < -pi;
    } else {
        $start_angle += 2 * pi if ($end_angle - $start_angle) > pi;
    }
    
    return ($start_angle, $end_angle);
}

# Main function to approximate Bezier curve with circular arcs
sub approximate_bezier_with_arcs {
    my ($p0, $p1, $p2, $p3, $num_segments) = @_;
    my @arcs = ();
    
    for (my $i = 0; $i < $num_segments; $i++) {
        # Sample three points from this segment of the Bezier curve
        my $t_start = $i / $num_segments;
        my $t_mid = ($i + 0.5) / $num_segments;
        my $t_end = ($i + 1) / $num_segments;
        
        my $start_point = evaluate_bezier($p0, $p1, $p2, $p3, $t_start
+);
        my $mid_point = evaluate_bezier($p0, $p1, $p2, $p3, $t_mid);
        my $end_point = evaluate_bezier($p0, $p1, $p2, $p3, $t_end);
        
        # Find circle passing through these points
        my ($center, $radius) = find_circle_from_three_points(
            $start_point, $mid_point, $end_point);
        
        # If points are collinear, use a line segment instead
        if (!defined $center) {
            push @arcs, {
                type => 'line',
                start => $start_point,
                end => $end_point
            };
            next;
        }
        
        # Compute start and end angles for the arc
        my ($start_angle, $end_angle) = compute_arc_angles(
            $center, $start_point, $end_point);
        
        # Store the arc parameters
        push @arcs, {
            type => 'arc',
            center => $center,
            radius => $radius,
            start_angle => $start_angle,
            end_angle => $end_angle,
            start_point => $start_point,
            end_point => $end_point
        };
    }
    
    return \@arcs;
}

# Example usage
my $p0 = [0, 0];   # Start point
my $p1 = [1, 2];   # Control point 1
my $p2 = [3, 3];   # Control point 2
my $p3 = [4, 1];   # End point

my $arcs = approximate_bezier_with_arcs($p0, $p1, $p2, $p3, 3);

# Print arc approximation results
foreach my $arc (@$arcs) {
    if ($arc->{type} eq 'arc') {
        printf "Arc: center=(%.2f, %.2f), radius=%.2f, angles=%.2f to 
+%.2f\n",
            $arc->{center}->[0], $arc->{center}->[1], $arc->{radius},
            $arc->{start_angle} * 180/pi, $arc->{end_angle} * 180/pi;
    } else {
        printf "Line: from (%.2f, %.2f) to (%.2f, %.2f)\n",
            $arc->{start}->[0], $arc->{start}->[1],
            $arc->{end}->[0], $arc->{end}->[1];
    }
}
[download]