### 15.3.452  src/lib/std/2d/geometry2d.api

`## geometry2d.api`
`#`
`# The api of the basic geometry types and operations.`

`# Compiled by:`
`#     `src/lib/std/standard.lib

`###            "Life without geometry is pointless."`

`###            "Let no one ignorant of Geometry enter here."    -- Pythagoras`

`# This api is implemented in:`
`#`
`#     `src/lib/std/2d/geometry2d.pkg

`# Used in:`
`#     `src/lib/x-kit/draw/band.pkg
`#     `src/lib/x-kit/draw/scan-convert.pkg

`api Geometry2d {`

`    # Geometric types (from Xlib::h) `
`    #`
`    Point =   { row:  Int,`
`                col:  Int`
`              };`

`    Line =    (Point, Point);`

`    Size =    { wide:  Int,`
`                high:  Int`
`              };`

`    # Screen rectangles represented as`
`    # upper-left corner plus size.`
`    #`
`    # For two-corner box representation see`
`    #     `src/lib/x-kit/draw/box2.pkg
`    #`
`    Box = { row:   Int,`
`            col:   Int,`
`            wide:  Int,`
`            high:  Int`
`          };`

`    Arc =   { row:  Int,`
`              col:  Int,`

`              wide:  Int,`
`              high:  Int,`

`              start_angle:  Float,              # In degrees, with zero angle at 3 o'clock, increasing counterclockwise.  Use positive angles from 0.0 to 360.0.`
`              fill_angle:   Float               # Draw a pie-slice of this many degrees starting at start_angle and running counterclockwise from there.`
`            };`
`                                                # Examples:`
`                                                #     Upper-right quadrant ==  { ..., start_angle =>   0.0,  fill_angle =>  90.0 }`
`                                                #     Upper-left  quadrant ==  { ..., start_angle =>  90.0,  fill_angle =>  90.0 }`
`                                                #     Lower-left  quadrant ==  { ..., start_angle => 180.0,  fill_angle =>  90.0 }`
`                                                #     Lower-right quadrant ==  { ..., start_angle => 270.0,  fill_angle =>  90.0 }`
`                                                #     Upper half           ==  { ...  start_angle =>   0.0,  fill_angle => 180.0 };`
`                                                #     Lower half           ==  { ...  start_angle => 180.0,  fill_angle => 180.0 };`
`                                                #     Full disk            ==  { ..., start_angle =>   0.0,  fill_angle => 360.0 }`

`    Arc64 = { row:  Int,`
`              col:  Int,`
`              #`
`              wide:  Int,`
`              high:  Int,`
`              #`
`              angle1:  Int,                     # In degrees * 64, with zero angle at 3 o'clock, increasing counterclockwise.`
`              angle2:  Int                      # In degrees * 64. Arc is drawn from angle1 for angle2 degrees.`
`            };`

`    # The size and position of a window`
`    # relative to its parent.`
`    #`
`    # Note that position does not take`
`    # border_thickness into account.`
`    #`
`    Window_Site`
`        =`
`        {`
`          upperleft:            Point,`
`          size:                 Size,`
`          border_thickness:     Int             # In pixels.`
`        };`

`    # Points: `
`    #`
`    package point:  api {`
`        #`
`        zero:      Point;                       # Point (0,0).`

`        row:       Point -> Int;`
`        col:       Point -> Int;`

`        scale:    (Point, Int  ) -> Point;`

`        add:      (Point, Point) -> Point;`
`        subtract: (Point, Point) -> Point;`

`        add_size: (Point, Size ) -> Point;`
`        clip:     (Point, Size ) -> Point;      # Clip point to be within box defined by point::zero and size, using orthogonal projection..`

`        ne:       (Point, Point) -> Bool;       # x1 != x2 or  y1 != y2.`
`        eq:       (Point, Point) -> Bool;       # x1 == x2 and y1 == y2.`
`        lt:       (Point, Point) -> Bool;       # x1 <  x2 and y1 <  y2.`
`        le:       (Point, Point) -> Bool;       # x1 <= x2 and y1 <= y2`
`        gt:       (Point, Point) -> Bool;       # x1 >  x2 and y1 >  y2`
`        ge:       (Point, Point) -> Bool;       # x1 >= x2 and y1 >= y2`

`        in_box:   (Point, Box  ) -> Bool;       # TRUE iff point is within box.`

`        compare_xy: (Point, Point) -> Order;    # Comparison fn to sort points by X (and by Y when X coords match).`
`                                                # Used in convex_hull; generally useful when a total order is needed, e.g.:`
`                                                #`
`                                                #     points = list_mergesort::sort_list_and_drop_duplicates  point::compare_xy  points;`
`        mean:     List(Point) -> Point;`
`    };`

`    package size:  api {`
`        #`
`        add:        (Size, Size) -> Size;`
`        subtract:   (Size, Size) -> Size;`
`        scale:      (Size, Int ) -> Size;`
`        eq:         (Size, Size) -> Bool;`
`    };`
`    #`

`    package box:  api {`
`        #`
`        zero:      Box;                                                                 # Box (0,0,0,0).`

`        ne:       (Box, Box) -> Bool;`
`        eq:       (Box, Box) -> Bool;`

`        make:         (Point, Size) -> Box;`
`        upperleft:     Box -> Point;`
`        lowerright:    Box -> Point;                                                    # Returns  { col => box.col + box.wide - 1,  row => box.row + box.high - 1 }`
`        lowerright1:   Box -> Point;                                                    # Returns  { col => box.col + box.wide    ,  row => box.row + box.high     }`
`        size:          Box -> Size;`
`        area:          Box -> Int;      `
`        midpoint:      Box -> Point;`
`        to_points:     Box -> List(Point);`
`        box_corners:   Box -> { upper_left:  Point,`
`                                lower_left:  Point,`
`                                lower_right: Point,`
`                                upper_right: Point`
`                              };        `
`        upperleft_and_size:  Box -> (Point, Size);`

`        clip_point:     (Box, Point) -> Point;                                          # Clip point to be within box, using orthogonal projection.`
`        translate:      (Box, Point) -> Box;                                            # box.upperleft += point.`
`        rtranslate:     (Box, Point) -> Box;                                            # box.upperleft -= point.`
`        intersect:      (Box,   Box) -> Bool;                                           # TRUE iff the boxes overlap.`
`        intersection:   (Box,   Box) -> Null_Or(Box);                                   # Construct largest box contained by both input boxes. Return NULL if they don't overlap.`
`        union:          (Box,   Box) -> Box;                                            # Construct smallest box containing  both input boxes.`
`        xor:            (Box,   Box) -> List(Box);                                      # Construct the symmetric difference of two boxes.`
`        point_in_box:   (Point, Box) -> Bool;                                           # TRUE iff point is within box:  (box.row <= point.row < box.row + box.high) and (box.col <= point.col < box.col + box.wide).`
`        box_a_in_box_b: { a: Box, b: Box } -> Bool;                                     # TRUE iff first box is within second.`

`        point_on_box_perimeter: (Point, Box) -> Bool;                                   # `

`        make_nested_box:(Box,   Int) -> Box;                                            # Create a box nested within given box, shrunk by given number of pixels.`
`                                                                                        # Returns given box unchanged if given box is       <= 2 pixels high or wide.`
`                                                                                        # Returns given box unchanged if shrink distance is <= 0.`

`        intersect_box_with_boxes: (Box, List(Box)) -> List(Box);`

`        intersect_boxes_with_boxes: (List(Box), List(Box)) -> List(Box);`

`        quadsect_box: (Box, Point) -> List(Box);                                        # Split a box into subboxes such that none cross the horizontal or vertical line running through the given point.`

`        quadsect_boxes: (List(Box), Point) -> List(Box);`

`        subtract_box_b_from_box_a: { a: Box, b: Box } -> List(Box);                     # Split 'a' into sub-boxes which do not cross the edges of 'b', then remove all sub-boxes which are contained in 'b' and return the rest.`

`        subtract_boxes_b_from_boxes_a: { a: List(Box), b: List(Box) } -> List(Box);     # As above, but subtracting box-set b from box-set a.  We don't try to be smart, just simple -- this is intended for small-scale problems.`
`    };`

`    package line: api {`
`        #`
`        intersection                                                                    # Find the intersection of two lines. Return NULL if the lines are parallel.`
`            :`
`            (Line, Line) -> Null_Or(Point);`

`        rotate_90_degrees_counterclockwise                                              # Rotate given line segment by a right angle around first point. Result line has same first point as given line.`
`            :`
`            Line -> Line;`
`    };`

`    bounding_box:   List(Point)  -> Box;                                                # Construct bounding box for given points.`
`                                                                                        # Empty list returns BOX { col=>0, row=>0, wide=>0, high=>0 };`

`    convex_hull:  List(Point)  -> List(Point);                                          # http://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain`

`    point_in_polygon`
`        :`
`        (Point, List(Point)) -> Bool;`

`};`

`## COPYRIGHT (c) 1990, 1991 by John H. Reppy.  See SMLNJ-COPYRIGHT file for details.`
`## Subsequent changes by Jeff Prothero Copyright (c) 2010-2015,`
`## released per terms of SMLNJ-COPYRIGHT.`

Comments and suggestions to: bugs@mythryl.org