Math-Intersection-Circle-Line
view release on metacpan or search on metacpan
lib/Math/Intersection/Circle/Line.pm view on Meta::CPAN
# a == (r*r-ð—¿*ð—¿ + ð—¹*ð—¹)/ (2*ð—¹)
#
# The distance ð—® at right angles to ð—Ÿ to an intersection is sqrt(r*r-a*a)
#
# The unit vector ð•• == (ð•©, ð•ª) along line ð—Ÿ from (x,y) to (ð˜…, ð˜†) is the unit in
# direction: (ð˜…-x, ð˜†-y)
#
# The unit vectors d, ð—± at right angles to ð—Ÿ are (-ð•ª, ð•©) and (ð•ª, -ð•©)
#-------------------------------------------------------------------------------
sub intersectionCircles(&$$$$$$)
{my ($sub, # Sub routine to process intersection
$x, $y, $r, # First circle centre, radius
$ð˜…, $ð˜†, $ð—¿) = @_; # Second circle centre, radius
@_ == 7 or confess "Wrong number of parameters";
return &$sub("Duplicate circles!") if # Complain if the two circles are in fact the same circle within the definition of nearness
near($x, $ð˜…) and near($y, $ð˜†) and near($r, $ð—¿);
my ($ð•, $ð•) = ($𘅠- $x, $𘆠- $y); # Vector between centres
my $ð—¹ = vectorLength($ð•, $ð•); # Distance between centres
return &$sub("No intersection!") if $ð—¹ > $r + $ð—¿ or $ð—¹ < abs($r - $ð—¿); # The circles are too far apart or too close to intersect
lib/Math/Intersection/Circle/Line.pm view on Meta::CPAN
#
# ð—žnown: two circles specified by ($x, $y, $r) and ($ð˜…, $ð˜†, $ð—¿)
#
# ð—™ind: the area of intersection expressed as a fraction of the area
# of the smaller circle
#
# ð— ethod: the area of a triangle is (base * height) / 2, the area of a slice is
# ð°ð—¿ð—¿/2 where ð° is the angle of a slice.
#-------------------------------------------------------------------------------
sub intersectionCirclesArea(&$$$$$$)
{my ($sub, # Sub routine to process area
$x, $y, $r, # First circle centre, radius
$ð˜…, $ð˜†, $ð—¿) = @_; # Second circle centre, radius
@_ == 7 or confess "Wrong number of parameters";
near($r) and confess "Radius of first circle is too small!";
near($ð—¿) and confess "Radius of second circle is too small!";
my $l = vectorLength($𘅠- $x, $𘆠- $y); # Distance between centres
return &$sub(0) if $l >= $r + $ð—¿; # The circles are too far apart to overlap
my $ð•£ = $r < $ð—¿ ? $r : $ð—¿; # Radius of smaller circle
return &$sub(1) if $l <= abs($r - $ð—¿); # The larger circle overlaps the smaller circle completely
lib/Math/Intersection/Circle/Line.pm view on Meta::CPAN
#
# ð—žnown: two points on the line ð—Ÿ such that: ð—¹ = (ð˜…, ð˜†), ð• = (ð•©, ð•ª) and the
# specified point ð—½ = (x, y).
#
# ð—™ind ð—° the point on ð—Ÿ closest to ð—½.
#
# ð— ethod: a circle with centre ð—¹ through ð—½ will intersect a circle with centre ð•
# through ð—½ at ð—¾. ð—° is then the average of ð—½ and ð—¾.
#-------------------------------------------------------------------------------
sub intersectionLinePoint(&$$$$$$)
{my ($sub, # Sub routine to process intersection
$ð˜…, $ð˜†, $ð•©, $ð•ª, # Two points on line ð—¹
$x, $y) = @_; # The point ð—½
@_ == 7 or confess "Wrong number of parameters";
near($ð˜…, $ð•©) and near($ð˜†, $ð•ª) and confess "Points on line are too close!"; # Line not well defined
return &$sub($x, $y) if near($x, $ð˜…) && near($y, $ð˜†) or # Point in question is near an end of the line segment
near($x, $ð•©) && near($y, $ð•ª);
return &$sub($x, $y) if threeCollinearPoints($ð˜…, $ð˜†, $ð•©, $ð•ª, $x, $y); # Collinear
# Points known not to be collinear
my $𗿠= vectorLength($𘅠- $x, $𘆠- $y); # Radius of first circle
my $𕣠= vectorLength($𕩠- $x, $𕪠- $y); # Radius of second circle
intersectionCircles
{return &$sub(@_) if @_ == 2; # Point is on line
my ($x, $y, $ð˜…, $ð˜†) = @_;
&$sub(($x+$ð˜…) / 2, ($y+$ð˜†) / 2) # Average intersection of intersection points
} $ð˜…, $ð˜†, $ð—¿, $ð•©, $ð•ª, $ð•£;
}
sub unsignedDistanceFromLineToPoint(&$$$$$$) # Unsigned distance from point to line
{my ($sub, $ð˜…, $ð˜†, $ð•©, $ð•ª, $x, $y) = @_; # Parameters are the same as for intersectionLinePoint()
@_ == 7 or confess "Wrong number of parameters";
intersectionLinePoint {&$sub(&vectorLength($x, $y, @_))} $ð˜…,$ð˜†, $ð•©,$ð•ª, $x,$y; # Distance from point to nearest point on line
}
#-------------------------------------------------------------------------------
# ð—œntersection of two lines
#
# ð—žnown: two lines l specified by two points ð—¹ = (ð˜…, ð˜†), ð• = (ð•©, ð•ª) and
# L specified by two points ð—Ÿ = (ð—«, ð—¬), 𕃠= (ð•, ð•)
# ð—™ind ð—° the point where the two lines intersect else $sub is called empty
#
# ð— ethod: Let the closest point to point ð—Ÿ on line l be ð—® and the closest point
# to point ð—® on line L be ð—¯. Lð—®ð—¯ is similar to Lð—®ð—°.
#-------------------------------------------------------------------------------
sub intersectionLines(&$$$$$$$$)
{my ($sub, # Sub routine to process intersection
$ð˜…, $ð˜†, $ð•©, $ð•ª, # Two points on line l
$ð—«, $ð—¬, $ð•, $ð•) = @_; # Two points on line L
@_ == 9 or confess "Wrong number of parameters";
near($ð˜…, $ð•©) and near($ð˜†, $ð•ª) and confess "Points on first line are too close!";
near($ð—«, $ð•) and near($ð—¬, $ð•) and confess "Points on second line are too close!";
return &$sub("Parallel lines!") if # Lines are parallel if they have the same gradient
near(atan2($ð˜†-$ð•ª, $ð˜…-$ð•©), atan2($ð—¬-$ð•, $ð—«-$ð•));
intersectionLinePoint # Find ð—®
lib/Math/Intersection/Circle/Line.pm view on Meta::CPAN
# at which the line touches the circle or report that there are no points in
# common.
#
# ð— ethod: If the line crosses the circle we can draw an isosceles triangle from
# the centre of the circle to the points of intersection, with the line forming
# the base of said triangle. The centre of the base is the closest point on the
# line to the centre of the circle. The line is at right angles to the line from
# the centre of the circle to the centre of the base.
#-------------------------------------------------------------------------------
sub intersectionCircleLine(&$$$$$$$)
{my ($sub, # Sub routine to process intersection
$x, $y, $r, # Circle centre, radius
$ð˜…, $ð˜†, $ð•©, $ð•ª) = @_; # Line goes through these two points
@_ == 8 or confess "Wrong number of parameters";
near($ð˜…, $ð•©) and near($ð˜†, $ð•ª) and confess "Points on line are too close!";
if (near($r)) # Zero radius circle
{return &$sub($x, $y) if threeCollinearPoints($x, $y, $ð˜…, $ð˜†, $ð•©, $ð•ª); # Line passes through the centre of the circle
confess "Radius is too small!";
}
lib/Math/Intersection/Circle/Line.pm view on Meta::CPAN
#-------------------------------------------------------------------------------
# ð—”rea of intersection of a circle with a line
#
# ð—žnown: a circle specified by its centre (x, y), and radius (r)
# and a line that passes through points: ($ð˜…, $ð˜†) and ($ð•©, $ð•ª).
# ð—™ind: the area of the smallest lune as a fraction of the area of the circle
# ð— ethod:
#-------------------------------------------------------------------------------
sub intersectionCircleLineArea(&$$$$$$$)
{my ($sub, # Sub routine to process area
$x, $y, $r, # Circle centre, radius
$ð˜…, $ð˜†, $ð•©, $ð•ª) = @_; # Line goes through these two points
@_ == 8 or confess "Wrong number of parameters";
near($ð˜…, $ð•©) and near($ð˜†, $ð•ª) and confess "Points on line are too close!";
near($r) and confess "Radius is too small!";
intersectionCircleLine
{return &$sub(0) if @_ < 4;
my ($X, $Y, $ð—«, $ð—¬) = @_; # Intersection points
lib/Math/Intersection/Circle/Line.pm view on Meta::CPAN
&$sub(($r**2*atan2($h, $w) - $h*$w)/(ð¿()*$r**2)) # Area of smallest lune as a fraction of circle
} $x, $y, $r, $ð˜…, $ð˜†, $ð•©, $ð•ª;
}
#-------------------------------------------------------------------------------
# ð—–ircumCentre: intersection of the sides of a triangle when rotated ð¿/2 at
# their mid points - centre of the circumCircle
# ð—žnown: coordinates of each corner of the triangle
#-------------------------------------------------------------------------------
sub circumCentre(&$$$$$$)
{my ($sub, $x, $y, $ð˜…, $ð˜†, $ð•©, $ð•ª) = @_; # Subroutine to process results, coordinates of corners
@_ == 7 or confess "Wrong number of parameters";
(near($x, $ð˜…) && near($y, $ð˜†) or near($ð˜…, $ð•©) && near($ð˜†, $ð•ª)) and confess "Corners are too close!";
&intersectionLines(sub{&$sub(@_)},
rotate90AroundMidPoint($x, $y, $ð˜…, $ð˜†),
rotate90AroundMidPoint($ð˜…, $ð˜†, $ð•©, $ð•ª));
}
#-------------------------------------------------------------------------------
# ð—–ircle through three points: https://en.wikipedia.org/wiki/Circumscribed_circle
# ð—žnown: coordinates of each point
# ð—™ind: coordinates of the centre and radius of the circle through these three
# points
#-------------------------------------------------------------------------------
sub circumCircle(&$$$$$$)
{my ($sub, $x, $y, $ð˜…, $ð˜†, $ð•©, $ð•ª) = @_; # Subroutine to process results, coordinates of corners
@_ == 7 or confess "Wrong number of parameters";
(near($x, $ð˜…) && near($y, $ð˜†) or near($ð˜…, $ð•©) && near($ð˜†, $ð•ª)) and confess "Points are too close!";
circumCentre
{my ($X, $Y) = @_; # Centre
my @r = (vectorLength($x, $y, $X, $Y), # Radii
vectorLength($ð˜…, $ð˜†, $X, $Y),
vectorLength($ð•©, $ð•ª, $X, $Y));
&near(@r[0,1]) && &near(@r[1,2]) or confess "Bad radius computed!";
lib/Math/Intersection/Circle/Line.pm view on Meta::CPAN
#-------------------------------------------------------------------------------
# ð—–entre of a circle inscribed inside a triangle so that the inscribed circle
# touches each side just once.
#
# ð—žnown: coordinates of each corner of the triangle
# ð—™ind: centre coordinates and radius of inscribed circle
# ð— ethod: find the intersection of the lines bisecting two angles
#-------------------------------------------------------------------------------
sub circleInscribedInTriangle(&$$$$$$)
{my ($sub, $x, $y, $ð˜…, $ð˜†, $ð•©, $ð•ª) = @_; # Subroutine to process results, coordinates of corners
@_ == 7 or confess "Wrong number of parameters";
(near($x, $ð˜…) && near($y, $ð˜†) or near($ð˜…, $ð•©) && near($ð˜†, $ð•ª)) and confess "Corners are too close!";
my $ð—± = vectorLength($x, $y, $ð•©, $ð•ª); # Lengths of sides opposite corners
my $ð•• = vectorLength($x, $y, $ð˜…, $ð˜†);
my $d = vectorLength($ð˜…, $ð˜†, $ð•©, $ð•ª);
intersectionLines
{my ($X, $Y) = @_; # Intersection point
my @r = ((unsignedDistanceFromLineToPoint {@_} $x, $y, $ð˜…, $ð˜†, $X, $Y),
lib/Math/Intersection/Circle/Line.pm view on Meta::CPAN
}
#-------------------------------------------------------------------------------
# ð—–entre of a circle inscribed through the midpoints of each side of a triangle
# == Nine point circle: https://en.wikipedia.org/wiki/Nine-point_circle
# ð—žnown: coordinates of each corner of the triangle
# ð—™ind: centre coordinates and radius of circle through midpoints
# ð— ethod: use circumCircle on the midpoints
#-------------------------------------------------------------------------------
sub ninePointCircle(&$$$$$$)
{my ($sub, $x, $y, $ð˜…, $ð˜†, $ð•©, $ð•ª) = @_; # Subroutine to process results, coordinates of corners
@_ == 7 or confess "Wrong number of parameters";
(near($x, $ð˜…) && near($y, $ð˜†) or near($ð˜…, $ð•©) && near($ð˜†, $ð•ª)) and confess "Corners are too close!";
&circumCircle(sub{&$sub(@_)}, # Circle through mid points
midPoint($x, $y, $ð˜…, $ð˜†),
midPoint($ð˜…, $ð˜†, $ð•©, $ð•ª),
midPoint($ð•©, $ð•ª, $x, $y));
}
#-------------------------------------------------------------------------------
# Bisect the first angle of a triangle
#-------------------------------------------------------------------------------
sub bisectAnAngle(&$$$$$$)
{my ($sub, $x, $y, $ð˜…, $ð˜†, $ð•©, $ð•ª) = @_; # Subroutine to process results, coordinates of corners
@_ == 7 or confess "Wrong number of parameters";
(near($x, $ð˜…) && near($y, $ð˜†) or near($ð˜…, $ð•©) && near($ð˜†, $ð•ª)) and confess "Corners are too close!";
my $ð•• = vectorLength($x, $y, $ð•©, $ð•ª); # Lengths to opposite corners
my $ð—± = vectorLength($x, $y, $ð˜…, $ð˜†);
&$sub($x, $y, $x + ($ð˜…-$x)/$ð•• + ($ð•©-$x)/$ð—±, $y + ($ð˜†-$y)/$ð•• + ($ð•ª-$y)/$ð—±) # Vector from vertex pointing along bisector
}
#-------------------------------------------------------------------------------
# ð—™ind the centres and radii of the excircles of a triangle
# https://en.wikipedia.org/wiki/Incircle_and_excircles_of_a_triangle
# ð—žnown: coordinates of each corner of the triangle
# ð— ethod: intersection of appropriate angles of the triangles
#-------------------------------------------------------------------------------
sub exCircles(&$$$$$$)
{my ($sub, $x, $y, $ð˜…, $ð˜†, $ð•©, $ð•ª) = @_; # Subroutine to process results, coordinates of corners
@_ == 7 or confess "Wrong number of parameters";
(near($x, $ð˜…) && near($y, $ð˜†) or near($ð˜…, $ð•©) && near($ð˜†, $ð•ª)) and confess "Corners are too close!";
my @c = &intersectionLines(sub{@_}, # Centres
(bisectAnAngle {@_} $x, $y, $ð˜…, $ð˜†, $ð•©, $ð•ª),
(bisectAnAngle {@_} $ð˜…, $ð˜†, $ð•©, $ð•ª, 2*$𘅠- $x, 2*$𘆠- $y));
my @ð—° = &intersectionLines(sub{@_},
(bisectAnAngle {@_} $ð˜…, $ð˜†, $ð•©, $ð•ª, $x, $y),
lib/Math/Intersection/Circle/Line.pm view on Meta::CPAN
&unsignedDistanceFromLineToPoint(sub {@_}, $ð•©, $ð•ª, $x, $y, @ð•”));
([@c, @r], [@ð—°, @ð—¿], [@ð•”, @ð•£]) # For each circle, the centre followed by the radii estimates
}
#-------------------------------------------------------------------------------
# ð—–entroid: intersection of lines between corners and mid points of opposite sides
# ð—™ind: coordinates of centroid
# ð—žnown: coordinates of each corner of the triangle
#-------------------------------------------------------------------------------
sub centroid(&$$$$$$)
{my ($sub, $x, $y, $ð˜…, $ð˜†, $ð•©, $ð•ª) = @_; # Subroutine to process results, coordinates of corners
@_ == 7 or confess "Wrong number of parameters";
(near($x, $ð˜…) && near($y, $ð˜†) or near($ð˜…, $ð•©) && near($ð˜†, $ð•ª)) and confess "Corners are too close!";
&intersectionLines(sub{&$sub(@_)},
$x, $y, midPoint($ð˜…, $ð˜†, $ð•©, $ð•ª),
$ð˜…, $ð˜†, midPoint($ð•©, $ð•ª, $x, $y));
}
#-------------------------------------------------------------------------------
# ð—¢rthocentre: intersection of altitudes
# ð—™ind: coordinates of orthocentre
# ð—žnown: coordinates of each corner of the triangle
#-------------------------------------------------------------------------------
sub orthoCentre(&$$$$$$)
{my ($sub, $x, $y, $ð˜…, $ð˜†, $ð•©, $ð•ª) = @_; # Subroutine to process results, coordinates of corners
@_ == 7 or confess "Wrong number of parameters";
(near($x, $ð˜…) && near($y, $ð˜†) or near($ð˜…, $ð•©) && near($ð˜†, $ð•ª)) and confess "Corners are too close!";
&intersectionLines(sub{&$sub(@_)},
$x, $y, (intersectionLinePoint {@_} $ð˜…, $ð˜†, $ð•©, $ð•ª, $x, $y),
$ð˜…, $ð˜†, (intersectionLinePoint {@_} $ð•©, $ð•ª, $x, $y, $ð˜…, $ð˜†));
}
#-------------------------------------------------------------------------------
# ð—”rea of a triangle
# ð—žnown: coordinates of each corner of the triangle
# ð—™ind: area
# ð— ethod: height of one corner from line through other two corners
#-------------------------------------------------------------------------------
sub areaOfTriangle(&$$$$$$)
{my ($sub, $x, $y, $ð˜…, $ð˜†, $ð•©, $ð•ª) = @_; # Subroutine to process results, coordinates of corners
@_ == 7 or confess "Wrong number of parameters";
return &$sub(0) if near($x, $ð˜…) && near($y, $ð˜†) or near($ð˜…, $ð•©) && near($ð˜†, $ð•ª); # A pair of corners are close, so the area of the triangle must be zero
my ($d) = unsignedDistanceFromLineToPoint(sub {@_}, $ð˜…, $ð˜†, $ð•©, $ð•ª, $x, $y); # Distance for first corner from opposite line
&$sub($d * vectorLength($ð˜…, $ð˜†, $ð•©, $ð•ª)/2) # Area = half base * height
}
#-------------------------------------------------------------------------------
# ð—”rea of a polygon
# ð—žnown: coordinates of each corner=vertex of the polygon
# ð—™ind: area
# ð— ethod: divide the polygon into triangles which all share the first vertex
#-------------------------------------------------------------------------------
sub areaOfPolygon(&@)
{my ($sub, $x, $y, $ð˜…, $ð˜†, $ð•©, $ð•ª, @vertices) = @_; # Subroutine to process results, coordinates of vertices
my ($area) = areaOfTriangle {@_} $x, $y, $ð˜…, $ð˜†, $ð•©, $ð•ª; # Area of first triangle
for(;scalar @vertices;) # Each subsequent triangle
{($ð˜…, $ð˜†) = ($ð•©, $ð•ª); # Move up one vertex at a time
($ð•©, $ð•ª) = splice @vertices, 0, 2; # Remove one vertex
my ($a) = areaOfTriangle {@_} $x, $y, $ð˜…, $ð˜†, $ð•©, $ð•ª; # Area of latest triangle
$area += $a; # Sum areas
}
&$sub($area) # Area of polygon
}
( run in 1.061 second using v1.01-cache-2.11-cpan-49f99fa48dc )