math::geometry(3tcl)

📦
version 2.0 · 3 versions
, in debian trixie, ubuntu questing, ubuntu resolute, ubuntu stonking

✨ NAME ✨

math::geometry — Geometrical computations 💅

(And yes bestie, this is the math::geometry(3tcl) page from the Tcl Math Library. Buckle up.)

🌸 SYNOPSIS 🌸

package require Tcl ?8.5 9?

package require math::geometry ?1.4.2?

::math::geometry::+ point1 point2

::math::geometry::- point1 point2

::math::geometry::p x y

::math::geometry::distance point1 point2

::math::geometry::length point

::math::geometry::s* factor point

::math::geometry::direction angle

::math::geometry::h length

::math::geometry::v length

::math::geometry::between point1 point2 s

::math::geometry::octant point

::math::geometry::rect nw se

::math::geometry::nwse rect

::math::geometry::angle line

::math::geometry::angleBetween vector1 vector2

::math::geometry::inproduct vector1 vector2

::math::geometry::areaParallellogram vector1 vector2

::math::geometry::calculateDistanceToLine P line

::math::geometry::calculateDistanceToLineSegment P linesegment

::math::geometry::calculateDistanceToPolyline P polyline

::math::geometry::calculateDistanceToPolygon P polygon

::math::geometry::findClosestPointOnLine P line

::math::geometry::findClosestPointOnLineSegment P linesegment

::math::geometry::findClosestPointOnPolyline P polyline

::math::geometry::lengthOfPolyline polyline

::math::geometry::movePointInDirection P direction dist

::math::geometry::lineSegmentsIntersect linesegment1 linesegment2

::math::geometry::findLineSegmentIntersection linesegment1 linesegment2

::math::geometry::findLineIntersection line1 line2

::math::geometry::polylinesIntersect polyline1 polyline2

::math::geometry::polylinesBoundingIntersect polyline1 polyline2 granularity

::math::geometry::intervalsOverlap y1 y2 y3 y4 strict

::math::geometry::rectanglesOverlap P1 P2 Q1 Q2 strict

::math::geometry::bbox polyline

::math::geometry::overlapBBox polyline1 polyline2 ?strict?

::math::geometry::pointInsideBBox bbox point

::math::geometry::cathetusPoint pa pb cathetusLength ?location?

::math::geometry::parallel line offset ?orient?

::math::geometry::unitVector line

::math::geometry::pointInsidePolygon P polyline

::math::geometry::pointInsidePolygonAlt P polyline

::math::geometry::rectangleInsidePolygon P1 P2 polyline

::math::geometry::areaPolygon polygon

::math::geometry::translate vector polyline

::math::geometry::rotate angle polyline

::math::geometry::rotateAbout p angle polyline

::math::geometry::reflect angle polyline

::math::geometry::degToRad angle

::math::geometry::radToDeg angle

::math::geometry::circle centre radius

::math::geometry::circleTwoPoints point1 point2

::math::geometry::pointInsideCircle point circle

::math::geometry::lineIntersectsCircle line circle

::math::geometry::lineSegmentIntersectsCircle segment circle

::math::geometry::intersectionLineWithCircle line circle

::math::geometry::intersectionCircleWithCircle circle1 circle2

::math::geometry::tangentLinesToCircle point circle

::math::geometry::intersectionPolylines polyline1 polyline2 ?mode? ?granularity?

::math::geometry::intersectionPolylineCircle polyline circle ?mode? ?granularity?

::math::geometry::polylineCutOrigin polyline1 polyline2 ?granularity?

::math::geometry::polylineCutEnd polyline1 polyline2 ?granularity?

::math::geometry::splitPolyline polyline numberVertex

::math::geometry::enrichPolyline polyline accuracy

::math::geometry::cleanupPolyline polyline

🦋 DESCRIPTION 🦋

okay so the math::geometry package is literally a whole collection of functions for computations and manipulations on two-dimensional geometrical objects, like 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 COORDINATE SYSTEM.

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.
  • line segment — 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).
  • point set — 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.

🛠️ PROCEDURES 🛠️

The package defines the following public procedures:

::math::geometry::+ point1 point2

Compute the sum of the two vectors given as points and return it. The result is a vector as well. vector math? slay.

::math::geometry::- point1 point2

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

::math::geometry::p x y

Construct a point from its coordinates and return it as the result of the command.

::math::geometry::distance point1 point2

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::length point

Compute the length of the vector and return it as the result of the command.

::math::geometry::s* factor point

Scale the vector by the factor and return it as the result of the command. This is a vector as well.

::math::geometry::direction angle

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::h length

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

::math::geometry::v length

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

::math::geometry::between point1 point2 s

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::octant point

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::rect nw se

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

::math::geometry::nwse rect

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::angle line

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

  • list line — Coordinates of the line

::math::geometry::angleBetween vector1 vector2

Calculate the angle between two vectors (in degrees)

  • list vector1 — First vector
  • list vector2 — Second vector

::math::geometry::inproduct vector1 vector2

Calculate the inner product of two vectors

  • list vector1 — First vector
  • list vector2 — Second vector

::math::geometry::areaParallellogram vector1 vector2

Calculate the area of the parallellogram with the two vectors as its sides

  • list vector1 — First vector
  • list vector2 — Second vector

::math::geometry::calculateDistanceToLine P line

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::calculateDistanceToLineSegment P linesegment

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::calculateDistanceToPolyline P polyline

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::calculateDistanceToPolygon P polygon

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::findClosestPointOnLine P line — okay so picture this: you've got a point, you've got a whole entire infinite line, and you want the exact spot on that line that's closest to your point. Boom. This hands it to you. 💅
    • 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::findClosestPointOnLineSegment P linesegment — same vibe as above but the line got feelings and also boundaries now, because it's a segment, not an infinite line. Returns the point on the segment closest to your 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::findClosestPointOnPolyline P polyline — the glow-up version: now it's a whole polyline, all those little connected segments, and you still just want the closest point on the whole thing. She'll find it. 🌸
    • list P — List of two numbers, the coordinates of the point
    • list polyline — List of numbers, the vertices of the polyline
  • ::math::geometry::lengthOfPolyline polyline — measures how long the polyline is, like if you walked along every single segment. Important: she is not regarded as a polygon here, so don't come at her with polygon expectations. It's a polyline, periodt.
    • list polyline — List of numbers, the vertices of the polyline
  • ::math::geometry::movePointInDirection P direction dist — take a point, pick a direction, pick a distance, and she moves. Returns the new coordinates. Two dimensions only, bestie, we stay flat here. 🦋
    • 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::lineSegmentsIntersect linesegment1 linesegment2 — do these two segments cross, or do they just fully coincide? Returns 1 if yes, 0 if no. Two dimensions only. And heads up: if an endpoint of one segment sits on the other segment (or is very close to it), that totally counts as intersecting. 👀
    • list linesegment1 — First line segment
    • list linesegment2 — Second line segment
  • ::math::geometry::findLineSegmentIntersection linesegment1 linesegment2 — the point where two segments actually meet. Returns the coordinates… or the keyword "coincident" if they lie on top of each other, or "none" if they share zero points. Two dimensions only. 💫
    • list linesegment1 — First line segment
    • list linesegment2 — Second line segment
  • ::math::geometry::findLineIntersection line1 line2 — now with infinite lines, no endpoints, no limits, main character energy. Returns the coordinates of the intersection, or the keyword "coincident" if the lines coincide, or "none" if they have no points in common. Two dimensions only, obviously.
    • list line1 — First line
    • list line2 — Second line
Want the actual math tea? The References section has the details on the algorithm and the math behind it. Go look. 🍓
  • ::math::geometry::polylinesIntersect polyline1 polyline2 — yes or no, do these two polylines intersect? Two dimensions only.
    • list polyline1 — First polyline
    • list polyline2 — Second polyline
  • ::math::geometry::polylinesBoundingIntersect polyline1 polyline2 granularity — this one's the speedrun version: it checks whether two polylines intersect, but it trades away some correctness down to whatever granularity you give it. Use it when you want faster but weaker intersection checking. 🏃‍♀️

How it works: each polyline gets split into a bunch of smaller polylines, each made of granularity points. If the bounding boxes of any pair of those smaller lines intersect, the 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::intervalsOverlap y1 y2 y3 y4 strict — do these two intervals overlap? That's it, that's the whole thing. 💜
    • 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::rectanglesOverlap P1 P2 Q1 Q2 strict — do these two rectangles overlap? Inquiring minds want to know. ✨
    • 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::bbox polyline — gives you the bounding box of a polyline, returned as a list of four coordinates: the upper-left corner and the lower-right corner of the box. 📦
    • list polyline — The polyline to be examined
  • ::math::geometry::overlapBBox polyline1 polyline2 ?strict? — do the bounding boxes of these two polylines overlap or not? That's the whole question, bestie.

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)
Not me noticing the second argument is labelled polyline1 up there 🙈 that's literally what the page says, so I'm keeping it exactly as-is. No cap.
  • ::math::geometry::pointInsideBBox bbox point — is this point inside the bounding box, or sitting right on it, or neither? Let's find out.

Arguments:

  • list bbox — The bounding box given as a list of x/y coordinates
  • list point — The point to be checked
  • ::math::geometry::cathetusPoint pa pb cathetusLength ?location? — okay geometry girlies, gather round: this returns 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 from point B, if the location is given as "b") to that third point is the cathetus length. And heads up: if the cathetus' length is lower than the length of the hypothenusa, you get back an empty list. That's the rule. 😭

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::parallel line offset ?orient? — hands you a line parallel to the one you gave it, sitting at a distance of 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::unitVector line — returns a unit vector from the given line or direction. And plot twist: 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::pointInsidePolygon P polyline — is this point completely inside a polygon? If the point touches the polygon, then the point is not completely inside the polygon. Boundaries are not it. Nope.
    • list P — Coordinates of the point
    • list polyline — The polyline to be examined
  • ::math::geometry::pointInsidePolygonAlt P polyline — same deal, is the point completely inside the polygon, and again, if the point touches the polygon it is not completely inside. But here's the ✨ twist ✨: this alternative procedure uses the so-called winding number to figure it out, and it handles self-intersecting polygons in a "natural" way. Fancy.
    • list P — Coordinates of the point
    • list polyline — The polyline to be examined
  • ::math::geometry::rectangleInsidePolygon P1 P2 polyline — is this rectangle completely inside a polygon? And if the polygon touches the rectangle, then the rectangle is not complete inside the polygon. Same energy as the point version.
    • list P1 — Upper-left corner of the rectangle
    • list P2 — Lower-right corner of the rectangle
    • list polygon — The polygon in question
  • ::math::geometry::areaPolygon polygon — calculates the area of a polygon. That's the whole gig. 🌈
    • list polygon — The polygon in question
  • ::math::geometry::translate vector polyline — slides your whole polyline over by a given vector. 💫
    • list vector — Translation vector
    • list polyline — The polyline to be translated
  • ::math::geometry::rotate angle polyline — spins the polyline by a given angle (degrees) around the origin. Yes, the origin specifically.
    • list angle — Angle over which to rotate the polyline (degrees)
    • list polyline — The polyline to be rotated
  • ::math::geometry::rotateAbout p angle polyline — same rotation situation but now you get to pick the point p she spins around, and you get the new polyline back. Iconic, honestly.

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::reflect angle polyline — mirrors your polyline in a line that passes 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::degToRad angle — converts degrees to radians. Little guy. Does exactly one job. We love her. 🎀
    • list angle — Angle in degrees
  • ::math::geometry::radToDeg angle — and this one converts radians to degrees. The other direction. Besties. 💖
    • list angle — Angle in radians
  • ::math::geometry::circle centre radius — a lil convenience procedure that makes a circle from a point and a radius, so you don't have to assemble it yourself. 🍓
    • list centre — Coordinates of the circle centre
    • list radius — Radius of the circle
  • ::math::geometry::circleTwoPoints point1 point2 — another convenience one: makes a circle from two points on its circumference. The centre is the point between the two given points, and the radius is half the distance between them. Math? Slayed. ⭐
    • list point1 — (first point on the circumference)
    • list point2 — (second point on the circumference)

…and finishing off that argument list from the procedure above, bestie 💖

  • list point1 — First point
  • list point2 — Second point

::math::geometry::pointInsideCircle point circle

Is this point in the circle or not? 🎯 That's the entire assignment. You get 1 if the point is inside the circle or sitting right on the circumference, and 0 if it's out there living its own life. 💅

  • list point — Point to be checked
  • list circle — Circle that may or may not contain the point

::math::geometry::lineIntersectsCircle line circle

Does this line meet the circle? 1 if it intersects it or even just grazes it, 0 if it's a total no 💀.

  • list line — Line to be checked
  • list circle — Circle that may or may not be intersected

::math::geometry::lineSegmentIntersectsCircle segment circle

Same energy as the one above, but for a line segment — so it's finite, it has endpoints, it's a main character with boundaries ✨. 1 = intersects or touches it, 0 = does not.

  • list segment — Line segment to be checked
  • list circle — Circle that may or may not be intersected

::math::geometry::intersectionLineWithCircle line circle

Where exactly does the line cross the circle? 👀 You can get zero, one or two points back. (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.) So yeah, the math is doing a tiny little "are we touching or not" vibe check with a fuzz factor. 🦋

  • list line — Line to be checked
  • list circle — Circle that may or may not be intersected

::math::geometry::intersectionCircleWithCircle circle1 circle2

Two circles, where do they kiss? 💞 Again you can get 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::tangentLinesToCircle point circle

Tangent lines from a point to a circle — like, how many lines can you draw from that point that just barely graze the circle? 🌸 You can get zero, one or two lines. (If the point is on the circumference 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::intersectionPolylines polyline1 polyline2 ?mode? ?granularity?

Returns the first point — or all the 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 ⚡ (speedrun strats, iykyk).

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::intersectionPolylineCircle polyline circle ?mode? ?granularity?

Same situation, but it's a polyline vs a circle now 🌀 — returns the first point or all the points where the polyline intersects the circle. Big polyline? Granularity is right there for a faster, approximate answer.

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::polylineCutOrigin polyline1 polyline2 ?granularity?

Scissors out ✂️ the part of the first polyline that runs from the origin up to the first intersection with the second one. And yes — big polyline means granularity is your girl for a faster approximate answer.

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::polylineCutEnd polyline1 polyline2 ?granularity?

The other blade of the scissors ✂️✨ — returns the part of the first polyline going from the last intersection point with the second one all the way to the end. Granularity does its usual speed-up thing when the polyline is huge.

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::splitPolyline polyline numberVertex

Chops the polyline into a whole 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::enrichPolyline polyline accuracy

Takes every segment of a polyline, splits it into a bunch of smaller segments, and returns the glow-up 💅✨

Arguments:

  • list polyline — The polyline to be refined
  • int accuracy — The number of subsegments to be created

::math::geometry::cleanupPolyline polyline

Removes duplicate neighbouring vertices and returns the result 🧼 — decluttering, but make it geometry.

Arguments:

  • list polyline — The polyline to be cleaned up

🧭 COORDINATE SYSTEM 🧭

The coordinate system this package lives in is the ordinary cartesian one, bestie: positive x-axis points right, positive y-axis points up. 📐 Angles and directions are measured from the positive x-axis and go in a counter-clockwise direction, so an angle of 90 degrees means the direction of the positive y-axis. Simple, iconic, no notes.

Heads up though 🙈 — the Tk canvas coordinates are not this. There the origin sits in the upper left corner of the window. And up to and including version 1.3, the direction and octant procedures of this package used this convention inconsistently. So if you're on old code, be careful. 💀

📚 REFERENCES 📚

  1. Polygon Intersection [http:/wiki.tcl.tk/12070]
  2. http://en.wikipedia.org/wiki/Line-line_intersection
  3. http://local.wasp.uwa.edu.au/~pbourke/geometry/lineline2d/

🐛 BUGS, IDEAS, FEEDBACK 🐛

This document, and the package it describes, will undoubtedly contain bugs and other problems — it's giving "we're all human" 💀. Please report such in the category math :: geometry of the Tcllib Trackers [http://core.tcl.tk/tcllib/reportlist]. And please also report any ideas for enhancements you may have for either the package and/or the documentation. We want them fr fr 🫶

When proposing code changes, please provide unified diffs, 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. 🎀

🔑 KEYWORDS 🔑

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

🏷️ CATEGORY 🏷️

Mathematics

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

And that's the whole page, babe — geometry, fully understood, no cap. This one ships as part of tcllib, version 1.4.2, and the page you just read is math::geometry(3tcl). Go draw something beautiful with it 💖✨📐🦋

📦 where this page comes from