1math::geometry(n)              Tcl Math Library              math::geometry(n)
2
3
4
5______________________________________________________________________________
6

NAME

8       math::geometry - Geometrical computations
9

SYNOPSIS

11       package require Tcl  ?8.5?
12
13       package require math::geometry  ?1.3.0?
14
15       ::math::geometry::+ point1 point2
16
17       ::math::geometry::- point1 point2
18
19       ::math::geometry::p x y
20
21       ::math::geometry::distance point1 point2
22
23       ::math::geometry::length point
24
25       ::math::geometry::s* factor point
26
27       ::math::geometry::direction angle
28
29       ::math::geometry::h length
30
31       ::math::geometry::v length
32
33       ::math::geometry::between point1 point2 s
34
35       ::math::geometry::octant point
36
37       ::math::geometry::rect nw se
38
39       ::math::geometry::nwse rect
40
41       ::math::geometry::angle line
42
43       ::math::geometry::angleBetween vector1 vector2
44
45       ::math::geometry::inproduct vector1 vector2
46
47       ::math::geometry::areaParallellogram vector1 vector2
48
49       ::math::geometry::calculateDistanceToLine P line
50
51       ::math::geometry::calculateDistanceToLineSegment P linesegment
52
53       ::math::geometry::calculateDistanceToPolyline P polyline
54
55       ::math::geometry::calculateDistanceToPolygon P polygon
56
57       ::math::geometry::findClosestPointOnLine P line
58
59       ::math::geometry::findClosestPointOnLineSegment P linesegment
60
61       ::math::geometry::findClosestPointOnPolyline P polyline
62
63       ::math::geometry::lengthOfPolyline polyline
64
65       ::math::geometry::movePointInDirection P direction dist
66
67       ::math::geometry::lineSegmentsIntersect linesegment1 linesegment2
68
69       ::math::geometry::findLineSegmentIntersection linesegment1 linesegment2
70
71       ::math::geometry::findLineIntersection line1 line2
72
73       ::math::geometry::polylinesIntersect polyline1 polyline2
74
75       ::math::geometry::polylinesBoundingIntersect polyline1 polyline2 granu‐
76       larity
77
78       ::math::geometry::intervalsOverlap y1 y2 y3 y4 strict
79
80       ::math::geometry::rectanglesOverlap P1 P2 Q1 Q2 strict
81
82       ::math::geometry::bbox polyline
83
84       ::math::geometry::pointInsidePolygon P polyline
85
86       ::math::geometry::pointInsidePolygonAlt P polyline
87
88       ::math::geometry::rectangleInsidePolygon P1 P2 polyline
89
90       ::math::geometry::areaPolygon polygon
91
92       ::math::geometry::translate vector polyline
93
94       ::math::geometry::rotate angle polyline
95
96       ::math::geometry::reflect angle polyline
97
98       ::math::geometry::degToRad angle
99
100       ::math::geometry::radToDeg angle
101
102       ::math::geometry::circle centre radius
103
104       ::math::geometry::circleTwoPoints point1 point2
105
106       ::math::geometry::pointInsideCircle point circle
107
108       ::math::geometry::lineIntersectsCircle line circle
109
110       ::math::geometry::lineSegmentIntersectsCircle segment circle
111
112       ::math::geometry::intersectionLineWithCircle line circle
113
114       ::math::geometry::intersectionCircleWithCircle circle1 circle2
115
116       ::math::geometry::tangentLinesToCircle point circle
117
118______________________________________________________________________________
119

DESCRIPTION

121       The math::geometry package is a collection of  functions  for  computa‐
122       tions and manipulations on two-dimensional geometrical objects, such as
123       points, lines and polygons.
124
125       The geometrical objects are implemented as plain lists of  coordinates.
126       For instance a line is defined by a list of four numbers, the x- and y-
127       coordinate of a first point and the x- and y-coordinates  of  a  second
128       point on the line.
129
130       The  various types of object are recognised by the number of coordinate
131       pairs and the context in which they are used: a list of  four  elements
132       can  be regarded as an infinite line, a finite line segment but also as
133       a polyline of one segment and a point set of two points.
134
135       Currently the following types of objects are distinguished:
136
137point - a list of two coordinates representing the x- and  y-co‐
138              ordinates respectively.
139
140line  - a list of four coordinates, interpreted as the x- and y-
141              coordinates of two distinct points on the line.
142
143line segment - a list of four coordinates, interpreted as the x-
144              and  y-coordinates  of the first and the last points on the line
145              segment.
146
147polyline - a list of an even number of coordinates,  interpreted
148              as the x- and y-coordinates of an ordered set of points.
149
150polygon  -  like a polyline, but the implicit assumption is that
151              the polyline is closed (if the first and last points do not  co‐
152              incide, the missing segment is automatically added).
153
154point  set  - again a list of an even number of coordinates, but
155              the points are regarded without any ordering.
156
157circle - a list of three numbers, the first two are the  coordi‐
158              nates of the centre and the third is the radius.
159

PROCEDURES

161       The package defines the following public procedures:
162
163       ::math::geometry::+ point1 point2
164              Compute  the  sum  of the two vectors given as points and return
165              it.  The result is a vector as well.
166
167       ::math::geometry::- point1 point2
168              Compute the difference (point1 -  point2)  of  the  two  vectors
169              given as points and return it. The result is a vector as well.
170
171       ::math::geometry::p x y
172              Construct  a point from its coordinates and return it as the re‐
173              sult of the command.
174
175       ::math::geometry::distance point1 point2
176              Compute the distance between the two points and return it as the
177              result of the command. This is in essence the same as
178
179
180                  math::geometry::length [math::geomtry::- point1 point2]
181
182
183       ::math::geometry::length point
184              Compute  the length of the vector and return it as the result of
185              the command.
186
187       ::math::geometry::s* factor point
188              Scale the vector by the factor and return it as  the  result  of
189              the command. This is a vector as well.
190
191       ::math::geometry::direction angle
192              Given the angle in degrees this command computes and returns the
193              unit vector pointing into this direction. The vector  for  angle
194              == 0 points to the right (up), and for angle == 90 up (north).
195
196       ::math::geometry::h length
197              Returns  a  horizontal  vector  on  the  X-axis of the specified
198              length.  Positive lengths point to the right (east).
199
200       ::math::geometry::v length
201              Returns a vertical vector on the Y-axis of the specified length.
202              Positive lengths point down (south).
203
204       ::math::geometry::between point1 point2 s
205              Compute  the  point  which is at relative distance s between the
206              two points and return it as the result of the command.  A  rela‐
207              tive  distance  of  0  returns  point1,  the  distance 1 returns
208              point2.  Distances < 0 or > 1 extrapolate along the line between
209              the two point.
210
211       ::math::geometry::octant point
212              Compute  the  octant of the circle the point is in and return it
213              as the result of the command. The possible results are
214
215              [1]    east
216
217              [2]    northeast
218
219              [3]    north
220
221              [4]    northwest
222
223              [5]    west
224
225              [6]    southwest
226
227              [7]    south
228
229              [8]    southeast
230
231              Each octant is the arc of the circle +/- 22.5 degrees  from  the
232              cardinal direction the octant is named for.
233
234       ::math::geometry::rect nw se
235              Construct  a  rectangle from its northwest and southeast corners
236              and return it as the result of the command.
237
238       ::math::geometry::nwse rect
239              Extract the northwest and southeast corners of the rectangle and
240              return  them as the result of the command (a 2-element list con‐
241              taining the points, in the named order).
242
243       ::math::geometry::angle line
244              Calculate the angle from the positive x-axis to a given line (in
245              two dimensions only).
246
247              list line
248                     Coordinates of the line
249
250       ::math::geometry::angleBetween vector1 vector2
251              Calculate the angle between two vectors (in degrees)
252
253              list vector1
254                     First vector
255
256              list vector2
257                     Second vector
258
259       ::math::geometry::inproduct vector1 vector2
260              Calculate the inner product of two vectors
261
262              list vector1
263                     First vector
264
265              list vector2
266                     Second vector
267
268       ::math::geometry::areaParallellogram vector1 vector2
269              Calculate the area of the parallellogram with the two vectors as
270              its sides
271
272              list vector1
273                     First vector
274
275              list vector2
276                     Second vector
277
278
279       ::math::geometry::calculateDistanceToLine P line
280              Calculate the distance of point P to the (infinite) line and re‐
281              turn the result
282
283              list P List of two numbers, the coordinates of the point
284
285              list line
286                     List  of  four  numbers, the coordinates of two points on
287                     the line
288
289
290       ::math::geometry::calculateDistanceToLineSegment P linesegment
291              Calculate the distance of point P to the (finite)  line  segment
292              and return the result.
293
294              list P List of two numbers, the coordinates of the point
295
296              list linesegment
297                     List  of  four  numbers, the coordinates of the first and
298                     last points of the line segment
299
300
301
302       ::math::geometry::calculateDistanceToPolyline P polyline
303              Calculate the distance of point P to the polyline and return the
304              result. Note that a polyline needs not to be closed.
305
306              list P List of two numbers, the coordinates of the point
307
308              list polyline
309                     List  of  numbers, the coordinates of the vertices of the
310                     polyline
311
312
313       ::math::geometry::calculateDistanceToPolygon P polygon
314              Calculate the distance of point P to the polygon and return  the
315              result. If the list of coordinates is not closed (first and last
316              points differ), it is automatically closed.
317
318              list P List of two numbers, the coordinates of the point
319
320              list polygon
321                     List of numbers, the coordinates of the vertices  of  the
322                     polygon
323
324
325       ::math::geometry::findClosestPointOnLine P line
326              Return the point on a line which is closest to a given point.
327
328              list P List of two numbers, the coordinates of the point
329
330              list line
331                     List  of  four  numbers, the coordinates of two points on
332                     the line
333
334
335       ::math::geometry::findClosestPointOnLineSegment P linesegment
336              Return the point on a line segment which is closest to  a  given
337              point.
338
339              list P List of two numbers, the coordinates of the point
340
341              list linesegment
342                     List  of  four  numbers, the first and last points on the
343                     line segment
344
345
346       ::math::geometry::findClosestPointOnPolyline P polyline
347              Return the point on a polyline  which  is  closest  to  a  given
348              point.
349
350              list P List of two numbers, the coordinates of the point
351
352              list polyline
353                     List of numbers, the vertices of the polyline
354
355
356       ::math::geometry::lengthOfPolyline polyline
357              Return  the  length  of the polyline (note: it not regarded as a
358              polygon)
359
360              list polyline
361                     List of numbers, the vertices of the polyline
362
363
364       ::math::geometry::movePointInDirection P direction dist
365              Move a point over a given distance in a given direction and  re‐
366              turn the new coordinates (in two dimensions only).
367
368              list P Coordinates of the point to be moved
369
370              double direction
371                     Direction (in degrees; 0 is to the right, 90 upwards)
372
373              list dist
374                     Distance over which to move the point
375
376
377       ::math::geometry::lineSegmentsIntersect linesegment1 linesegment2
378              Check  if  two line segments intersect or coincide. Returns 1 if
379              that is the case, 0 otherwise (in two dimensions  only).  If  an
380              endpoint  of  one  segment lies on the other segment (or is very
381              close to the segment), they are considered to intersect
382
383              list linesegment1
384                     First line segment
385
386              list linesegment2
387                     Second line segment
388
389
390       ::math::geometry::findLineSegmentIntersection linesegment1 linesegment2
391              Find the intersection point of two line segments. Return the co‐
392              ordinates  or  the  keywords  "coincident" or "none" if the line
393              segments coincide or have no points in common (in two dimensions
394              only).
395
396              list linesegment1
397                     First line segment
398
399              list linesegment2
400                     Second line segment
401
402
403       ::math::geometry::findLineIntersection line1 line2
404              Find  the intersection point of two (infinite) lines. Return the
405              coordinates or the keywords "coincident" or "none" if the  lines
406              coincide or have no points in common (in two dimensions only).
407
408              list line1
409                     First line
410
411              list line2
412                     Second line
413
414              See section References for details on the algorithm and math be‐
415              hind it.
416
417
418       ::math::geometry::polylinesIntersect polyline1 polyline2
419              Check if two polylines  intersect  or  not  (in  two  dimensions
420              only).
421
422              list polyline1
423                     First polyline
424
425              list polyline2
426                     Second polyline
427
428
429       ::math::geometry::polylinesBoundingIntersect polyline1 polyline2 granu‐
430       larity
431              Check whether two polylines intersect, but reduce  the  correct‐
432              ness  of  the  result  to  the  given granularity.  Use this for
433              faster, but weaker, intersection checking.
434
435              How it works:
436
437              Each polyline is split into a number of smaller polylines,  con‐
438              sisting  of  granularity points each. If a pair of those smaller
439              lines' bounding boxes intersect, then this procedure returns  1,
440              otherwise it returns 0.
441
442              list polyline1
443                     First polyline
444
445              list polyline2
446                     Second polyline
447
448              int granularity
449                     Number  of  points  in  each  part (<=1 means check every
450                     edge)
451
452
453       ::math::geometry::intervalsOverlap y1 y2 y3 y4 strict
454              Check if two intervals overlap.
455
456              double y1,y2
457                     Begin and end of first interval
458
459              double y3,y4
460                     Begin and end of second interval
461
462              logical strict
463                     Check for strict or non-strict overlap
464
465
466       ::math::geometry::rectanglesOverlap P1 P2 Q1 Q2 strict
467              Check if two rectangles overlap.
468
469              list P1
470                     upper-left corner of the first rectangle
471
472              list P2
473                     lower-right corner of the first rectangle
474
475              list Q1
476                     upper-left corner of the second rectangle
477
478              list Q2
479                     lower-right corner of the second rectangle
480
481              list strict
482                     choosing strict or non-strict interpretation
483
484
485       ::math::geometry::bbox polyline
486              Calculate the bounding box of a polyline. Returns a list of four
487              coordinates:  the  upper-left  and the lower-right corner of the
488              box.
489
490              list polyline
491                     The polyline to be examined
492
493
494       ::math::geometry::pointInsidePolygon P polyline
495              Determine if a point is completely  inside  a  polygon.  If  the
496              point  touches the polygon, then the point is not completely in‐
497              side the polygon.
498
499              list P Coordinates of the point
500
501              list polyline
502                     The polyline to be examined
503
504
505       ::math::geometry::pointInsidePolygonAlt P polyline
506              Determine if a point is completely  inside  a  polygon.  If  the
507              point  touches the polygon, then the point is not completely in‐
508              side the polygon. Note: this alternative procedure uses the  so-
509              called  winding number to determine this. It handles self-inter‐
510              secting polygons in a "natural" way.
511
512              list P Coordinates of the point
513
514              list polyline
515                     The polyline to be examined
516
517
518       ::math::geometry::rectangleInsidePolygon P1 P2 polyline
519              Determine if a rectangle is  completely  inside  a  polygon.  If
520              polygon  touches  the  rectangle, then the rectangle is not com‐
521              plete inside the polygon.
522
523              list P1
524                     Upper-left corner of the rectangle
525
526              list P2
527                     Lower-right corner of the rectangle
528
529
530              list polygon
531                     The polygon in question
532
533
534       ::math::geometry::areaPolygon polygon
535              Calculate the area of a polygon.
536
537              list polygon
538                     The polygon in question
539
540
541       ::math::geometry::translate vector polyline
542              Translate a polyline over a given vector
543
544              list vector
545                     Translation vector
546
547              list polyline
548                     The polyline to be translated
549
550
551       ::math::geometry::rotate angle polyline
552              Rotate a polyline over a given angle (degrees) around the origin
553
554              list angle
555                     Angle over which to rotate the polyline (degrees)
556
557              list polyline
558                     The polyline to be rotated
559
560
561       ::math::geometry::reflect angle polyline
562              Reflect a polyline in a line through the origin at a given angle
563              (degrees) to the x-axis
564
565              list angle
566                     Angle of the line of reflection (degrees)
567
568              list polyline
569                     The polyline to be reflected
570
571
572       ::math::geometry::degToRad angle
573              Convert from degrees to radians
574
575              list angle
576                     Angle in degrees
577
578
579       ::math::geometry::radToDeg angle
580              Convert from radians to degrees
581
582              list angle
583                     Angle in radians
584
585       ::math::geometry::circle centre radius
586              Convenience  procedure to create a circle from a point and a ra‐
587              dius.
588
589              list centre
590                     Coordinates of the circle centre
591
592              list radius
593                     Radius of the circle
594
595       ::math::geometry::circleTwoPoints point1 point2
596              Convenience procedure to create a circle from two points on  its
597              circumference  The  centre  is  the  point between the two given
598              points, the radius is half the distance between them.
599
600              list point1
601                     First point
602
603              list point2
604                     Second point
605
606       ::math::geometry::pointInsideCircle point circle
607              Determine if the given point is inside the circle or on the cir‐
608              cumference (1) or outside (0).
609
610              list point
611                     Point to be checked
612
613              list circle
614                     Circle that may or may not contain the point
615
616       ::math::geometry::lineIntersectsCircle line circle
617              Determine  if the given line intersects the circle or touches it
618              (1) or does not (0).
619
620              list line
621                     Line to be checked
622
623              list circle
624                     Circle that may or may not be intersected
625
626       ::math::geometry::lineSegmentIntersectsCircle segment circle
627              Determine if the given line segment  intersects  the  circle  or
628              touches it (1) or does not (0).
629
630              list segment
631                     Line segment to be checked
632
633              list circle
634                     Circle that may or may not be intersected
635
636       ::math::geometry::intersectionLineWithCircle line circle
637              Determine the points at which the given line intersects the cir‐
638              cle. There can be zero, one or two points. (If the line  touches
639              the circle or is close to it, then one point is returned. An ar‐
640              bitrary margin of 1.0e-10 times the radius is used to  determine
641              this situation.)
642
643              list line
644                     Line to be checked
645
646              list circle
647                     Circle that may or may not be intersected
648
649       ::math::geometry::intersectionCircleWithCircle circle1 circle2
650              Determine  the  points at which the given two circles intersect.
651              There can be zero, one or two points. (If the two circles  touch
652              the circle or are very close, then one point is returned. An ar‐
653              bitrary margin of 1.0e-10 times the mean of the radii of the two
654              circles is used to determine this situation.)
655
656              list circle1
657                     First circle
658
659              list circle2
660                     Second circle
661
662       ::math::geometry::tangentLinesToCircle point circle
663              Determine  the tangent lines from the given point to the circle.
664              There can be zero, one or two lines. (If the  point  is  on  the
665              cirucmference  or very close to the circle, then one line is re‐
666              turned. An arbitrary margin of 1.0e-10 times the radius  of  the
667              circle is used to determine this situation.)
668
669              list point
670                     Point in question
671
672              list circle
673                     Circle to which the tangent lines are to be determined
674

REFERENCES

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

BUGS, IDEAS, FEEDBACK

683       This  document,  and the package it describes, will undoubtedly contain
684       bugs and other problems.  Please report such in the  category  math  ::
685       geometry of the Tcllib Trackers [http://core.tcl.tk/tcllib/reportlist].
686       Please also report any ideas for enhancements you may have  for  either
687       package and/or documentation.
688
689       When proposing code changes, please provide unified diffs, i.e the out‐
690       put of diff -u.
691
692       Note further that  attachments  are  strongly  preferred  over  inlined
693       patches.  Attachments  can  be  made  by  going to the Edit form of the
694       ticket immediately after its creation, and  then  using  the  left-most
695       button in the secondary navigation bar.
696

KEYWORDS

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

CATEGORY

701       Mathematics
702
704       Copyright (c) 2001 by Ideogramic ApS and other parties
705       Copyright (c) 2010 by Andreas Kupries
706       Copyright (c) 2010 by Kevin Kenny
707       Copyright (c) 2018 by Arjen Markus
708
709
710
711
712tcllib                               1.3.0                   math::geometry(n)
Impressum