Perform calculations on lines, polygons, planes and circles, including normals, intersections of objects, distance between objects, and tangent lines. Throughout this library, lines can be treated as either unbounded lines, as rays with a single endpoint or as segments, bounded by endpoints at both ends.

To use, add the following lines to the beginning of your file:

include <BOSL2/std.scad>

1. Section: Lines, Rays, and Segments

   • is_point_on_line() – Determine if a point is on a line, ray or segment.
   • is_collinear() – Determine if points are collinear.
   • point_line_distance() – Find shortest distance from point to a line, segment or ray.
   • segment_distance() – Find smallest distance between two line semgnets.
   • line_normal() – Return normal vector to given line.
   • line_intersection() – Compute intersection of two lines, segments or rays.
   • line_closest_point() – Find point on given line, segment or ray that is closest to a given point.
   • line_from_points() – Given a list of collinear points, return the line they define.

2. Section: Planes

   • is_coplanar() – Check if 3d points are coplanar and not collinear.
   • plane3pt() – Return a plane from 3 points.
   • plane3pt_indexed() – Given list of 3d points and 3 indices, return the plane they define.
   • plane_from_normal() – Return plane defined by normal vector and a point.
   • plane_from_points() – Return plane defined by a set of coplanar 3d points, with arbitrary normal direction.
   • plane_from_polygon() – Given a 3d planar polygon, returns directed plane.
   • plane_normal() – Returns the normal vector to a plane.
   • plane_offset() – Returns the signed offset of the plane from the origin.
   • plane_line_intersection() – Returns the intersection of a plane and 3d line, segment or ray.
   • plane_intersection() – Returns the intersection of two or three planes.
   • plane_line_angle() – Returns the angle between a plane and a 3d line.
   • plane_closest_point() – Returns the orthogonal projection of points onto a plane.
   • point_plane_distance() – Determine distance between a point and plane.
   • are_points_on_plane() – Determine if all of the listed points are on a plane.

3. Section: Circle Calculations

   • circle_line_intersection() – Find the intersection points between a 2d circle and a line, ray or segment.
   • circle_circle_intersection() – Find the intersection points of two 2d circles.
   • circle_2tangents() – Given two 2d or 3d rays, find a circle tangent to both.
   • circle_3points() – Find a circle passing through three 2d or 3d points.
   • circle_point_tangents() – Given a circle and point, find tangents to circle passing through the point.
   • circle_circle_tangents() – Find tangents to a pair of circles in 2d.

4. Section: Sphere Calculations

   • sphere_line_intersection() – Find intersection between a sphere and line, ray or segment.

5. Section: Polygons

   • polygon_area() – Calculate area of a 2d or 3d polygon.
   • centroid() – Compute centroid of a 2d or 3d polygon or a VNF.
   • polygon_normal() – Return normal to a polygon.
   • point_in_polygon() – Checks if a 2d point is inside or on the boundary of a 2d polygon.
   • polygon_line_intersection() – Find intersection between 2d or 3d polygon and a line, segment or ray.
   • polygon_triangulate() – Divide a polygon into triangles.
   • is_polygon_clockwise() – Determine if a 2d polygon winds clockwise.
   • clockwise_polygon() – Return clockwise version of a polygon.
   • ccw_polygon() – Return counter-clockwise version of a polygon.
   • reverse_polygon() – Reverse winding direction of polygon.
   • reindex_polygon() – Adjust point indexing of polygon to minimize pointwise distance to a reference polygon.
   • align_polygon() – Find best alignment of a 2d polygon to a reference 2d polygon over a set of transformations.
   • are_polygons_equal() – Check if two polygons (not necessarily in the same point order) are equal.

6. Section: Convex Hull

   • hull() – Convex hull of a list of 2d or 3d points. ^[Ext]
   • hull_points() – Convex hull of a list of 2d or 3d points.
   • hull2d_path() – Convex hull of a list of 2d points.
   • hull3d_faces() – Convex hull of a list of 3d points.

7. Section: Convex Sets

   • is_polygon_convex() – Check if a polygon is convex.
   • convex_distance() – Compute distance between convex hull of two point lists.
   • convex_collision() – Check whether the convex hulls of two point lists intersect.

8. Section: Rotation Decoding

   • rot_decode() – Extract axis and rotation angle from a rotation matrix.

Synopsis: Determine if a point is on a line, ray or segment.

Topics: Geometry, Points, Segments

See Also: is_collinear(), point_line_distance(), line_from_points()

Usage:

• pt = is_point_on_line(point, line, [bounded], [eps]);

Description:

Determine if the point is on the line segment, ray or segment defined by the two between two points. Returns true if yes, and false if not. If bounded is set to true it specifies a segment, with both lines bounded at the ends. Set bounded to [true,false] to get a ray. You can use the shorthands RAY and SEGMENT to set bounded.

Arguments:

Synopsis: Determine if points are collinear.

Topics: Geometry, Points, Collinearity

See Also: is_point_on_line(), point_line_distance(), line_from_points()

Usage:

• bool = is_collinear(a, [b, c], [eps]);

Description:

Returns true if the points a, b and c are co-linear or if the list of points a is collinear.

Arguments:

Synopsis: Find shortest distance from point to a line, segment or ray.

Topics: Geometry, Points, Lines, Distance

See Also: is_collinear(), is_point_on_line(), line_from_points()

Usage:

• dist = point_line_distance(pt, line, [bounded]);

Description:

Finds the shortest distance from the point pt to the specified line, segment or ray. The bounded parameter specifies the whether the endpoints give a ray or segment. By default assumes an unbounded line.

Arguments:

Example 1:

include <BOSL2/std.scad>
dist1 = point_line_distance([3,8], [[-10,0], [10,0]]);  // Returns: 8
dist2 = point_line_distance([3,8], [[-10,0], [10,0]],SEGMENT);  // Returns: 8
dist3 = point_line_distance([14,3], [[-10,0], [10,0]],SEGMENT);  // Returns: 5

Synopsis: Find smallest distance between two line semgnets.

Topics: Geometry, Segments, Distance

See Also: convex_collision(), convex_distance()

Usage:

• dist = segment_distance(seg1, seg2, [eps]);

Description:

Returns the smallest distance of the points on two given line segments.

Arguments:

Example 1:

include <BOSL2/std.scad>
dist = segment_distance([[-14,3], [-15,9]], [[-10,0], [10,0]]);  // Returns: 5
dist2 = segment_distance([[-5,5], [5,-5]], [[-10,3], [10,-3]]);  // Returns: 0

Synopsis: Return normal vector to given line.

Topics: Geometry, Lines

See Also: line_intersection(), line_from_points()

Usage:

• vec = line_normal([P1,P2])
• vec = line_normal(p1,p2)

Description:

Returns the 2D normal vector to the given 2D line. This is otherwise known as the perpendicular vector counter-clockwise to the given ray.

Arguments:

Example 1:

include <BOSL2/std.scad>
p1 = [10,10];
p2 = [50,30];
n = line_normal(p1,p2);
stroke([p1,p2], endcap2="arrow2");
color("green") stroke([p1,p1+10*n], endcap2="arrow2");
color("blue") move_copies([p1,p2]) circle(d=2, $fn=12);

Synopsis: Compute intersection of two lines, segments or rays.

Topics: Geometry, Lines

See Also: line_normal(), line_from_points()

Usage:

• pt = line_intersection(line1, line2, [bounded1], [bounded2], [bounded=], [eps=]);

Description:

Returns the intersection point of any two 2D lines, segments or rays. Returns undef if they do not intersect. You specify a line by giving two distinct points on the line. You specify rays or segments by giving a pair of points and indicating bounded[0]=true to bound the line at the first point, creating rays based at l1[0] and l2[0], or bounded[1]=true to bound the line at the second point, creating the reverse rays bounded at l1[1] and l2[1]. If bounded=[true, true] then you have segments defined by their two endpoints. By using bounded1 and bounded2 you can mix segments, rays, and lines as needed. You can set the bounds parameters to true as a shorthand for [true,true] to sepcify segments.

Arguments:

Example 1: The segments do not intersect but the lines do in this example.

include <BOSL2/std.scad>
line1 = 10*[[9, 4], [5, 7]];
line2 = 10*[[2, 3], [6, 5]];
stroke(line1, endcaps="arrow2");
stroke(line2, endcaps="arrow2");
isect = line_intersection(line1, line2);
color("red") translate(isect) circle(r=1,$fn=12);

Example 2: Specifying a ray and segment using the shorthand variables.

include <BOSL2/std.scad>
line1 = 10*[[0, 2], [4, 7]];
line2 = 10*[[10, 4], [3, 4]];
stroke(line1);
stroke(line2, endcap2="arrow2");
isect = line_intersection(line1, line2, SEGMENT, RAY);
color("red") translate(isect) circle(r=1,$fn=12);

Example 3: Here we use the same example as above, but specify two segments using the bounded argument.

include <BOSL2/std.scad>
line1 = 10*[[0, 2], [4, 7]];
line2 = 10*[[10, 4], [3, 4]];
stroke(line1);
stroke(line2);
isect = line_intersection(line1, line2, bounded=true);  // Returns undef

Synopsis: Find point on given line, segment or ray that is closest to a given point.

Topics: Geometry, Lines, Distance

See Also: line_normal(), point_line_distance()

Usage:

• pt = line_closest_point(line, pt, [bounded]);

Description:

Returns the point on the given line, segment or ray that is closest to the given point pt. The inputs line and pt args should be of the same dimension. The parameter bounded indicates whether the points of line should be treated as endpoints.

Arguments:

Example 1:

include <BOSL2/std.scad>
line = [[-30,0],[30,30]];
pt = [-32,-10];
p2 = line_closest_point(line,pt);
stroke(line, endcaps="arrow2");
color("blue") translate(pt) circle(r=1,$fn=12);
color("red") translate(p2) circle(r=1,$fn=12);

Example 2: If the line is bounded on the left you get the endpoint instead

include <BOSL2/std.scad>
line = [[-30,0],[30,30]];
pt = [-32,-10];
p2 = line_closest_point(line,pt,bounded=[true,false]);
stroke(line, endcap2="arrow2");
color("blue") translate(pt) circle(r=1,$fn=12);
color("red") translate(p2) circle(r=1,$fn=12);

Example 3: In this case it doesn't matter how bounded is set. Using SEGMENT is the most restrictive option.

include <BOSL2/std.scad>
line = [[-30,0],[30,30]];
pt = [-5,0];
p2 = line_closest_point(line,pt,SEGMENT);
stroke(line);
color("blue") translate(pt) circle(r=1,$fn=12);
color("red") translate(p2) circle(r=1,$fn=12);

Example 4: The result here is the same for a line or a ray.

include <BOSL2/std.scad>
line = [[-30,0],[30,30]];
pt = [40,25];
p2 = line_closest_point(line,pt,RAY);
stroke(line, endcap2="arrow2");
color("blue") translate(pt) circle(r=1,$fn=12);
color("red") translate(p2) circle(r=1,$fn=12);

Example 5: But with a segment we get a different result

include <BOSL2/std.scad>
line = [[-30,0],[30,30]];
pt = [40,25];
p2 = line_closest_point(line,pt,SEGMENT);
stroke(line);
color("blue") translate(pt) circle(r=1,$fn=12);
color("red") translate(p2) circle(r=1,$fn=12);

Example 6: The shorthand RAY uses the first point as the base of the ray. But you can specify a reversed ray directly, and in this case the result is the same as the result above for the segment.

include <BOSL2/std.scad>
line = [[-30,0],[30,30]];
pt = [40,25];
p2 = line_closest_point(line,pt,[false,true]);
stroke(line,endcap1="arrow2");
color("blue") translate(pt) circle(r=1,$fn=12);
color("red") translate(p2) circle(r=1,$fn=12);

Example 7: A 3D example

include <BOSL2/std.scad>
line = [[-30,-15,0],[30,15,30]];
pt = [5,5,5];
p2 = line_closest_point(line,pt);
stroke(line, endcaps="arrow2");
color("blue") translate(pt) sphere(r=1,$fn=12);
color("red") translate(p2) sphere(r=1,$fn=12);

Synopsis: Given a list of collinear points, return the line they define.

Topics: Geometry, Lines, Points

Usage:

• line = line_from_points(points, [fast], [eps]);

Description:

Given a list of 2 or more collinear points, returns two points defining a line containing them. If fast is false and the points are coincident or non-collinear, then undef is returned. if fast is true, then the collinearity test is skipped and a line passing through 2 distinct arbitrary points is returned.

Arguments:

Synopsis: Check if 3d points are coplanar and not collinear.

Topics: Geometry, Coplanarity

See Also: plane3pt(), plane3pt_indexed(), plane_from_normal(), plane_from_points(), plane_from_polygon()

Usage:

• bool = is_coplanar(points,[eps]);

Description:

Returns true if the given 3D points are non-collinear and are on a plane.

Arguments:

Synopsis: Return a plane from 3 points.

Topics: Geometry, Planes

See Also: plane3pt_indexed(), plane_from_normal(), plane_from_points(), plane_from_polygon()

Usage:

• plane = plane3pt(p1, p2, p3);
• plane = plane3pt([p1, p2, p3]);

Description:

Generates the normalized cartesian equation of a plane from three 3d points. Returns [A,B,C,D] where Ax + By + Cz = D is the equation of a plane. Returns undef, if the points are collinear.

Arguments:

Synopsis: Given list of 3d points and 3 indices, return the plane they define.

Topics: Geometry, Planes

See Also: plane3pt(), plane_from_normal(), plane_from_points(), plane_from_polygon()

Usage:

• plane = plane3pt_indexed(points, i1, i2, i3);

Description:

Given a list of 3d points, and the indices of three of those points, generates the normalized cartesian equation of a plane that those points all lie on. If the points are not collinear, returns [A,B,C,D] where Ax+By+Cz=D is the equation of a plane. If they are collinear, returns [].

Arguments:

Synopsis: Return plane defined by normal vector and a point.

Topics: Geometry, Planes

See Also: plane3pt(), plane3pt_indexed(), plane_from_points(), plane_from_polygon()

Usage:

• plane = plane_from_normal(normal, [pt])

Description:

Returns a plane defined by a normal vector and a point. If you omit pt you will get a plane passing through the origin.

Arguments:

Example 1:

include <BOSL2/std.scad>
plane_from_normal([0,0,1], [2,2,2]);  // Returns the xy plane passing through the point (2,2,2)

Synopsis: Return plane defined by a set of coplanar 3d points, with arbitrary normal direction.

Topics: Geometry, Planes, Points

See Also: plane3pt(), plane3pt_indexed(), plane_from_normal(), plane_from_polygon()

Usage:

• plane = plane_from_points(points, [fast], [eps]);

Description:

Given a list of 3 or more coplanar 3D points, returns the coefficients of the normalized cartesian equation of a plane, that is [A,B,C,D] where Ax+By+Cz=D is the equation of the plane and norm([A,B,C])=1. If fast is false and the points in the list are collinear or not coplanar, then undef is returned. If fast is true, the polygon coplanarity check is skipped and a best fitting plane is returned. The direction of the plane's normal is arbitrary and is not determined by the point order, unlike plane_from_polygon(). This function is faster than plane_from_polygon().

Arguments:

Example 1:

include <BOSL2/std.scad>
points = rot(45, v=[-0.3,1,0], p=path3d(random_points(25,2,scale=55,seed=47), 70));
plane = plane_from_points(points);
#move_copies(points)sphere(d=3);
cp = mean(points);
move(cp) rot(from=UP,to=plane_normal(plane)) anchor_arrow(50);

Synopsis: Given a 3d planar polygon, returns directed plane.

Topics: Geometry, Planes, Polygons

See Also: plane3pt(), plane3pt_indexed(), plane_from_normal(), plane_from_points()

Usage:

• plane = plane_from_polygon(points, [fast], [eps]);

Description:

Given a 3D planar polygon, returns the normalized cartesian equation of its plane. Returns [A,B,C,D] where Ax+By+Cz=D is the equation of the plane where norm([A,B,C])=1. If not all the points in the polygon are coplanar, then [] is returned. If fast is false and the points in the list are collinear or not coplanar, then undef is returned. if fast is true, then the coplanarity test is skipped and a plane passing through 3 non-collinear arbitrary points is returned. The normal direction is determined by the order of the points and the right hand rule. This is slower than plane_from_points(), which returns an arbitrary normal.

Arguments:

Example 1:

include <BOSL2/std.scad>
xyzpath = rot(45, v=[0,1,0], p=path3d(star(n=5,step=2,d=100), 70));
plane = plane_from_polygon(xyzpath);
#stroke(xyzpath,closed=true,width=3);
cp = centroid(xyzpath);
move(cp) rot(from=UP,to=plane_normal(plane)) anchor_arrow(45);

Synopsis: Returns the normal vector to a plane.

Topics: Geometry, Planes

See Also: plane3pt(), plane3pt_indexed(), plane_from_normal(), plane_from_points(), plane_from_polygon(), plane_offset()

Usage:

• vec = plane_normal(plane);

Description:

Returns the unit length normal vector for the given plane.

Arguments:

Synopsis: Returns the signed offset of the plane from the origin.

Topics: Geometry, Planes

See Also: plane3pt(), plane3pt_indexed(), plane_from_normal(), plane_from_points(), plane_from_polygon(), plane_normal()

Usage:

• d = plane_offset(plane);

Description:

Returns coeficient D of the normalized plane equation Ax+By+Cz=D, or the scalar offset of the plane from the origin. This value may be negative. The absolute value of this coefficient is the distance of the plane from the origin.

Arguments:

Synopsis: Returns the intersection of a plane and 3d line, segment or ray.

Topics: Geometry, Planes, Lines, Intersection

See Also: plane3pt(), plane_from_normal(), plane_from_points(), plane_from_polygon(), line_intersection()

Usage:

• pt = plane_line_intersection(plane, line, [bounded], [eps]);

Description:

Takes a line, and a plane [A,B,C,D] where the equation of that plane is Ax+By+Cz=D. If line intersects plane at one point, then that intersection point is returned. If line lies on plane, then the original given line is returned. If line is parallel to, but not on plane, then undef is returned.

Arguments:

Synopsis: Returns the intersection of two or three planes.

Topics: Geometry, Planes, Intersection

See Also: plane3pt(), plane_from_normal(), plane_from_points(), plane_from_polygon(), line_intersection()

Usage:

• line = plane_intersection(plane1, plane2)
• pt = plane_intersection(plane1, plane2, plane3)

Description:

Compute the point which is the intersection of the three planes, or the line intersection of two planes. If you give three planes the intersection is returned as a point. If you give two planes the intersection is returned as a list of two points on the line of intersection. If any two input planes are parallel or coincident then returns undef.

Arguments:

Synopsis: Returns the angle between a plane and a 3d line.

Topics: Geometry, Planes, Lines, Angle

See Also: plane3pt(), plane_from_normal(), plane_from_points(), plane_from_polygon(), plane_intersection(), line_intersection(), vector_angle()

Usage:

• angle = plane_line_angle(plane,line);

Description:

Compute the angle between a plane [A, B, C, D] and a 3d line, specified as a pair of 3d points [p1,p2]. The resulting angle is signed, with the sign positive if the vector p2-p1 lies above the plane, on the same side of the plane as the plane's normal vector.

Synopsis: Returns the orthogonal projection of points onto a plane.

Topics: Geometry, Planes, Projection

See Also: plane3pt(), line_closest_point(), point_plane_distance()

Usage:

• pts = plane_closest_point(plane, points);

Description:

Given a plane definition [A,B,C,D], where Ax+By+Cz=D, and a list of 2d or 3d points, return the closest 3D orthogonal projection of the points on the plane. In other words, for every point given, returns the closest point to it on the plane. If points is a single point then returns a single point result.

Arguments:

Example 1:

include <BOSL2/std.scad>
points = move([10,20,30], p=yrot(25, p=path3d(circle(d=100, $fn=36))));
plane = plane_from_normal([1,0,1]);
proj = plane_closest_point(plane,points);
color("red") move_copies(points) sphere(d=4,$fn=12);
color("blue") move_copies(proj) sphere(d=4,$fn=12);
move(centroid(proj)) {
    rot(from=UP,to=plane_normal(plane)) {
        anchor_arrow(50);
        %cube([120,150,0.1],center=true);
    }
}

Synopsis: Determine distance between a point and plane.

Topics: Geometry, Planes, Distance

See Also: plane3pt(), line_closest_point(), plane_closest_point()

Usage:

• dist = point_plane_distance(plane, point)

Description:

Given a plane as [A,B,C,D] where the cartesian equation for that plane is Ax+By+Cz=D, determines how far from that plane the given point is. The returned distance will be positive if the point is above the plane, meaning on the side where the plane normal points. If the point is below the plane, then the distance returned will be negative. The normal of the plane is [A,B,C].

Arguments:

Synopsis: Determine if all of the listed points are on a plane.

Topics: Geometry, Planes, Points

See Also: plane3pt(), line_closest_point(), plane_closest_point(), is_coplanar()

Usage:

• bool = are_points_on_plane(points, plane, [eps]);

Description:

Returns true if the given 3D points are on the given plane.

Arguments:

Synopsis: Find the intersection points between a 2d circle and a line, ray or segment.

Topics: Geometry, Circles, Lines, Intersection

See Also: circle_circle_intersection(), circle_2tangents(), circle_3points(), circle_point_tangents(), circle_circle_tangents()

Usage:

• pts = circle_line_intersection(r|d=, cp, line, [bounded], [eps=]);

Description:

Find intersection points between a 2D circle and a line, ray or segment specified by two points. By default the line is unbounded. Returns the list of zero or more intersection points.

Arguments:

Example 1: Standard intersection returns two points.

include <BOSL2/std.scad>
line = [[-15,2], [15,7]];
cp = [1,2]; r = 10;
translate(cp) circle(r=r);
color("black") stroke(line, endcaps="arrow2", width=0.5);
isects = circle_line_intersection(r=r, cp=cp, line=line);
color("red") move_copies(isects) circle(d=1);

Example 2: Tangent intersection returns one point.

include <BOSL2/std.scad>
line = [[-10,12], [10,12]];
cp = [1,2]; r = 10;
translate(cp) circle(r=r);
color("black") stroke(line, endcaps="arrow2", width=0.5);
isects = circle_line_intersection(r=r, cp=cp, line=line);
color("#f44") move_copies(isects) circle(d=1);

Example 3: A bounded ray might only intersect in one direction.

include <BOSL2/std.scad>
line = [[-5,2], [5,7]];
extended = [line[0], line[0]+22*unit(line[1]-line[0])];
cp = [1,2]; r = 10;
translate(cp) circle(r=r);
color("gray") dashed_stroke(extended, width=0.2);
color("black") stroke(line, endcap2="arrow2", width=0.5);
isects = circle_line_intersection(r=r, cp=cp, line=line, bounded=[true,false]);
color("#f44") move_copies(isects) circle(d=1);

Example 4: If they don't intersect at all, then an empty list is returned.

include <BOSL2/std.scad>
line = [[-12,12], [12,8]];
cp = [-5,-2]; r = 10;
translate(cp) circle(r=r);
color("black") stroke(line, endcaps="arrow2", width=0.5);
isects = circle_line_intersection(r=r, cp=cp, line=line);
color("#f44") move_copies(isects) circle(d=1);

Synopsis: Find the intersection points of two 2d circles.

Topics: Geometry, Circles

See Also: circle_line_intersection(), circle_2tangents(), circle_3points(), circle_point_tangents(), circle_circle_tangents()

Usage:

• pts = circle_circle_intersection(r1|d1=, cp1, r2|d2=, cp2, [eps]);

Description:

Compute the intersection points of two circles. Returns a list of the intersection points, which will contain two points in the general case, one point for tangent circles, or will be empty if the circles do not intersect.

Arguments:

Example 1: Circles intersect in two points.

include <BOSL2/std.scad>
$fn=32;
cp1 = [4,4];  r1 = 3;
cp2 = [7,7];  r2 = 2;
pts = circle_circle_intersection(r1, cp1, r2, cp2);
move(cp1) stroke(circle(r=r1), width=0.2, closed=true);
move(cp2) stroke(circle(r=r2), width=0.2, closed=true);
color("red") move_copies(pts) circle(r=.3);

Example 2: Circles are tangent, so one intersection point:

include <BOSL2/std.scad>
$fn=32;
cp1 = [4,4];  r1 = 4;
cp2 = [4,10]; r2 = 2;
pts = circle_circle_intersection(r1, cp1, r2, cp2);
move(cp1) stroke(circle(r=r1), width=0.2, closed=true);
move(cp2) stroke(circle(r=r2), width=0.2, closed=true);
color("red") move_copies(pts) circle(r=.3);

Example 3: Another tangent example:

include <BOSL2/std.scad>
$fn=32;
cp1 = [4,4];  r1 = 4;
cp2 = [5,5];  r2 = 4-sqrt(2);
pts = circle_circle_intersection(r1, cp1, r2, cp2);
move(cp1) stroke(circle(r=r1), width=0.2, closed=true);
move(cp2) stroke(circle(r=r2), width=0.2, closed=true);
color("red") move_copies(pts) circle(r=.3);

Example 4: Circles do not intersect. Returns empty list.

include <BOSL2/std.scad>
$fn=32;
cp1 = [3,4];  r1 = 2;
cp2 = [7,10]; r2 = 3;
pts = circle_circle_intersection(r1, cp1, r2, cp2);
move(cp1) stroke(circle(r=r1), width=0.2, closed=true);
move(cp2) stroke(circle(r=r2), width=0.2, closed=true);
color("red") move_copies(pts) circle(r=.3);

Synopsis: Given two 2d or 3d rays, find a circle tangent to both.

Topics: Geometry, Circles, Tangents

See Also: circle_line_intersection(), circle_circle_intersection(), circle_3points(), circle_point_tangents(), circle_circle_tangents()

Usage:

• circ = circle_2tangents(r|d=, pt1, pt2, pt3, [tangents=]);
• circ = circle_2tangents(r|d=, [PT1, PT2, PT3], [tangents=]);

Description:

Given a pair of 2d or 3d rays with a common origin, and a known circle radius/diameter, finds the centerpoint for the circle of that size that touches both rays tangentally. Both rays start at pt2, one passing through pt1, and the other through pt3.

When called with collinear rays, returns undef. Otherwise, when called with tangents=false, returns [CP,NORMAL]. Otherwise, when called with tangents=true, returns [CP,NORMAL,TANPT1,TANPT2].

• CP is the centerpoint of the circle.
• NORMAL is the normal vector of the plane that the circle is on (UP or DOWN if the points are 2D).
• TANPT1 is the point where the circle is tangent to the ray [pt2,pt1].
• TANPT2 is the point where the circle is tangent to the ray [pt2,pt3].

Figure 1:

Arguments:

Example 1:

include <BOSL2/std.scad>
pts = [[40,40], [10,10], [55,5]];  rad = 10;
circ = circle_2tangents(r=rad, pt1=pts[0], pt2=pts[1], pt3=pts[2]);
stroke(pts, endcaps="arrow2");
color("red") move(circ[0]) circle(r=rad);

Example 2:

include <BOSL2/std.scad>
pts = [[20,40], [10,10], [55,20]];  rad = 10;
circ = circle_2tangents(r=rad, pt1=pts[0], pt2=pts[1], pt3=pts[2], tangents=true);
stroke(pts, endcaps="arrow2");
color("red") move(circ[0]) circle(r=rad);
color("blue") move_copies(select(circ,2,3)) circle(d=2);

Example 3: Fit into 3D path corner.

include <BOSL2/std.scad>
pts = [[45,5,10], [10,10,15], [30,40,30]];  rad = 10;
circ = circle_2tangents(rad, [pts[0], pts[1], pts[2]]);
stroke(pts, endcaps="arrow2");
color("red") move(circ[0]) cyl(h=10, r=rad, orient=circ[1]);

Example 4:

include <BOSL2/std.scad>
path = yrot(20, p=path3d(star(d=100, n=5, step=2)));
stroke(path, closed=true);
for (i = [0:1:5]) {
    crn = select(path, i*2-1, i*2+1);
    ci = circle_2tangents(5, crn[0], crn[1], crn[2]);
    move(ci[0]) cyl(h=10,r=5,orient=ci[1]);
}

Synopsis: Find a circle passing through three 2d or 3d points.

Topics: Geometry, Circles

See Also: circle_line_intersection(), circle_circle_intersection(), circle_2tangents(), circle_point_tangents(), circle_circle_tangents()

Usage:

• circ = circle_3points(pt1, pt2, pt3);
• circ = circle_3points([PT1, PT2, PT3]);

Description:

Returns the [CENTERPOINT, RADIUS, NORMAL] of the circle that passes through three non-collinear points where NORMAL is the normal vector of the plane that the circle is on (UP or DOWN if the points are 2D). The centerpoint will be a 2D or 3D vector, depending on the points input. If all three points are 2D, then the resulting centerpoint will be 2D, and the normal will be UP ([0,0,1]). If any of the points are 3D, then the resulting centerpoint will be 3D. If the three points are collinear, then [undef,undef,undef] will be returned. The normal will be a normalized 3D vector with a non-negative Z axis. Instead of 3 arguments, it is acceptable to input the 3 points as a list given in pt1, leaving pt2and pt3 as undef.

Arguments:

Example 1:

include <BOSL2/std.scad>
pts = [[60,40], [10,10], [65,5]];
circ = circle_3points(pts[0], pts[1], pts[2]);
translate(circ[0]) color("green") stroke(circle(r=circ[1]),closed=true,$fn=72);
translate(circ[0]) color("red") circle(d=3, $fn=12);
move_copies(pts) color("blue") circle(d=3, $fn=12);

Synopsis: Given a circle and point, find tangents to circle passing through the point.

Topics: Geometry, Circles, Tangents

See Also: circle_line_intersection(), circle_circle_intersection(), circle_2tangents(), circle_3points(), circle_circle_tangents()

Usage:

• tangents = circle_point_tangents(r|d=, cp, pt);

Description:

Given a 2d circle and a 2d point outside that circle, finds the 2d tangent point(s) on the circle for a line passing through the point. Returns a list of zero or more 2D tangent points.

Arguments:

Example 1:

include <BOSL2/std.scad>
cp = [-10,-10];  r = 30;  pt = [30,10];
tanpts = circle_point_tangents(r=r, cp=cp, pt=pt);
color("yellow") translate(cp) circle(r=r);
color("cyan") for(tp=tanpts) {stroke([tp,pt]); stroke([tp,cp]);}
color("red") move_copies(tanpts) circle(d=3,$fn=12);
color("blue") move_copies([cp,pt]) circle(d=3,$fn=12);

Synopsis: Find tangents to a pair of circles in 2d.

Topics: Geometry, Circles, Tangents

See Also: circle_line_intersection(), circle_circle_intersection(), circle_2tangents(), circle_3points(), circle_point_tangents()

Usage:

• segs = circle_circle_tangents(r1|d1=, cp1, r2|d2=, cp2);

Description:

Computes 2d lines tangents to a pair of circles in 2d. Returns a list of line endpoints [p1,p2] where p1 is the tangent point on circle 1 and p2 is the tangent point on circle 2. If four tangents exist then the first one is the left hand exterior tangent as regarded looking from circle 1 toward circle 2. The second value is the right hand exterior tangent. The third entry gives the interior tangent that starts on the left of circle 1 and crosses to the right side of circle 2. And the fourth entry is the last interior tangent that starts on the right side of circle 1. If the circles intersect then the interior tangents don't exist and the function returns only two entries. If one circle is inside the other one then no tangents exist so the function returns the empty set. When the circles are tangent a degenerate tangent line passes through the point of tangency of the two circles: this degenerate line is NOT returned.

Arguments:

Example 1: Four tangents, first in green, second in black, third in blue, last in red.

include <BOSL2/std.scad>
$fn=32;
cp1 = [3,4];  r1 = 2;
cp2 = [7,10]; r2 = 3;
pts = circle_circle_tangents(r1, cp1, r2, cp2);
move(cp1) stroke(circle(r=r1), width=0.2, closed=true);
move(cp2) stroke(circle(r=r2), width=0.2, closed=true);
colors = ["green","black","blue","red"];
for(i=[0:len(pts)-1]) color(colors[i]) stroke(pts[i],width=0.2);

Example 2: Circles overlap so only exterior tangents exist.

include <BOSL2/std.scad>
$fn=32;
cp1 = [4,4];  r1 = 3;
cp2 = [7,7];  r2 = 2;
pts = circle_circle_tangents(r1, cp1, r2, cp2);
move(cp1) stroke(circle(r=r1), width=0.2, closed=true);
move(cp2) stroke(circle(r=r2), width=0.2, closed=true);
colors = ["green","black","blue","red"];
for(i=[0:len(pts)-1]) color(colors[i]) stroke(pts[i],width=0.2);

Example 3: Circles are tangent. Only exterior tangents are returned. The degenerate internal tangent is not returned.

include <BOSL2/std.scad>
$fn=32;
cp1 = [4,4];  r1 = 4;
cp2 = [4,10]; r2 = 2;
pts = circle_circle_tangents(r1, cp1, r2, cp2);
move(cp1) stroke(circle(r=r1), width=0.2, closed=true);
move(cp2) stroke(circle(r=r2), width=0.2, closed=true);
colors = ["green","black","blue","red"];
for(i=[0:1:len(pts)-1]) color(colors[i]) stroke(pts[i],width=0.2);

Example 4: One circle is inside the other: no tangents exist. If the interior circle is tangent the single degenerate tangent will not be returned.

include <BOSL2/std.scad>
$fn=32;
cp1 = [4,4];  r1 = 4;
cp2 = [5,5];  r2 = 2;
pts = circle_circle_tangents(r1, cp1, r2, cp2);
move(cp1) stroke(circle(r=r1), width=0.2, closed=true);
move(cp2) stroke(circle(r=r2), width=0.2, closed=true);
echo(pts);   // Returns []

Synopsis: Find intersection between a sphere and line, ray or segment.

Topics: Geometry, Spheres, Lines, Intersection

See Also: circle_line_intersection(), circle_circle_intersection(), circle_2tangents(), circle_3points(), circle_point_tangents(), circle_circle_tangents()

Usage:

• isect = sphere_line_intersection(r|d=, cp, line, [bounded], [eps=]);

Description:

Find intersection points between a sphere and a line, ray or segment specified by two points. By default the line is unbounded.

Arguments:

Example 1:

include <BOSL2/std.scad>
cp = [10,20,5];  r = 40;
line = [[-50,-10,25], [70,0,40]];
isects = sphere_line_intersection(r=r, cp=cp, line=line);
color("cyan") stroke(line);
move(cp) sphere(r=r, $fn=72);
color("red") move_copies(isects) sphere(d=3, $fn=12);

Synopsis: Calculate area of a 2d or 3d polygon.

Topics: Geometry, Polygons, Area

See Also: centroid(), polygon_normal(), point_in_polygon(), polygon_line_intersection()

Usage:

• area = polygon_area(poly, [signed]);

Description:

Given a 2D or 3D simple planar polygon, returns the area of that polygon. If the polygon is non-planar the result is undef. If the polygon is self-intersecting then the return will be a meaningless number. When signed is true and the polygon is 2d, a signed area is returned: a positive area indicates a counter-clockwise polygon. The area of 3d polygons is always nonnegative.

Arguments:

Synopsis: Compute centroid of a 2d or 3d polygon or a VNF.

Topics: Geometry, Polygons, Centroid

See Also: polygon_area(), polygon_normal(), point_in_polygon(), polygon_line_intersection()

Usage:

• c = centroid(object, [eps]);

Description:

Given a simple 2D polygon, returns the 2D coordinates of the polygon's centroid. Given a simple 3D planar polygon, returns the 3D coordinates of the polygon's centroid. If you provide a non-planar or collinear polygon you will get an error. For self-intersecting polygons you may get an error or you may get meaningless results.

Given a region, returns the 2D coordinates of the region's centroid.

Given a manifold VNF then returns the 3D centroid of the polyhedron. The VNF must describe a valid polyhedron with consistent face direction and no holes in the mesh; otherwise the results are undefined.

Arguments:

Example 1:

include <BOSL2/std.scad>
path = [
    [-10,10], [-5,15], [15,15], [20,0],
    [15,-5], [25,-20], [25,-27], [15,-20],
    [0,-30], [-15,-25], [-5,-5]
];
linear_extrude(height=0.01) polygon(path);
cp = centroid(path);
color("red") move(cp) sphere(d=2);

Synopsis: Return normal to a polygon.

Topics: Geometry, Polygons

See Also: polygon_area(), centroid(), point_in_polygon(), polygon_line_intersection()

Usage:

• vec = polygon_normal(poly);

Description:

Given a 3D simple planar polygon, returns a unit normal vector for the polygon. The vector is oriented so that if the normal points towards the viewer, the polygon winds in the clockwise direction. If the polygon has zero area, returns undef. If the polygon is self-intersecting the the result is undefined. It doesn't check for coplanarity.

Arguments:

Example 1:

include <BOSL2/std.scad>
path = rot([0,30,15], p=path3d(star(n=5, d=100, step=2)));
stroke(path, closed=true);
n = polygon_normal(path);
rot(from=UP, to=n)
    color("red")
        stroke([[0,0,0], [0,0,20]], endcap2="arrow2");

Synopsis: Checks if a 2d point is inside or on the boundary of a 2d polygon.

Topics: Geometry, Polygons

See Also: polygon_area(), centroid(), polygon_normal(), polygon_line_intersection()

Usage:

• bool = point_in_polygon(point, poly, [nonzero], [eps])

Description:

This function tests whether the given 2D point is inside, outside or on the boundary of the specified 2D polygon. The polygon is given as a list of 2D points, not including the repeated end point. Returns -1 if the point is outside the polygon. Returns 0 if the point is on the boundary. Returns 1 if the point lies in the interior. The polygon does not need to be simple: it may have self-intersections. But the polygon cannot have holes (it must be simply connected). Rounding errors may give mixed results for points on or near the boundary.

When polygons intersect themselves different definitions exist for determining which points are inside the polygon. The figure below shows the difference. OpenSCAD uses the Even-Odd rule when creating polygons, where membership in overlapping regions depends on how many times they overlap. The Nonzero rule considers point inside the polygon if the polygon overlaps them any number of times. For more information see https://en.wikipedia.org/wiki/Nonzero-rule and https://en.wikipedia.org/wiki/Even–odd_rule.

Figure 1:

Arguments:

Example 1: With nonzero set to false (the default), we get this result. Green dots are inside the polygon and red are outside:

include <BOSL2/std.scad>
a=20*2/3;
b=30*2/3;
ofs = 17*2/3;
curve = [for(theta=[0:10:140])  [a * theta/360*2*PI - b*sin(theta), a-b*cos(theta)]];
path = deduplicate(concat( reverse(offset(curve,r=ofs)),
               xflip(offset(curve,r=ofs)),
               xflip(reverse(curve)),
               curve
             ));
stroke(path,closed=true);
pts = [[0,0],[10,0],[0,20]];
for(p=pts){
  color(point_in_polygon(p,path)==1 ? "green" : "red")
  move(p)circle(r=1.5, $fn=12);
}

Example 2: With nonzero set to true, one dot changes color:

include <BOSL2/std.scad>
a=20*2/3;
b=30*2/3;
ofs = 17*2/3;
curve = [for(theta=[0:10:140])  [a * theta/360*2*PI - b*sin(theta), a-b*cos(theta)]];
path = deduplicate(concat( reverse(offset(curve,r=ofs)),
               xflip(offset(curve,r=ofs)),
               xflip(reverse(curve)),
               curve
             ));
stroke(path,closed=true);
pts = [[0,0],[10,0],[0,20]];
for(p=pts){
  color(point_in_polygon(p,path,nonzero=true)==1 ? "green" : "red")
  move(p)circle(r=1.5, $fn=12);
}

Synopsis: Find intersection between 2d or 3d polygon and a line, segment or ray.

Topics: Geometry, Polygons, Lines, Intersection

See Also: polygon_area(), centroid(), polygon_normal(), point_in_polygon()

Usage:

• pt = polygon_line_intersection(poly, line, [bounded], [nonzero], [eps]);

Description:

Takes a possibly bounded line, and a 2D or 3D planar polygon, and finds their intersection. Note the polygon is treated as its boundary and interior, so the intersection may include both points and line segments. If the line does not intersect the polygon returns undef. In 3D if the line is not on the plane of the polygon but intersects it then you get a single intersection point. Otherwise the polygon and line are in the same plane, or when your input is 2D, you will get a list of segments and single point lists. Use is_vector to distinguish these two cases.

In the 2D case, a common result is a list containing a single segment, which lists the two intersection points with the boundary of the polygon. When single points are in the intersection (the line just touches a polygon corner) they appear on the segment list as lists of a single point (like single point segments) so a single point intersection in 2D has the form [[[x,y,z]]] as compared to a single point intersection in 3D which has the form [x,y,z]. You can identify whether an entry in the segment list is a true segment by checking its length, which will be 2 for a segment and 1 for a point.

Arguments:

Example 1: The line intersects the 3d hexagon in a single point.

include <BOSL2/std.scad>
hex = zrot(140,p=rot([-45,40,20],p=path3d(hexagon(r=15))));
line = [[5,0,-13],[-3,-5,13]];
isect = polygon_line_intersection(hex,line);
stroke(hex,closed=true);
stroke(line);
color("red")move(isect)sphere(r=1,$fn=12);

Example 2: In 2D things are more complicated. The output is a list of intersection parts, in the simplest case a single segment.

include <BOSL2/std.scad>
hex = hexagon(r=15);
line = [[-20,10],[25,-7]];
isect = polygon_line_intersection(hex,line);
stroke(hex,closed=true);
stroke(line,endcaps="arrow2");
color("red")
  for(part=isect)
     if(len(part)==1)
       move(part[0]) sphere(r=1);
     else
       stroke(part);

Example 3: Here the line is treated as a ray.

include <BOSL2/std.scad>
hex = hexagon(r=15);
line = [[0,0],[25,-7]];
isect = polygon_line_intersection(hex,line,RAY);
stroke(hex,closed=true);
stroke(line,endcap2="arrow2");
color("red")
  for(part=isect)
     if(len(part)==1)
       move(part[0]) circle(r=1,$fn=12);
     else
       stroke(part);

Example 4: Here the intersection is a single point, which is returned as a single point "path" on the path list.

include <BOSL2/std.scad>
hex = hexagon(r=15);
line = [[15,-10],[15,13]];
isect = polygon_line_intersection(hex,line,RAY);
stroke(hex,closed=true);
stroke(line,endcap2="arrow2");
color("red")
  for(part=isect)
     if(len(part)==1)
       move(part[0]) circle(r=1,$fn=12);
     else
       stroke(part);

Example 5: Another way to get a single segment

include <BOSL2/std.scad>
hex = hexagon(r=15);
line = rot(30,p=[[15,-10],[15,25]],cp=[15,0]);
isect = polygon_line_intersection(hex,line,RAY);
stroke(hex,closed=true);
stroke(line,endcap2="arrow2");
color("red")
  for(part=isect)
     if(len(part)==1)
       move(part[0]) circle(r=1,$fn=12);
     else
       stroke(part);

Example 6: Single segment again

include <BOSL2/std.scad>
star = star(r=15,n=8,step=2);
line = [[20,-5],[-5,20]];
isect = polygon_line_intersection(star,line,RAY);
stroke(star,closed=true);
stroke(line,endcap2="arrow2");
color("red")
  for(part=isect)
     if(len(part)==1)
       move(part[0]) circle(r=1,$fn=12);
     else
       stroke(part);

Example 7: Solution is two points

include <BOSL2/std.scad>
star = star(r=15,n=8,step=3);
line = rot(22.5,p=[[15,-10],[15,20]],cp=[15,0]);
isect = polygon_line_intersection(star,line,SEGMENT);
stroke(star,closed=true);
stroke(line);
color("red")
  for(part=isect)
     if(len(part)==1)
       move(part[0]) circle(r=1,$fn=12);
     else
       stroke(part);

Example 8: Solution is list of three segments

include <BOSL2/std.scad>
star = star(r=25,ir=9,n=8);
line = [[-25,12],[25,12]];
isect = polygon_line_intersection(star,line);
stroke(star,closed=true);
stroke(line,endcaps="arrow2");
color("red")
  for(part=isect)
     if(len(part)==1)
       move(part[0]) circle(r=1,$fn=12);
     else
       stroke(part);

Example 9: Solution is a mixture of segments and points

include <BOSL2/std.scad>
star = star(r=25,ir=9,n=7);
line = [left(10,p=star[8]), right(50,p=star[8])];
isect = polygon_line_intersection(star,line);
stroke(star,closed=true);
stroke(line,endcaps="arrow2");
color("red")
  for(part=isect)
     if(len(part)==1)
       move(part[0]) circle(r=1,$fn=12);
     else
       stroke(part);

Synopsis: Divide a polygon into triangles.

Topics: Geometry, Triangulation

See Also: vnf_triangulate()

Usage:

• triangles = polygon_triangulate(poly, [ind], [error], [eps])

Description:

Given a simple polygon in 2D or 3D, triangulates it and returns a list of triples indexing into the polygon vertices. When the optional argument ind is given, it is used as an index list into poly to define the polygon vertices. In that case, poly may have a length greater than ind. When ind is undefined, all points in poly are considered as vertices of the polygon.

For 2d polygons, the output triangles will have the same winding (CW or CCW) of the input polygon. For 3d polygons, the triangle windings will induce a normal vector with the same direction of the polygon normal.

The function produce correct triangulations for some non-twisted non-simple polygons. A polygon is non-twisted iff it is simple or it has a partition in simple polygons with the same winding such that the intersection of any two partitions is made of full edges and/or vertices of both partitions. These polygons may have "touching" vertices (two vertices having the same coordinates, but distinct adjacencies) and "contact" edges (edges whose vertex pairs have the same pairwise coordinates but are in reversed order) but has no self-crossing. See examples bellow. If all polygon edges are contact edges (polygons with zero area), it returns an empty list for 2d polygons and reports an error for 3d polygons. Triangulation errors are reported either by an assert error (when error=true) or by returning undef (when error=false). Invalid arguments always produce an assert error.

Twisted polygons have no consistent winding and when input to this function usually reports an error but when an error is not reported the outputs are not correct triangulations. The function can work for 3d non-planar polygons if they are close enough to planar but may otherwise report an error for this case.

Arguments:

Example 1: a simple polygon; see from above

include <BOSL2/std.scad>
poly = star(id=10, od=15,n=11);
tris =  polygon_triangulate(poly);
color("lightblue") for(tri=tris) polygon(select(poly,tri));
color("blue")    up(1) for(tri=tris) { stroke(select(poly,tri),.15,closed=true); }
color("magenta") up(2) stroke(poly,.25,closed=true);
color("black")   up(3) debug_vnf([path3d(poly),[]],faces=false,size=1);

Example 2: a polygon with a hole and one "contact" edge; see from above

include <BOSL2/std.scad>
poly = [ [-10,0], [10,0], [0,10], [-10,0], [-4,4], [4,4], [0,2], [-4,4] ];
tris =  polygon_triangulate(poly);
color("lightblue") for(tri=tris) polygon(select(poly,tri));
color("blue")    up(1) for(tri=tris) { stroke(select(poly,tri),.15,closed=true); }
color("magenta") up(2) stroke(poly,.25,closed=true);
color("black")   up(3) debug_vnf([path3d(poly),[]],faces=false,size=1);

Example 3: a polygon with "touching" vertices and no holes; see from above

include <BOSL2/std.scad>
poly = [ [0,0], [5,5], [-5,5], [0,0], [-5,-5], [5,-5] ];
tris =  polygon_triangulate(poly);
color("lightblue") for(tri=tris) polygon(select(poly,tri));
color("blue")    up(1) for(tri=tris) { stroke(select(poly,tri),.15,closed=true); }
color("magenta") up(2) stroke(poly,.25,closed=true);
color("black")   up(3) debug_vnf([path3d(poly),[]],faces=false,size=1);

Example 4: a polygon with "contact" edges and no holes; see from above

include <BOSL2/std.scad>
poly = [ [0,0], [10,0], [10,10], [0,10], [0,0], [3,3], [7,3],
         [7,7], [7,3], [3,3] ];
tris =  polygon_triangulate(poly);
color("lightblue") for(tri=tris) polygon(select(poly,tri));
color("blue")    up(1) for(tri=tris) { stroke(select(poly,tri),.15,closed=true); }
color("magenta") up(2) stroke(poly,.25,closed=true);
color("black")   up(3) debug_vnf([path3d(poly),[]],faces=false,size=1);

Example 5:

include <BOSL2/std.scad>
include <BOSL2/polyhedra.scad>
vnf = regular_polyhedron_info(name="dodecahedron",side=5,info="vnf");
vnf_polyhedron(vnf);
vnf_tri = [vnf[0], [for(face=vnf[1]) each polygon_triangulate(vnf[0], face) ] ];
color("blue")
vnf_wireframe(vnf_tri, width=.15);

Synopsis: Determine if a 2d polygon winds clockwise.

Topics: Geometry, Polygons, Clockwise

See Also: clockwise_polygon(), ccw_polygon(), reverse_polygon()

Usage:

• bool = is_polygon_clockwise(poly);

Description:

Return true if the given 2D simple polygon is in clockwise order, false otherwise. Results for complex (self-intersecting) polygon are indeterminate.

Arguments:

Synopsis: Return clockwise version of a polygon.

Topics: Geometry, Polygons, Clockwise

See Also: is_polygon_clockwise(), ccw_polygon(), reverse_polygon()

Usage:

• newpoly = clockwise_polygon(poly);

Description:

Given a 2D polygon path, returns the clockwise winding version of that path.

Arguments:

Synopsis: Return counter-clockwise version of a polygon.

Topics: Geometry, Polygons, Clockwise

See Also: is_polygon_clockwise(), clockwise_polygon(), reverse_polygon()

Usage:

• newpoly = ccw_polygon(poly);

Description:

Given a 2D polygon poly, returns the counter-clockwise winding version of that poly.

Arguments:

Synopsis: Reverse winding direction of polygon.

Topics: Geometry, Polygons, Clockwise

See Also: is_polygon_clockwise(), ccw_polygon(), clockwise_polygon()

Usage:

• newpoly = reverse_polygon(poly)

Description:

Reverses a polygon's winding direction, while still using the same start point.

Arguments:

Synopsis: Adjust point indexing of polygon to minimize pointwise distance to a reference polygon.

Topics: Geometry, Polygons

See Also: align_polygon(), are_polygons_equal()

Usage:

• newpoly = reindex_polygon(reference, poly);

Description:

Rotates and possibly reverses the point order of a 2d or 3d polygon path to optimize its pairwise point association with a reference polygon. The two polygons must have the same number of vertices and be the same dimension. The optimization is done by computing the distance, norm(reference[i]-poly[i]), between corresponding pairs of vertices of the two polygons and choosing the polygon point index rotation that makes the total sum over all pairs as small as possible. Returns the reindexed polygon. Note that the geometry of the polygon is not changed by this operation, just the labeling of its vertices. If the input polygon is 2d and is oriented opposite the reference then its point order is reversed.

Arguments:

Example 1: The red dots show the 0th entry in the two input path lists. Note that the red dots are not near each other. The blue dot shows the 0th entry in the output polygon

include <BOSL2/std.scad>
pent = subdivide_path([for(i=[0:4])[sin(72*i),cos(72*i)]],30);
circ = circle($fn=30,r=2.2);
reindexed = reindex_polygon(circ,pent);
move_copies(concat(circ,pent)) circle(r=.1,$fn=32);
color("red") move_copies([pent[0],circ[0]]) circle(r=.1,$fn=32);
color("blue") translate(reindexed[0])circle(r=.1,$fn=32);

Example 2: The indexing that minimizes the total distance will not necessarily associate the nearest point of poly with the reference, as in this example where again the blue dot indicates the 0th entry in the reindexed result.

include <BOSL2/std.scad>
pent = move([3.5,-1],p=subdivide_path([for(i=[0:4])[sin(72*i),cos(72*i)]],30));
circ = circle($fn=30,r=2.2);
reindexed = reindex_polygon(circ,pent);
move_copies(concat(circ,pent)) circle(r=.1,$fn=32);
color("red") move_copies([pent[0],circ[0]]) circle(r=.1,$fn=32);
color("blue") translate(reindexed[0])circle(r=.1,$fn=32);

Synopsis: Find best alignment of a 2d polygon to a reference 2d polygon over a set of transformations.

Topics: Geometry, Polygons

See Also: reindex_polygon(), are_polygons_equal()

Usage:

• newpoly = align_polygon(reference, poly, [angles], [cp], [tran], [return_ind]);

Description:

Find the best alignment of a specified 2D polygon with a reference 2D polygon over a set of transformations. You can specify a list or range of angles and a centerpoint or you can give a list of arbitrary 2d transformation matrices. For each transformation or angle, the polygon is reindexed, which is a costly operation so if run time is a problem, use a smaller sampling of angles or transformations. By default returns the rotated and reindexed polygon. You can also request that the best angle or the index into the transformation list be returned.

Arguments:

Example 1: Rotating the poorly aligned light gray triangle by 105 degrees produces the best alignment, shown in blue:

include <BOSL2/std.scad>
ellipse = yscale(3,circle(r=10, $fn=32));
tri = move([-50/3,-9],
           subdivide_path([[0,0], [50,0], [0,27]], 32));
aligned = align_polygon(ellipse,tri, [0:5:180]);
color("white")stroke(tri,width=.5,closed=true);
stroke(ellipse, width=.5, closed=true);
color("blue")stroke(aligned,width=.5,closed=true);

Example 2: Translating a triangle (light gray) to the best alignment (blue)

include <BOSL2/std.scad>
ellipse = yscale(2,circle(r=10, $fn=32));
tri = subdivide_path([[0,0], [27,0], [-7,50]], 32);
T = [for(x=[-10:0], y=[-30:-15]) move([x,y])];
aligned = align_polygon(ellipse,tri, trans=T);
color("white")stroke(tri,width=.5,closed=true);
stroke(ellipse, width=.5, closed=true);
color("blue")stroke(aligned,width=.5,closed=true);

Synopsis: Check if two polygons (not necessarily in the same point order) are equal.

Topics: Geometry, Polygons, Comparators

See Also: reindex_polygon(), align_polygon()

Usage:

• bool = are_polygons_equal(poly1, poly2, [eps])

Description:

Returns true if poly1 and poly2 are the same polongs within given epsilon tolerance.

Arguments:

Example 1:

include <BOSL2/std.scad>
are_polygons_equal(pentagon(r=4),
               rot(360/5, p=pentagon(r=4))); // returns true
are_polygons_equal(pentagon(r=4),
               rot(90, p=pentagon(r=4)));    // returns false

Synopsis: Convex hull of a list of 2d or 3d points. ^[Ext]

Topics: Geometry, Hulling

See Also: hull_points(), hull2d_path(), hull3d_faces()

Usage:

• face_list_or_index_list = hull(points);

Description:

Takes a list of 2D or 3D points (but not both in the same list) and returns either the list of indexes into points that forms the 2D convex hull perimeter path, or the list of faces that form the 3d convex hull surface. Each face is a list of indexes into points. If the input points are co-linear, the result will be the indexes of the two extrema points. If the input points are co-planar, the results will be a simple list of vertex indices that will form a planar perimeter. Otherwise a list of faces will be returned, where each face is a simple list of vertex indices for the perimeter of the face.

Arguments:

Synopsis: Convex hull of a list of 2d or 3d points.

Topics: Geometry, Hulling

See Also: hull(), hull2d_path(), hull3d_faces()

Usage:

• hull_points(points, [fast]);

Description:

If given a list of 2D points, creates a 2D convex hull polygon that encloses all those points. If given a list of 3D points, creates a 3D polyhedron that encloses all the points. This should handle about 4000 points in slow mode. If fast is set to true, this should be able to handle far more. When fast mode is off, 3d hulls that lie in a plane will produce a single face of a polyhedron, which can be viewed in preview but will not render.

Arguments:

Example 1:

include <BOSL2/std.scad>
pts = [[-10,-10], [0,10], [10,10], [12,-10]];
hull_points(pts);

Example 2:

include <BOSL2/std.scad>
pts = [for (phi = [30:60:150], theta = [0:60:359]) spherical_to_xyz(10, theta, phi)];
hull_points(pts);

Synopsis: Convex hull of a list of 2d points.

Topics: Geometry, Hulling

See Also: hull(), hull_points(), hull3d_faces()

Usage:

• index_list = hull2d_path(points,all)

Description:

Takes a list of arbitrary 2D points, and finds the convex hull polygon to enclose them. Returns a path as a list of indices into points. When all==true, returns extra points that are on edges of the hull.

Arguments:

Example 1:

include <BOSL2/std.scad>
pts = [[-10,-10], [0,10], [10,10], [12,-10]];
path = hull2d_path(pts);
move_copies(pts) color("red") circle(1,$fn=12);
polygon(points=pts, paths=[path]);

Synopsis: Convex hull of a list of 3d points.

Topics: Geometry, Hulling

See Also: hull(), hull_points(), hull2d_path()

Usage:

• faces = hull3d_faces(points)

Description:

Takes a list of arbitrary 3D points, and finds the convex hull polyhedron to enclose them. Returns a list of triangular faces, where each face is a list of indexes into the given points list. The output will be valid for use with the polyhedron command, but may include vertices that are in the interior of a face of the hull, so it is not necessarily the minimal representation of the hull. If all points passed to it are coplanar, then the return is the list of indices of points forming the convex hull polygon.

Example 1:

include <BOSL2/std.scad>
pts = [[-20,-20,0], [20,-20,0], [0,20,5], [0,0,20]];
faces = hull3d_faces(pts);
move_copies(pts) color("red") sphere(1);
%polyhedron(points=pts, faces=faces);

Synopsis: Check if a polygon is convex.

Topics: Geometry, Convexity, Test

See Also: clockwise_polygon(), ccw_polygon()

Usage:

• bool = is_polygon_convex(poly, [eps]);

Description:

Returns true if the given 2D or 3D polygon is convex. The result is meaningless if the polygon is not simple (self-crossing) or non coplanar. If the points are collinear or not coplanar an error may be generated.

Arguments:

Example 1:

include <BOSL2/std.scad>
test1 = is_polygon_convex(circle(d=50));                                 // Returns: true
test2 = is_polygon_convex(rot([50,120,30], p=path3d(circle(1,$fn=50)))); // Returns: true
spiral = [for (i=[0:36]) let(a=-i*10) (10+i)*[cos(a),sin(a)]];
test = is_polygon_convex(spiral);                                        // Returns: false

Synopsis: Compute distance between convex hull of two point lists.

Topics: Geometry, Convexity, Distance

Usage:

• dist = convex_distance(points1, points2,eps);

Description:

Returns the smallest distance between a point in convex hull of points1 and a point in the convex hull of points2. All the points in the lists should have the same dimension, either 2D or 3D. A zero result means the hulls intercept whithin a tolerance eps.

Arguments:

Example 1:

include <BOSL2/std.scad>
pts1 = move([-3,0], p=square(3,center=true));
pts2 = rot(a=45, p=square(2,center=true));
pts3 = [ [2,0], [1,2],[3,2], [3,-2], [1,-2] ];
polygon(pts1);
polygon(pts2);
polygon(pts3);
echo(convex_distance(pts1,pts2)); // Returns: 0.0857864
echo(convex_distance(pts2,pts3)); // Returns: 0

Example 2:

include <BOSL2/std.scad>
sphr1 = sphere(2,$fn=10);
sphr2 = move([4,0,0], p=sphr1);
sphr3 = move([4.5,0,0], p=sphr1);
vnf_polyhedron(sphr1);
vnf_polyhedron(sphr2);
echo(convex_distance(sphr1[0], sphr2[0])); // Returns: 0
echo(convex_distance(sphr1[0], sphr3[0])); // Returns: 0.5

Synopsis: Check whether the convex hulls of two point lists intersect.

Topics: Geometry, Convexity, Collision, Intersection

Usage:

• bool = convex_collision(points1, points2, [eps]);

Description:

Returns true if the convex hull of points1 intersects the convex hull of points2 otherwise, false. All the points in the lists should have the same dimension, either 2D or 3D. This function is tipically faster than convex_distance to find a non-collision.

Arguments:

Example 1:

include <BOSL2/std.scad>
pts1 = move([-3,0], p=square(3,center=true));
pts2 = rot(a=45, p=square(2,center=true));
pts3 = [ [2,0], [1,2],[3,2], [3,-2], [1,-2] ];
polygon(pts1);
polygon(pts2);
polygon(pts3);
echo(convex_collision(pts1,pts2)); // Returns: false
echo(convex_collision(pts2,pts3)); // Returns: true

Example 2:

include <BOSL2/std.scad>
sphr1 = sphere(2,$fn=10);
sphr2 = move([4,0,0], p=sphr1);
sphr3 = move([4.5,0,0], p=sphr1);
vnf_polyhedron(sphr1);
vnf_polyhedron(sphr2);
echo(convex_collision(sphr1[0], sphr2[0])); // Returns: true
echo(convex_collision(sphr1[0], sphr3[0])); // Returns: false

Synopsis: Extract axis and rotation angle from a rotation matrix.

Topics: Affine, Matrices, Transforms

Usage:

• info = rot_decode(rotation,[long]); // Returns: [angle,axis,cp,translation]

Description:

Given an input 3D rigid transformation operator (one composed of just rotations and translations) represented as a 4x4 matrix, compute the rotation and translation parameters of the operator. Returns a list of the four parameters, the angle, in the interval [0,180], the rotation axis as a unit vector, a centerpoint for the rotation, and a translation. If you set parms = rot_decode(rotation) then the transformation can be reconstructed from parms as move(parms[3]) * rot(a=parms[0],v=parms[1],cp=parms[2]). This decomposition makes it possible to perform interpolation. If you construct a transformation using rot the decoding may flip the axis (if you gave an angle outside of [0,180]). The returned axis will be a unit vector, and the centerpoint lies on the plane through the origin that is perpendicular to the axis. It may be different than the centerpoint you used to construct the transformation.

If you set long to true then return the reversed rotation, with the angle in [180,360].

Arguments:

Example 1:

include <BOSL2/std.scad>
info = rot_decode(rot(45));
       // Returns: [45, [0,0,1], [0,0,0], [0,0,0]]
info = rot_decode(rot(a=37, v=[1,2,3], cp=[4,3,-7])));
       // Returns: [37, [0.26, 0.53, 0.80], [4.8, 4.6, -4.6], [0,0,0]]
info = rot_decode(left(12)*xrot(-33));
       // Returns: [33, [-1,0,0], [0,0,0], [-12,0,0]]
info = rot_decode(translate([3,4,5]));
       // Returns: [0, [0,0,1], [0,0,0], [3,4,5]]