1math::geometry(n) Tcl Math Library math::geometry(n)
2______________________________________________________________________________
6
8 math::geometry - Geometrical computations
9
11 package require Tcl ?8.5?
12 package require math::geometry ?1.4.1?
14 ::math::geometry::+ point1 point2
16 ::math::geometry::- point1 point2
18 ::math::geometry::p x y
20 ::math::geometry::distance point1 point2
22 ::math::geometry::length point
24 ::math::geometry::s* factor point
26 ::math::geometry::direction angle
28 ::math::geometry::h length
30 ::math::geometry::v length
32 ::math::geometry::between point1 point2 s
34 ::math::geometry::octant point
36 ::math::geometry::rect nw se
38 ::math::geometry::nwse rect
40 ::math::geometry::angle line
42 ::math::geometry::angleBetween vector1 vector2
44 ::math::geometry::inproduct vector1 vector2
46 ::math::geometry::areaParallellogram vector1 vector2
48 ::math::geometry::calculateDistanceToLine P line
50 ::math::geometry::calculateDistanceToLineSegment P linesegment
52 ::math::geometry::calculateDistanceToPolyline P polyline
54 ::math::geometry::calculateDistanceToPolygon P polygon
56 ::math::geometry::findClosestPointOnLine P line
58 ::math::geometry::findClosestPointOnLineSegment P linesegment
60 ::math::geometry::findClosestPointOnPolyline P polyline
62 ::math::geometry::lengthOfPolyline polyline
64 ::math::geometry::movePointInDirection P direction dist
66 ::math::geometry::lineSegmentsIntersect linesegment1 linesegment2
68 ::math::geometry::findLineSegmentIntersection linesegment1 linesegment2
70 ::math::geometry::findLineIntersection line1 line2
72 ::math::geometry::polylinesIntersect polyline1 polyline2
74 ::math::geometry::polylinesBoundingIntersect polyline1 polyline2 granu‐
76 larity
77 ::math::geometry::intervalsOverlap y1 y2 y3 y4 strict
79 ::math::geometry::rectanglesOverlap P1 P2 Q1 Q2 strict
81 ::math::geometry::bbox polyline
83 ::math::geometry::overlapBBox polyline1 polyline2 ?strict?
85 ::math::geometry::pointInsideBBox bbox point
87 ::math::geometry::cathetusPoint pa pb cathetusLength ?location?
89 ::math::geometry::parallel line offset ?orient?
91 ::math::geometry::unitVector line
93 ::math::geometry::pointInsidePolygon P polyline
95 ::math::geometry::pointInsidePolygonAlt P polyline
97 ::math::geometry::rectangleInsidePolygon P1 P2 polyline
99 ::math::geometry::areaPolygon polygon
101 ::math::geometry::translate vector polyline
103 ::math::geometry::rotate angle polyline
105 ::math::geometry::rotateAbout p angle polyline
107 ::math::geometry::reflect angle polyline
109 ::math::geometry::degToRad angle
111 ::math::geometry::radToDeg angle
113 ::math::geometry::circle centre radius
115 ::math::geometry::circleTwoPoints point1 point2
117 ::math::geometry::pointInsideCircle point circle
119 ::math::geometry::lineIntersectsCircle line circle
121 ::math::geometry::lineSegmentIntersectsCircle segment circle
123 ::math::geometry::intersectionLineWithCircle line circle
125 ::math::geometry::intersectionCircleWithCircle circle1 circle2
127 ::math::geometry::tangentLinesToCircle point circle
129 ::math::geometry::intersectionPolylines polyline1 polyline2 ?mode?
131 ?granularity?
132 ::math::geometry::intersectionPolylineCircle polyline circle ?mode?
134 ?granularity?
135 ::math::geometry::polylineCutOrigin polyline1 polyline2 ?granularity?
137 ::math::geometry::polylineCutEnd polyline1 polyline2 ?granularity?
139 ::math::geometry::splitPolyline polyline numberVertex
141 ::math::geometry::enrichPolyline polyline accuracy
143 ::math::geometry::cleanupPolyline polyline
145______________________________________________________________________________
147
149 The math::geometry package is a collection of functions for computa‐
150 tions and manipulations on two-dimensional geometrical objects, such as
151 points, lines and polygons.
152 The geometrical objects are implemented as plain lists of coordinates.
154 For instance a line is defined by a list of four numbers, the x- and y-
155 coordinate of a first point and the x- and y-coordinates of a second
156 point on the line.
157 Note: In version 1.4.0 an inconsistency was repaired - see
159 https://core.tcl-lang.org/tcllib/tktview?name=fb4812f82b. More in CO‐
160 ORDINATE SYSTEM
161 The various types of object are recognised by the number of coordinate
163 pairs and the context in which they are used: a list of four elements
164 can be regarded as an infinite line, a finite line segment but also as
165 a polyline of one segment and a point set of two points.
166 Currently the following types of objects are distinguished:
168 • point - a list of two coordinates representing the x- and y-co‐
170 ordinates respectively.
171 • line - a list of four coordinates, interpreted as the x- and y-
173 coordinates of two distinct points on the line.
174 • line segment - a list of four coordinates, interpreted as the x-
176 and y-coordinates of the first and the last points on the line
177 segment.
178 • polyline - a list of an even number of coordinates, interpreted
180 as the x- and y-coordinates of an ordered set of points.
181 • polygon - like a polyline, but the implicit assumption is that
183 the polyline is closed (if the first and last points do not co‐
184 incide, the missing segment is automatically added).
185 • point set - again a list of an even number of coordinates, but
187 the points are regarded without any ordering.
188 • circle - a list of three numbers, the first two are the coordi‐
190 nates of the centre and the third is the radius.
191
193 The package defines the following public procedures:
194 ::math::geometry::+ point1 point2
196 Compute the sum of the two vectors given as points and return
197 it. The result is a vector as well.
198 ::math::geometry::- point1 point2
200 Compute the difference (point1 - point2) of the two vectors
201 given as points and return it. The result is a vector as well.
202 ::math::geometry::p x y
204 Construct a point from its coordinates and return it as the re‐
205 sult of the command.
206 ::math::geometry::distance point1 point2
208 Compute the distance between the two points and return it as the
209 result of the command. This is in essence the same as
210 math::geometry::length [math::geomtry::- point1 point2]
213 ::math::geometry::length point
216 Compute the length of the vector and return it as the result of
217 the command.
218 ::math::geometry::s* factor point
220 Scale the vector by the factor and return it as the result of
221 the command. This is a vector as well.
222 ::math::geometry::direction angle
224 Given the angle in degrees this command computes and returns the
225 unit vector pointing into this direction. The vector for angle
226 == 0 points to the right (east), and for angle == 90 up (north).
227 ::math::geometry::h length
229 Returns a horizontal vector on the X-axis of the specified
230 length. Positive lengths point to the right (east).
231 ::math::geometry::v length
233 Returns a vertical vector on the Y-axis of the specified length.
234 Positive lengths point down (south).
235 ::math::geometry::between point1 point2 s
237 Compute the point which is at relative distance s between the
238 two points and return it as the result of the command. A rela‐
239 tive distance of 0 returns point1, the distance 1 returns
240 point2. Distances < 0 or > 1 extrapolate along the line between
241 the two point.
242 ::math::geometry::octant point
244 Compute the octant of the circle the point is in and return it
245 as the result of the command. The possible results are
246 [1] east
248 [2] northeast
250 [3] north
252 [4] northwest
254 [5] west
256 [6] southwest
258 [7] south
260 [8] southeast
262 Each octant is the arc of the circle +/- 22.5 degrees from the
264 cardinal direction the octant is named for.
265 ::math::geometry::rect nw se
267 Construct a rectangle from its northwest and southeast corners
268 and return it as the result of the command.
269 ::math::geometry::nwse rect
271 Extract the northwest and southeast corners of the rectangle and
272 return them as the result of the command (a 2-element list con‐
273 taining the points, in the named order).
274 ::math::geometry::angle line
276 Calculate the angle from the positive x-axis to a given line (in
277 two dimensions only).
278 list line
280 Coordinates of the line
281 ::math::geometry::angleBetween vector1 vector2
283 Calculate the angle between two vectors (in degrees)
284 list vector1
286 First vector
287 list vector2
289 Second vector
290 ::math::geometry::inproduct vector1 vector2
292 Calculate the inner product of two vectors
293 list vector1
295 First vector
296 list vector2
298 Second vector
299 ::math::geometry::areaParallellogram vector1 vector2
301 Calculate the area of the parallellogram with the two vectors as
302 its sides
303 list vector1
305 First vector
306 list vector2
308 Second vector
309 ::math::geometry::calculateDistanceToLine P line
311 Calculate the distance of point P to the (infinite) line and re‐
312 turn the result
313 list P List of two numbers, the coordinates of the point
315 list line
317 List of four numbers, the coordinates of two points on
318 the line
319 ::math::geometry::calculateDistanceToLineSegment P linesegment
321 Calculate the distance of point P to the (finite) line segment
322 and return the result.
323 list P List of two numbers, the coordinates of the point
325 list linesegment
327 List of four numbers, the coordinates of the first and
328 last points of the line segment
329 ::math::geometry::calculateDistanceToPolyline P polyline
331 Calculate the distance of point P to the polyline and return the
332 result. Note that a polyline needs not to be closed.
333 list P List of two numbers, the coordinates of the point
335 list polyline
337 List of numbers, the coordinates of the vertices of the
338 polyline
339 ::math::geometry::calculateDistanceToPolygon P polygon
341 Calculate the distance of point P to the polygon and return the
342 result. If the list of coordinates is not closed (first and last
343 points differ), it is automatically closed.
344 list P List of two numbers, the coordinates of the point
346 list polygon
348 List of numbers, the coordinates of the vertices of the
349 polygon
350 ::math::geometry::findClosestPointOnLine P line
352 Return the point on a line which is closest to a given point.
353 list P List of two numbers, the coordinates of the point
355 list line
357 List of four numbers, the coordinates of two points on
358 the line
359 ::math::geometry::findClosestPointOnLineSegment P linesegment
361 Return the point on a line segment which is closest to a given
362 point.
363 list P List of two numbers, the coordinates of the point
365 list linesegment
367 List of four numbers, the first and last points on the
368 line segment
369 ::math::geometry::findClosestPointOnPolyline P polyline
371 Return the point on a polyline which is closest to a given
372 point.
373 list P List of two numbers, the coordinates of the point
375 list polyline
377 List of numbers, the vertices of the polyline
378 ::math::geometry::lengthOfPolyline polyline
380 Return the length of the polyline (note: it not regarded as a
381 polygon)
382 list polyline
384 List of numbers, the vertices of the polyline
385 ::math::geometry::movePointInDirection P direction dist
387 Move a point over a given distance in a given direction and re‐
388 turn the new coordinates (in two dimensions only).
389 list P Coordinates of the point to be moved
391 double direction
393 Direction (in degrees; 0 is to the right, 90 upwards)
394 list dist
396 Distance over which to move the point
397 ::math::geometry::lineSegmentsIntersect linesegment1 linesegment2
399 Check if two line segments intersect or coincide. Returns 1 if
400 that is the case, 0 otherwise (in two dimensions only). If an
401 endpoint of one segment lies on the other segment (or is very
402 close to the segment), they are considered to intersect
403 list linesegment1
405 First line segment
406 list linesegment2
408 Second line segment
409 ::math::geometry::findLineSegmentIntersection linesegment1 linesegment2
411 Find the intersection point of two line segments. Return the co‐
412 ordinates or the keywords "coincident" or "none" if the line
413 segments coincide or have no points in common (in two dimensions
414 only).
415 list linesegment1
417 First line segment
418 list linesegment2
420 Second line segment
421 ::math::geometry::findLineIntersection line1 line2
423 Find the intersection point of two (infinite) lines. Return the
424 coordinates or the keywords "coincident" or "none" if the lines
425 coincide or have no points in common (in two dimensions only).
426 list line1
428 First line
429 list line2
431 Second line
432 See section References for details on the algorithm and math be‐
434 hind it.
435 ::math::geometry::polylinesIntersect polyline1 polyline2
437 Check if two polylines intersect or not (in two dimensions
438 only).
439 list polyline1
441 First polyline
442 list polyline2
444 Second polyline
445 ::math::geometry::polylinesBoundingIntersect polyline1 polyline2 granu‐
447 larity
448 Check whether two polylines intersect, but reduce the correct‐
449 ness of the result to the given granularity. Use this for
450 faster, but weaker, intersection checking.
451 How it works:
453 Each polyline is split into a number of smaller polylines, con‐
455 sisting of granularity points each. If a pair of those smaller
456 lines' bounding boxes intersect, then this procedure returns 1,
457 otherwise it returns 0.
458 list polyline1
460 First polyline
461 list polyline2
463 Second polyline
464 int granularity
466 Number of points in each part (<=1 means check every
467 edge)
468 ::math::geometry::intervalsOverlap y1 y2 y3 y4 strict
470 Check if two intervals overlap.
471 double y1,y2
473 Begin and end of first interval
474 double y3,y4
476 Begin and end of second interval
477 logical strict
479 Check for strict or non-strict overlap
480 ::math::geometry::rectanglesOverlap P1 P2 Q1 Q2 strict
482 Check if two rectangles overlap.
483 list P1
485 upper-left corner of the first rectangle
486 list P2
488 lower-right corner of the first rectangle
489 list Q1
491 upper-left corner of the second rectangle
492 list Q2
494 lower-right corner of the second rectangle
495 list strict
497 choosing strict or non-strict interpretation
498 ::math::geometry::bbox polyline
500 Calculate the bounding box of a polyline. Returns a list of four
501 coordinates: the upper-left and the lower-right corner of the
502 box.
503 list polyline
505 The polyline to be examined
506 ::math::geometry::overlapBBox polyline1 polyline2 ?strict?
508 Check if the bounding boxes of two polylines overlap or not.
509 Arguments:
511 list polyline1
513 The first polyline
514 list polyline1
516 The second polyline
517 int strict
519 Whether strict overlap is to checked (1) or if the bound‐
520 ing boxes may touch (0, default)
521 ::math::geometry::pointInsideBBox bbox point
523 Check if the point is inside or on the bounding box or not. Ar‐
525 guments:
526 list bbox
528 The bounding box given as a list of x/y coordinates
529 list point
531 The point to be checked
532 ::math::geometry::cathetusPoint pa pb cathetusLength ?location?
534 Return the third point of the rectangular triangle defined by
535 the two given end points of the hypothenusa. The triangle's
536 side from point A (or B, if the location is given as "b") to the
537 third point is the cathetus length. If the cathetus' length is
538 lower than the length of the hypothenusa, an empty list is re‐
539 turned.
540 Arguments:
542 list pa
544 The starting point on hypotenuse
545 list pb
547 The ending point on hypotenuse
548 float cathetusLength
550 The length of the cathetus of the triangle
551 string location
553 The location of the given cathetus, "a" means given
554 cathetus shares point pa (default) "b" means given
555 cathetus shares point pb
556 ::math::geometry::parallel line offset ?orient?
558 Return a line parallel to the given line, with a distance "off‐
559 set". The orientation is determined by the two points defining
560 the line.
561 Arguments:
563 list line
565 The given line
566 float offset
568 The distance to the given line
569 string orient
571 Orientation of the new line with respect to the given
572 line (defaults to "right")
573 ::math::geometry::unitVector line
576 Return a unit vector from the given line or direction, if the
577 line argument is a single point (then a line through the origin
578 is assumed) Arguments:
579 list line
581 The line in question (or a single point, implying a line
582 through the origin)
583 ::math::geometry::pointInsidePolygon P polyline
585 Determine if a point is completely inside a polygon. If the
586 point touches the polygon, then the point is not completely in‐
587 side the polygon.
588 list P Coordinates of the point
590 list polyline
592 The polyline to be examined
593 ::math::geometry::pointInsidePolygonAlt P polyline
595 Determine if a point is completely inside a polygon. If the
596 point touches the polygon, then the point is not completely in‐
597 side the polygon. Note: this alternative procedure uses the so-
598 called winding number to determine this. It handles self-inter‐
599 secting polygons in a "natural" way.
600 list P Coordinates of the point
602 list polyline
604 The polyline to be examined
605 ::math::geometry::rectangleInsidePolygon P1 P2 polyline
607 Determine if a rectangle is completely inside a polygon. If
608 polygon touches the rectangle, then the rectangle is not com‐
609 plete inside the polygon.
610 list P1
612 Upper-left corner of the rectangle
613 list P2
615 Lower-right corner of the rectangle
616 list polygon
619 The polygon in question
620 ::math::geometry::areaPolygon polygon
622 Calculate the area of a polygon.
623 list polygon
625 The polygon in question
626 ::math::geometry::translate vector polyline
628 Translate a polyline over a given vector
629 list vector
631 Translation vector
632 list polyline
634 The polyline to be translated
635 ::math::geometry::rotate angle polyline
637 Rotate a polyline over a given angle (degrees) around the origin
638 list angle
640 Angle over which to rotate the polyline (degrees)
641 list polyline
643 The polyline to be rotated
644 ::math::geometry::rotateAbout p angle polyline
646 Rotate a polyline around a given point p and return the new
647 polyline.
648 Arguments:
650 list p The point of rotation
652 float angle
654 The angle over which to rotate the polyline (degrees)
655 list polyline
657 The polyline to be rotated
658 ::math::geometry::reflect angle polyline
660 Reflect a polyline in a line through the origin at a given angle
661 (degrees) to the x-axis
662 list angle
664 Angle of the line of reflection (degrees)
665 list polyline
667 The polyline to be reflected
668 ::math::geometry::degToRad angle
670 Convert from degrees to radians
671 list angle
673 Angle in degrees
674 ::math::geometry::radToDeg angle
676 Convert from radians to degrees
677 list angle
679 Angle in radians
680 ::math::geometry::circle centre radius
682 Convenience procedure to create a circle from a point and a ra‐
683 dius.
684 list centre
686 Coordinates of the circle centre
687 list radius
689 Radius of the circle
690 ::math::geometry::circleTwoPoints point1 point2
692 Convenience procedure to create a circle from two points on its
693 circumference The centre is the point between the two given
694 points, the radius is half the distance between them.
695 list point1
697 First point
698 list point2
700 Second point
701 ::math::geometry::pointInsideCircle point circle
703 Determine if the given point is inside the circle or on the cir‐
704 cumference (1) or outside (0).
705 list point
707 Point to be checked
708 list circle
710 Circle that may or may not contain the point
711 ::math::geometry::lineIntersectsCircle line circle
713 Determine if the given line intersects the circle or touches it
714 (1) or does not (0).
715 list line
717 Line to be checked
718 list circle
720 Circle that may or may not be intersected
721 ::math::geometry::lineSegmentIntersectsCircle segment circle
723 Determine if the given line segment intersects the circle or
724 touches it (1) or does not (0).
725 list segment
727 Line segment to be checked
728 list circle
730 Circle that may or may not be intersected
731 ::math::geometry::intersectionLineWithCircle line circle
733 Determine the points at which the given line intersects the cir‐
734 cle. There can be zero, one or two points. (If the line touches
735 the circle or is close to it, then one point is returned. An ar‐
736 bitrary margin of 1.0e-10 times the radius is used to determine
737 this situation.)
738 list line
740 Line to be checked
741 list circle
743 Circle that may or may not be intersected
744 ::math::geometry::intersectionCircleWithCircle circle1 circle2
746 Determine the points at which the given two circles intersect.
747 There can be zero, one or two points. (If the two circles touch
748 the circle or are very close, then one point is returned. An ar‐
749 bitrary margin of 1.0e-10 times the mean of the radii of the two
750 circles is used to determine this situation.)
751 list circle1
753 First circle
754 list circle2
756 Second circle
757 ::math::geometry::tangentLinesToCircle point circle
759 Determine the tangent lines from the given point to the circle.
760 There can be zero, one or two lines. (If the point is on the
761 cirucmference or very close to the circle, then one line is re‐
762 turned. An arbitrary margin of 1.0e-10 times the radius of the
763 circle is used to determine this situation.)
764 list point
766 Point in question
767 list circle
769 Circle to which the tangent lines are to be determined
770 ::math::geometry::intersectionPolylines polyline1 polyline2 ?mode?
772 ?granularity?
773 Return the first point or all points where the two polylines in‐
774 tersect. If the number of points in the polylines is large, you
775 can use the granularity to get an approximate answer faster.
776 Arguments:
778 list polyline1
780 The first polyline
781 list polyline2
783 The second polyline
784 string mode
786 Whether to return only the first (default) or to return
787 all intersection points ("all")
788 int granularity
790 The number of points that will be skipped plus 1 in the
791 search for intersection points (1 or smaller means an ex‐
792 act answer is returned)
793 ::math::geometry::intersectionPolylineCircle polyline circle ?mode?
795 ?granularity?
796 Return the first point or all points where the polyline inter‐
797 sects the circle. If the number of points in the polyline is
798 large, you can use the granularity to get an approximate answer
799 faster.
800 Arguments:
802 list polyline
804 The polyline that may intersect the circle
805 list circle
807 The circle in question
808 string mode
810 Whether to return only the first (default) or to return
811 all intersection points ("all")
812 int granularity
814 The number of points that will be skipped plus 1 in the
815 search for intersection points (1 or smaller means an ex‐
816 act answer is returned)
817 ::math::geometry::polylineCutOrigin polyline1 polyline2 ?granularity?
819 Return the part of the first polyline from the origin up to the
820 first intersection with the second. If the number of points in
821 the polyline is large, you can use the granularity to get an ap‐
822 proximate answer faster.
823 Arguments:
825 list polyline1
827 The first polyline (from which a part is to be returned)
828 list polyline2
830 The second polyline
831 int granularity
833 The number of points that will be skipped plus 1 in the
834 search for intersection points (1 or smaller means an ex‐
835 act answer is returned)
836 ::math::geometry::polylineCutEnd polyline1 polyline2 ?granularity?
838 Return the part of the first polyline from the last intersection
839 point with the second to the end. If the number of points in the
840 polyline is large, you can use the granularity to get an approx‐
841 imate answer faster.
842 Arguments:
844 list polyline1
846 The first polyline (from which a part is to be returned)
847 list polyline2
849 The second polyline
850 int granularity
852 The number of points that will be skipped plus 1 in the
853 search for intersection points (1 or smaller means an ex‐
854 act answer is returned)
855 ::math::geometry::splitPolyline polyline numberVertex
857 Split the poyline into a set of polylines where each separate
858 polyline holds "numberVertex" vertices between the two end
859 points.
860 Arguments:
862 list polyline
864 The polyline to be split up
865 int numberVertex
867 The number of "internal" vertices
868 ::math::geometry::enrichPolyline polyline accuracy
870 Split up each segment of a polyline into a number of smaller
871 segments and return the result.
872 Arguments:
874 list polyline
876 The polyline to be refined
877 int accuracy
879 The number of subsegments to be created
880 ::math::geometry::cleanupPolyline polyline
882 Remove duplicate neighbouring vertices and return the result.
883 Arguments:
885 list polyline
887 The polyline to be cleaned up
888
890 The coordinate system used by the package is the ordinary cartesian
891 system, where the positive x-axis is directed to the right and the pos‐
892 itive y-axis is directed upwards. Angles and directions are defined
893 with respect to the positive x-axis in a counter-clockwise direction,
894 so that an angle of 90 degrees is the direction of the positive y-axis.
895 Note that the Tk canvas coordinates differ from this, as there the ori‐
896 gin is located in the upper left corner of the window. Up to and in‐
897 cluding version 1.3, the direction and octant procedures of this pack‐
898 age used this convention inconsistently.
899
901 [1] Polygon Intersection [http:/wiki.tcl.tk/12070]
902 [2] http://en.wikipedia.org/wiki/Line-line_intersection
904 [3] http://local.wasp.uwa.edu.au/~pbourke/geometry/lineline2d/
906
908 This document, and the package it describes, will undoubtedly contain
909 bugs and other problems. Please report such in the category math ::
910 geometry of the Tcllib Trackers [http://core.tcl.tk/tcllib/reportlist].
911 Please also report any ideas for enhancements you may have for either
912 package and/or documentation.
913 When proposing code changes, please provide unified diffs, i.e the out‐
915 put of diff -u.
916 Note further that attachments are strongly preferred over inlined
918 patches. Attachments can be made by going to the Edit form of the
919 ticket immediately after its creation, and then using the left-most
920 button in the secondary navigation bar.
921
923 angle, distance, line, math, plane geometry, point
924
926 Mathematics
927
929 Copyright (c) 2001 by Ideogramic ApS and other parties
930 Copyright (c) 2010 by Andreas Kupries
931 Copyright (c) 2010 by Kevin Kenny
932 Copyright (c) 2018 by Arjen Markus
933 Copyright (c) 2020 by Manfred Rosenberger
934tcllib 1.4.1 math::geometry(n)