math::geometry - Geometrical computations

       This document, and the package it describes, will undoubtedly contain bugs and  other  problems.   Please
       report     such     in     the     category     math::geometry    of    the    TcllibTrackers
       [http://core.tcl.tk/tcllib/reportlist].  Please also report any ideas for enhancements you may  have  for
       either package and/or documentation.

       When proposing code changes, please provide unifieddiffs, i.e the output of diff-u.

       Note  further  that  attachments  are strongly preferred over inlined patches. Attachments can be made by
       going to the Edit form of the ticket immediately after its creation, and then using the left-most  button
       in the secondary navigation bar.

       Mathematics

       The coordinate system used by the package is the ordinary cartesian system, where the positive x-axis  is
       directed  to  the  right  and the positive y-axis is directed upwards.  Angles and directions are defined
       with respect to the positive x-axis in a counter-clockwise direction, so that an angle of 90  degrees  is
       the direction of the positive y-axis.  Note that the Tk canvas coordinates differ from this, as there the
       origin  is located in the upper left corner of the window. Up to and including version 1.3, the direction
       and octant procedures of this package used this convention inconsistently.

       Copyright (c) 2001 by Ideogramic ApS and other parties
       Copyright (c) 2010 by Andreas Kupries
       Copyright (c) 2010 by Kevin Kenny
       Copyright (c) 2018 by Arjen Markus
       Copyright (c) 2020 by Manfred Rosenberger

tcllib                                                1.4.2                                 math::geometry(3tcl)

       The  math::geometry  package  is  a  collection  of  functions for computations and manipulations on two-
       dimensional geometrical objects, such as points, lines and polygons.

       The geometrical objects are implemented as plain lists of coordinates.  For instance a line is defined by
       a list of four numbers, the x- and y-coordinate of a first point and the x- and y-coordinates of a second
       point on the line.

       Note:   In    version    1.4.0    an    inconsistency    was    repaired    -    see    https://core.tcl-lang.org/tcllib/tktview?name=fb4812f82b.  More in COORDINATESYSTEM

       The  various  types  of  object are recognised by the number of coordinate pairs and the context in which
       they are used: a list of four elements can be regarded as an infinite line, a  finite  line  segment  but
       also as a polyline of one segment and a point set of two points.

       Currently the following types of objects are distinguished:

       •      point - a list of two coordinates representing the x- and y-coordinates respectively.

       •      line  - a list of four coordinates, interpreted as the x- and y-coordinates of two distinct points
              on the line.

       •      linesegment - a list of four coordinates, interpreted as the x- and y-coordinates  of  the  first
              and the last points on the line segment.

       •      polyline  - a list of an even number of coordinates, interpreted as the x- and y-coordinates of an
              ordered set of points.

       •      polygon - like a polyline, but the implicit assumption is that the  polyline  is  closed  (if  the
              first and last points do not coincide, the missing segment is automatically added).

       •      pointset - again a list of an even number of coordinates, but the points are regarded without any
              ordering.

       •      circle - a list of three numbers, the first two are the coordinates of the centre and the third is
              the radius.

       angle, distance, line, math, plane geometry, point

       math::geometry - Geometrical computations

       The package defines the following public procedures:

       ::math::geometry::+point1point2
              Compute the sum of the two vectors given as points and return it.  The result is a vector as well.

       ::math::geometry::-point1point2
              Compute  the  difference  (point1  - point2) of the two vectors given as points and return it. The
              result is a vector as well.

       ::math::geometry::pxy
              Construct a point from its coordinates and return it as the result of the command.

       ::math::geometry::distancepoint1point2
              Compute the distance between the two points and return it as the result of the command. This is in
              essence the same as

                  math::geometry::length [math::geomtry::- point1 point2]

       ::math::geometry::lengthpoint
              Compute the length of the vector and return it as the result of the command.

       ::math::geometry::s*factorpoint
              Scale the vector by the factor and return it as the result of the command. This  is  a  vector  as
              well.

       ::math::geometry::directionangle
              Given  the  angle  in degrees this command computes and returns the unit vector pointing into this
              direction. The vector for angle == 0 points to the right (east), and for angle == 90 up (north).

       ::math::geometry::hlength
              Returns a horizontal vector on the X-axis of the specified length.  Positive lengths point to  the
              right (east).

       ::math::geometry::vlength
              Returns  a  vertical  vector  on  the Y-axis of the specified length.  Positive lengths point down
              (south).

       ::math::geometry::betweenpoint1point2s
              Compute the point which is at relative distance s between the two points  and  return  it  as  the
              result  of  the  command.  A relative distance of 0 returns point1, the distance 1 returns point2.
              Distances < 0 or > 1 extrapolate along the line between the two point.

       ::math::geometry::octantpoint
              Compute the octant of the circle the point is in and return it as the result of the  command.  The
              possible results are

              [1]    east

              [2]    northeast

              [3]    north

              [4]    northwest

              [5]    west

              [6]    southwest

              [7]    south

              [8]    southeast

              Each  octant  is  the arc of the circle +/- 22.5 degrees from the cardinal direction the octant is
              named for.

       ::math::geometry::rectnwse
              Construct a rectangle from its northwest and southeast corners and return it as the result of  the
              command.

       ::math::geometry::nwserect
              Extract  the northwest and southeast corners of the rectangle and return them as the result of the
              command (a 2-element list containing the points, in the named order).

       ::math::geometry::angleline
              Calculate the angle from the positive x-axis to a given line (in two dimensions only).

              list line
                     Coordinates of the line

       ::math::geometry::angleBetweenvector1vector2
              Calculate the angle between two vectors (in degrees)

              list vector1
                     First vector

              list vector2
                     Second vector

       ::math::geometry::inproductvector1vector2
              Calculate the inner product of two vectors

              list vector1
                     First vector

              list vector2
                     Second vector

       ::math::geometry::areaParallellogramvector1vector2
              Calculate the area of the parallellogram with the two vectors as its sides

              list vector1
                     First vector

              list vector2
                     Second vector

       ::math::geometry::calculateDistanceToLinePline
              Calculate the distance of point P to the (infinite) line and return the result

              list P List of two numbers, the coordinates of the point

              list line
                     List of four numbers, the coordinates of two points on the line

       ::math::geometry::calculateDistanceToLineSegmentPlinesegment
              Calculate the distance of point P to the (finite) line segment and return the result.

              list P List of two numbers, the coordinates of the point

              list linesegment
                     List of four numbers, the coordinates of the first and last points of the line segment

       ::math::geometry::calculateDistanceToPolylinePpolyline
              Calculate the distance of point P to the polyline and return the  result.  Note  that  a  polyline
              needs not to be closed.

              list P List of two numbers, the coordinates of the point

              list polyline
                     List of numbers, the coordinates of the vertices of the polyline

       ::math::geometry::calculateDistanceToPolygonPpolygon
              Calculate the distance of point P to the polygon and return the result. If the list of coordinates
              is not closed (first and last points differ), it is automatically closed.

              list P List of two numbers, the coordinates of the point

              list polygon
                     List of numbers, the coordinates of the vertices of the polygon

       ::math::geometry::findClosestPointOnLinePline
              Return the point on a line which is closest to a given point.

              list P List of two numbers, the coordinates of the point

              list line
                     List of four numbers, the coordinates of two points on the line

       ::math::geometry::findClosestPointOnLineSegmentPlinesegment
              Return the point on a linesegment which is closest to a given point.

              list P List of two numbers, the coordinates of the point

              list linesegment
                     List of four numbers, the first and last points on the line segment

       ::math::geometry::findClosestPointOnPolylinePpolyline
              Return the point on a polyline which is closest to a given point.

              list P List of two numbers, the coordinates of the point

              list polyline
                     List of numbers, the vertices of the polyline

       ::math::geometry::lengthOfPolylinepolyline
              Return the length of the polyline (note: it not regarded as a polygon)

              list polyline
                     List of numbers, the vertices of the polyline

       ::math::geometry::movePointInDirectionPdirectiondist
              Move  a  point  over  a given distance in a given direction and return the new coordinates (in two
              dimensions only).

              list P Coordinates of the point to be moved

              double direction
                     Direction (in degrees; 0 is to the right, 90 upwards)

              list dist
                     Distance over which to move the point

       ::math::geometry::lineSegmentsIntersectlinesegment1linesegment2
              Check if two line segments intersect or coincide. Returns 1 if that is the case, 0  otherwise  (in
              two dimensions only). If an endpoint of one segment lies on the other segment (or is very close to
              the segment), they are considered to intersect

              list linesegment1
                     First line segment

              list linesegment2
                     Second line segment

       ::math::geometry::findLineSegmentIntersectionlinesegment1linesegment2
              Find  the  intersection  point  of  two  line  segments.  Return  the  coordinates or the keywords
              "coincident" or "none" if the line  segments  coincide  or  have  no  points  in  common  (in  two
              dimensions only).

              list linesegment1
                     First line segment

              list linesegment2
                     Second line segment

       ::math::geometry::findLineIntersectionline1line2
              Find  the  intersection  point  of  two  (infinite)  lines. Return the coordinates or the keywords
              "coincident" or "none" if the lines coincide or have no points in common (in two dimensions only).

              list line1
                     First line

              list line2
                     Second line

              See section References for details on the algorithm and math behind it.

       ::math::geometry::polylinesIntersectpolyline1polyline2
              Check if two polylines intersect or not (in two dimensions only).

              list polyline1
                     First polyline

              list polyline2
                     Second polyline

       ::math::geometry::polylinesBoundingIntersectpolyline1polyline2granularity
              Check whether two polylines intersect, but reduce the correctness  of  the  result  to  the  given
              granularity.  Use this for faster, but weaker, intersection checking.

              How it works:

              Each  polyline is split into a number of smaller polylines, consisting of granularity points each.
              If a pair of those smaller lines'  bounding  boxes  intersect,  then  this  procedure  returns  1,
              otherwise it returns 0.

              list polyline1
                     First polyline

              list polyline2
                     Second polyline

              int granularity
                     Number of points in each part (<=1 means check every edge)

       ::math::geometry::intervalsOverlapy1y2y3y4strict
              Check if two intervals overlap.

              double y1,y2
                     Begin and end of first interval

              double y3,y4
                     Begin and end of second interval

              logical strict
                     Check for strict or non-strict overlap

       ::math::geometry::rectanglesOverlapP1P2Q1Q2strict
              Check if two rectangles overlap.

              list P1
                     upper-left corner of the first rectangle

              list P2
                     lower-right corner of the first rectangle

              list Q1
                     upper-left corner of the second rectangle

              list Q2
                     lower-right corner of the second rectangle

              list strict
                     choosing strict or non-strict interpretation

       ::math::geometry::bboxpolyline
              Calculate  the  bounding box of a polyline. Returns a list of four coordinates: the upper-left and
              the lower-right corner of the box.

              list polyline
                     The polyline to be examined

       ::math::geometry::overlapBBoxpolyline1polyline2 ?strict?
              Check if the bounding boxes of two polylines overlap or not.

              Arguments:

              list polyline1
                     The first polyline

              list polyline1
                     The second polyline

              int strict
                     Whether strict overlap is to checked (1) or if the bounding boxes may touch (0, default)

       ::math::geometry::pointInsideBBoxbboxpoint

              Check if the point is inside or on the bounding box or not.  Arguments:

              list bbox
                     The bounding box given as a list of x/y coordinates

              list point
                     The point to be checked

       ::math::geometry::cathetusPointpapbcathetusLength ?location?
              Return the third point of the rectangular triangle defined by the two  given  end  points  of  the
              hypothenusa.   The  triangle's  side  from  point A (or B, if the location is given as "b") to the
              third point is the cathetus length.  If the cathetus' length is  lower  than  the  length  of  the
              hypothenusa, an empty list is returned.

              Arguments:

              list pa
                     The starting point on hypotenuse

              list pb
                     The ending point on hypotenuse

              float cathetusLength
                     The length of the cathetus of the triangle

              string location
                     The  location of the given cathetus, "a" means given cathetus shares point pa (default) "b"
                     means given cathetus shares point pb

       ::math::geometry::parallellineoffset ?orient?
              Return a line parallel to the given line, with a distance "offset". The orientation is  determined
              by the two points defining the line.

              Arguments:

              list line
                     The given line

              float offset
                     The distance to the given line

              string orient
                     Orientation of the new line with respect to the given line (defaults to "right")

       ::math::geometry::unitVectorline
              Return  a  unit  vector  from  the given line or direction, if the line argument is a single point
              (then a line through the origin is assumed) Arguments:

              list line
                     The line in question (or a single point, implying a line through the origin)

       ::math::geometry::pointInsidePolygonPpolyline
              Determine if a point is completely inside a polygon. If the point touches the  polygon,  then  the
              point is not completely inside the polygon.

              list P Coordinates of the point

              list polyline
                     The polyline to be examined

       ::math::geometry::pointInsidePolygonAltPpolyline
              Determine  if  a  point is completely inside a polygon. If the point touches the polygon, then the
              point is not completely inside the polygon. Note: this alternative procedure  uses  the  so-called
              winding number to determine this. It handles self-intersecting polygons in a "natural" way.

              list P Coordinates of the point

              list polyline
                     The polyline to be examined

       ::math::geometry::rectangleInsidePolygonP1P2polyline
              Determine  if  a  rectangle is completely inside a polygon. If polygon touches the rectangle, then
              the rectangle is not complete inside the polygon.

              list P1
                     Upper-left corner of the rectangle

              list P2
                     Lower-right corner of the rectangle

              list polygon
                     The polygon in question

       ::math::geometry::areaPolygonpolygon
              Calculate the area of a polygon.

              list polygon
                     The polygon in question

       ::math::geometry::translatevectorpolyline
              Translate a polyline over a given vector

              list vector
                     Translation vector

              list polyline
                     The polyline to be translated

       ::math::geometry::rotateanglepolyline
              Rotate a polyline over a given angle (degrees) around the origin

              list angle
                     Angle over which to rotate the polyline (degrees)

              list polyline
                     The polyline to be rotated

       ::math::geometry::rotateAboutpanglepolyline
              Rotate a polyline around a given point p and return the new polyline.

              Arguments:

              list p The point of rotation

              float angle
                     The angle over which to rotate the polyline (degrees)

              list polyline
                     The polyline to be rotated

       ::math::geometry::reflectanglepolyline
              Reflect a polyline in a line through the origin at a given angle (degrees) to the x-axis

              list angle
                     Angle of the line of reflection (degrees)

              list polyline
                     The polyline to be reflected

       ::math::geometry::degToRadangle
              Convert from degrees to radians

              list angle
                     Angle in degrees

       ::math::geometry::radToDegangle
              Convert from radians to degrees

              list angle
                     Angle in radians

       ::math::geometry::circlecentreradius
              Convenience procedure to create a circle from a point and a radius.

              list centre
                     Coordinates of the circle centre

              list radius
                     Radius of the circle

       ::math::geometry::circleTwoPointspoint1point2
              Convenience procedure to create a circle from two points on its circumference The  centre  is  the
              point between the two given points, the radius is half the distance between them.

              list point1
                     First point

              list point2
                     Second point

       ::math::geometry::pointInsideCirclepointcircle
              Determine if the given point is inside the circle or on the circumference (1) or outside (0).

              list point
                     Point to be checked

              list circle
                     Circle that may or may not contain the point

       ::math::geometry::lineIntersectsCirclelinecircle
              Determine if the given line intersects the circle or touches it (1) or does not (0).

              list line
                     Line to be checked

              list circle
                     Circle that may or may not be intersected

       ::math::geometry::lineSegmentIntersectsCirclesegmentcircle
              Determine if the given line segment intersects the circle or touches it (1) or does not (0).

              list segment
                     Line segment to be checked

              list circle
                     Circle that may or may not be intersected

       ::math::geometry::intersectionLineWithCirclelinecircle
              Determine  the points at which the given line intersects the circle. There can be zero, one or two
              points. (If the line touches the circle or is  close  to  it,  then  one  point  is  returned.  An
              arbitrary margin of 1.0e-10 times the radius is used to determine this situation.)

              list line
                     Line to be checked

              list circle
                     Circle that may or may not be intersected

       ::math::geometry::intersectionCircleWithCirclecircle1circle2
              Determine  the  points  at  which  the  given two circles intersect. There can be zero, one or two
              points. (If the two circles touch the circle or are very close, then one  point  is  returned.  An
              arbitrary  margin  of  1.0e-10 times the mean of the radii of the two circles is used to determine
              this situation.)

              list circle1
                     First circle

              list circle2
                     Second circle

       ::math::geometry::tangentLinesToCirclepointcircle
              Determine the tangent lines from the given point to the circle. There can  be  zero,  one  or  two
              lines.  (If  the  point  is  on  the  cirucmference  or very close to the circle, then one line is
              returned. An arbitrary margin of 1.0e-10 times the radius of the circle is used to determine  this
              situation.)

              list point
                     Point in question

              list circle
                     Circle to which the tangent lines are to be determined

       ::math::geometry::intersectionPolylinespolyline1polyline2 ?mode? ?granularity?
              Return the first point or all points where the two polylines intersect. If the number of points in
              the polylines is large, you can use the granularity to get an approximate answer faster.

              Arguments:

              list polyline1
                     The first polyline

              list polyline2
                     The second polyline

              string mode
                     Whether to return only the first (default) or to return all intersection points ("all")

              int granularity
                     The  number  of points that will be skipped plus 1 in the search for intersection points (1
                     or smaller means an exact answer is returned)

       ::math::geometry::intersectionPolylineCirclepolylinecircle ?mode? ?granularity?
              Return the first point or all points where the polyline intersects the circle. If  the  number  of
              points in the polyline is large, you can use the granularity to get an approximate answer faster.

              Arguments:

              list polyline
                     The polyline that may intersect the circle

              list circle
                     The circle in question

              string mode
                     Whether to return only the first (default) or to return all intersection points ("all")

              int granularity
                     The  number  of points that will be skipped plus 1 in the search for intersection points (1
                     or smaller means an exact answer is returned)

       ::math::geometry::polylineCutOriginpolyline1polyline2 ?granularity?
              Return the part of the first polyline from the origin  up  to  the  first  intersection  with  the
              second.  If  the  number of points in the polyline is large, you can use the granularity to get an
              approximate answer faster.

              Arguments:

              list polyline1
                     The first polyline (from which a part is to be returned)

              list polyline2
                     The second polyline

              int granularity
                     The number of points that will be skipped plus 1 in the search for intersection  points  (1
                     or smaller means an exact answer is returned)

       ::math::geometry::polylineCutEndpolyline1polyline2 ?granularity?
              Return the part of the first polyline from the last intersection point with the second to the end.
              If  the  number  of  points  in  the  polyline  is  large,  you  can use the granularity to get an
              approximate answer faster.

              Arguments:

              list polyline1
                     The first polyline (from which a part is to be returned)

              list polyline2
                     The second polyline

              int granularity
                     The number of points that will be skipped plus 1 in the search for intersection  points  (1
                     or smaller means an exact answer is returned)

       ::math::geometry::splitPolylinepolylinenumberVertex
              Split  the  poyline  into  a  set  of  polylines where each separate polyline holds "numberVertex"
              vertices between the two end points.

              Arguments:

              list polyline
                     The polyline to be split up

              int numberVertex
                     The number of "internal" vertices

       ::math::geometry::enrichPolylinepolylineaccuracy
              Split up each segment of a polyline into a number of smaller segments and return the result.

              Arguments:

              list polyline
                     The polyline to be refined

              int accuracy
                     The number of subsegments to be created

       ::math::geometry::cleanupPolylinepolyline
              Remove duplicate neighbouring vertices and return the result.

              Arguments:

              list polyline
                     The polyline to be cleaned up

       [1]    PolygonIntersection [http:/wiki.tcl.tk/12070]

       [2]    http://en.wikipedia.org/wiki/Line-line_intersection

       [3]    http://local.wasp.uwa.edu.au/~pbourke/geometry/lineline2d/

       package require Tcl?8.59?

       package require math::geometry?1.4.2?::math::geometry::+point1point2::math::geometry::-point1point2::math::geometry::pxy::math::geometry::distancepoint1point2::math::geometry::lengthpoint::math::geometry::s*factorpoint::math::geometry::directionangle::math::geometry::hlength::math::geometry::vlength::math::geometry::betweenpoint1point2s::math::geometry::octantpoint::math::geometry::rectnwse::math::geometry::nwserect::math::geometry::angleline::math::geometry::angleBetweenvector1vector2::math::geometry::inproductvector1vector2::math::geometry::areaParallellogramvector1vector2::math::geometry::calculateDistanceToLinePline::math::geometry::calculateDistanceToLineSegmentPlinesegment::math::geometry::calculateDistanceToPolylinePpolyline::math::geometry::calculateDistanceToPolygonPpolygon::math::geometry::findClosestPointOnLinePline::math::geometry::findClosestPointOnLineSegmentPlinesegment::math::geometry::findClosestPointOnPolylinePpolyline::math::geometry::lengthOfPolylinepolyline::math::geometry::movePointInDirectionPdirectiondist::math::geometry::lineSegmentsIntersectlinesegment1linesegment2::math::geometry::findLineSegmentIntersectionlinesegment1linesegment2::math::geometry::findLineIntersectionline1line2::math::geometry::polylinesIntersectpolyline1polyline2::math::geometry::polylinesBoundingIntersectpolyline1polyline2granularity::math::geometry::intervalsOverlapy1y2y3y4strict::math::geometry::rectanglesOverlapP1P2Q1Q2strict::math::geometry::bboxpolyline::math::geometry::overlapBBoxpolyline1polyline2 ?strict?

       ::math::geometry::pointInsideBBoxbboxpoint::math::geometry::cathetusPointpapbcathetusLength ?location?

       ::math::geometry::parallellineoffset ?orient?

       ::math::geometry::unitVectorline::math::geometry::pointInsidePolygonPpolyline::math::geometry::pointInsidePolygonAltPpolyline::math::geometry::rectangleInsidePolygonP1P2polyline::math::geometry::areaPolygonpolygon::math::geometry::translatevectorpolyline::math::geometry::rotateanglepolyline::math::geometry::rotateAboutpanglepolyline::math::geometry::reflectanglepolyline::math::geometry::degToRadangle::math::geometry::radToDegangle::math::geometry::circlecentreradius::math::geometry::circleTwoPointspoint1point2::math::geometry::pointInsideCirclepointcircle::math::geometry::lineIntersectsCirclelinecircle::math::geometry::lineSegmentIntersectsCirclesegmentcircle::math::geometry::intersectionLineWithCirclelinecircle::math::geometry::intersectionCircleWithCirclecircle1circle2::math::geometry::tangentLinesToCirclepointcircle::math::geometry::intersectionPolylinespolyline1polyline2 ?mode? ?granularity?

       ::math::geometry::intersectionPolylineCirclepolylinecircle ?mode? ?granularity?

       ::math::geometry::polylineCutOriginpolyline1polyline2 ?granularity?

       ::math::geometry::polylineCutEndpolyline1polyline2 ?granularity?

       ::math::geometry::splitPolylinepolylinenumberVertex::math::geometry::enrichPolylinepolylineaccuracy::math::geometry::cleanupPolylinepolyline

________________________________________________________________________________________________________________