Clip

JavaScript object containing the intersection of two paths. Every intersection point is on one path, but comes with a neighbour point having the same coordinates and being on the other path.

The intersection point is inserted into the doubly linked list of the path.

Parameters

Name	Type	Description
`coords`	JXG.Coords	JSXGraph Coords object containing the coordinates of the intersection
`i`	Number	Number of the segment of the subject path (first path) containing the intersection.
`alpha`	Number	The intersection is a p_1 + alpha*(p_2 - p_1), where p_1 and p_2 are the end points of the i-th segment.
`path`	Array	Pointer to the path containing the intersection point
`pathname`	String	Name of the path: 'S' or 'C'.

Details

Source: math/clip.js, line 128

(private, static) _addVertex(path, vertex, DEBUG) → {Boolean}

Add a point to the clipping path and returns if the algorithms arrived at an intersection point which has already been visited. In this case, true is returned.

Parameters

Name	Type	Description
`path`	Array	Resulting path
`vertex`	JXG.Math.Clip.Vertex	Point to be added
`DEBUG`	Boolean	if true, write debug output to console.log

Returns

true: point has been visited before, false otherwise

Type: Boolean

Details

Source: math/clip.js, line 1196

(private, static) _classifyDegenerateIntersections(P)

Determine the delayed status of degenerated intersection points. It is of the form ['on|left|right', 'on|left|right']

If all four determinants are zero, we add random noise to the point.

Parameters

Name	Type	Description
`P`	JXG.Math.Clip.Vertex	Start of path

Details

See

Source

math/clip.js, line 613

(private, static) _countCrossingIntersections(intersections)

Count intersection points of type 'X'.

Parameters

Name	Type	Description
`intersections`	JXG.Mat.Clip.Vertex

Returns

Number

Details

Source: math/clip.js, line 1578

(private, static) _getPath(obj, board) → {Array}

Create path from all sorts of input elements and convert it to a suitable input path for greinerHormann().

Parameters

Name	Type	Description
`obj`	Object	Maybe curve, arc, sector, circle, polygon, array of points, array of JXG.Coords, array of coordinate pairs.
`board`	JXG.Board	JSXGraph board object. It is needed to convert between user coordinates and screen coordinates.

Returns

Array of JXG.Coords elements containing a path.

Type: Array

Details

See

JXG.Math.Clip.greinerHormann

Source

math/clip.js, line 1604

(private, static) _getPosition(q, p1, p2, p3)

It is testedd if the point q lies to the left or right of the poylgonal chain [p1, p2, p3].

Parameters

Name	Type	Description
`q`	Array	User coords array
`p1`	Array	User coords array
`p2`	Array	User coords array
`p3`	Array	User coords array

Returns

string 'left' or 'right'

Details

Source: math/clip.js, line 581

(private, static) _handleFullyDegenerateCase(S, C, board)

Handle the case that all vertices of one path are contained in the other path. In this case we search for a midpoint of an edge which is not contained in the other path and add it to the path. It will be used as starting point for the entry/exit algorithm.

Parameters

Name	Type	Description
`S`	Array	Subject path
`C`	Array	Clip path
`board`	JXG.board	JSXGraph board object. It is needed to convert between user coordinates and screen coordinates.

Details

Source: math/clip.js, line 923

(private, static) _handleIntersectionChains(P)

At this point the degenerated intersections have been classified. Now we decide if the intersection chains of the given path ultimatively cross the other path or bounce.

Parameters

Name	Type	Description
`P`	JXG.Math.Clip.Vertex	Start of path

Details

See

Source

math/clip.js, line 813

(private, static) _stayOnPath(P, isBackward) → {Boolean}

Parameters

Name	Type	Description
`P`	Array
`isBackward`	Boolean

Returns

True, if the node is an intersection and is of type 'X'

Type: Boolean

Details

Source: math/clip.js, line 1175

(static) difference(subject, clip, board) → {Array}

Difference of two closed paths, i.e. path1 minus path2. The paths could be JSXGraph elements circle, curve, or polygon. Computed by the Greiner-Hormann algorithm.

Example

var curve1 = board.create('polygon', [[-4, 4], [4, 4], [0, -1]],
            {strokeColor: 'blue', fillColor: 'none'});

    var curve2 = board.create('curve', [
            [-1, 1, 0, -1],
            [1, 1, 3, 1]
        ],
        {strokeColor: 'black', fillColor: 'none', fillOpacity: 0.8});

    var clip_path = board.create('curve', [[], []], {strokeWidth: 3, fillColor: 'yellow', fillOpacity: 0.3});
    clip_path.updateDataArray = function() {
        var a = JXG.Math.Clip.difference(curve1, curve2, this.board);
        this.dataX = a[0];
        this.dataY = a[1];
    };

    board.update();

Parameters

Name	Type	Description
`subject`	Circle \| Curve \| Polygon	First closed path.
`clip`	Circle \| Curve \| Polygon	Second closed path.
`board`	JXG.Board	JSXGraph board object. It is needed to convert between user coordinates and screen coordinates.

Returns

Array consisting of two arrays containing the x-coordinates and the y-coordinates of the resulting path.

Type: Array

Details

See

Source

math/clip.js, line 2220

(private, static) findIntersections(S, C, board) → {Array}

Find all intersections between two paths.

Parameters

Name	Type	Description
`S`	Array	Subject path
`C`	Array	Clip path
`board`	JXG.Board	JSXGraph board object. It is needed to convert between user coordinates and screen coordinates.

Returns

Array containing two arrays. The first array contains the intersection vertices of the subject path and the second array contains the intersection vertices of the clip path.

Type: Array

Details

See

JXG.Math.Clip.Vertex

Source

math/clip.js, line 356

(static) greinerHormann(subject, clip, clip_type, board) → {Array}

Determine the intersection, union or difference of two closed paths.

This is an implementation of the Greiner-Hormann algorithm, see Günther Greiner and Kai Hormann (1998). "Efficient clipping of arbitrary polygons". ACM Transactions on Graphics. 17 (2): 71–83. and Erich, L. Foster, and Kai Hormann, Kai, and Romeo Traaian Popa (2019), "Clipping simple polygons with degenerate intersections", Computers & Graphics:X, 2.

It is assumed that the pathes are closed, whereby it does not matter if the last point indeed equals the first point. In contrast to the original Greiner-Hormann algorithm, this algorithm can cope with many degenerate cases. A degenerate case is a vertext of one path which is contained in the other path.

Problematic are:

degenerate cases where one path additionally has self-intersections
differences with one path having self-intersections.

Examples

var curve1 = board.create('curve', [
            [-3, 3, 0, -3],
            [3, 3, 0, 3]
        ],
        {strokeColor: 'black'});

    var curve2 = board.create('curve', [
            [-4, 4, 0, -4],
            [2, 2, 4, 2]
        ],
        {strokeColor: 'blue'});

    var clip_path = board.create('curve', [[], []], {strokeWidth: 3, fillColor: 'yellow', fillOpacity: 0.6});
    clip_path.updateDataArray = function() {
        var a = JXG.Math.Clip.greinerHormann(curve2, curve1, 'intersection', this.board);

        this.dataX = a[0];
        this.dataY = a[1];
    };

    board.update();

var curve1 = board.create('curve', [
            [-3, 3, 0, -3],
            [3, 3, 0, 3]
        ],
        {strokeColor: 'black', fillColor: 'none', fillOpacity: 0.8});

    var curve2 = board.create('polygon', [[3, 4], [-4, 0], [-4, 4]],
            {strokeColor: 'blue', fillColor: 'none'});

    var clip_path = board.create('curve', [[], []], {strokeWidth: 3, fillColor: 'yellow', fillOpacity: 0.6});
    clip_path.updateDataArray = function() {
        var a = JXG.Math.Clip.greinerHormann(curve1, curve2, 'union', this.board);
        this.dataX = a[0];
        this.dataY = a[1];
    };

    board.update();

var curve1 = board.create('curve', [
            [-4, 4, 0, -4],
            [4, 4, -2, 4]
        ],
        {strokeColor: 'black', fillColor: 'none', fillOpacity: 0.8});

    var curve2 = board.create('circle', [[0, 0], [0, -2]],
            {strokeColor: 'blue', strokeWidth: 1, fillColor: 'red', fixed: true, fillOpacity: 0.3,
            center: {visible: true, size: 5}, point2: {size: 5}});

    var clip_path = board.create('curve', [[], []], {strokeWidth: 3, fillColor: 'yellow', fillOpacity: 0.6});
    clip_path.updateDataArray = function() {
        var a = JXG.Math.Clip.greinerHormann(curve1, curve2, 'difference', this.board);

        this.dataX = a[0];
        this.dataY = a[1];
    };

    board.update();

var clip_path = board.create('curve', [[], []], {strokeWidth: 1, fillColor: 'yellow', fillOpacity: 0.6});
clip_path.updateDataArray = function() {
    var bbox = this.board.getBoundingBox(),
        canvas, triangle;

    canvas = [[bbox[0], bbox[1]], // ul
         [bbox[0], bbox[3]], // ll
         [bbox[2], bbox[3]], // lr
         [bbox[2], bbox[1]], // ur
         [bbox[0], bbox[1]]] // ul
    triangle = [[-1,1], [1,1], [0,-1], [-1,1]];

    var a = JXG.Math.Clip.greinerHormann(canvas, triangle, 'difference', this.board);
    this.dataX = a[0];
    this.dataY = a[1];
};

Parameters

Name	Type	Description
`subject`	Circle \| Curve \| Polygon	First closed path, usually called 'subject'. Maybe curve, arc, sector, circle, polygon, array of points, array of JXG.Coords, array of coordinate pairs.
`clip`	Circle \| Curve \| Polygon	Second closed path, usually called 'clip'. Maybe curve, arc, sector, circle, polygon, array of points, array of JXG.Coords, array of coordinate pairs.
`clip_type`	String	Determines the type of boolean operation on the two paths. Possible values are 'intersection', 'union', or 'difference'.
`board`	JXG.Board	JSXGraph board object. It is needed to convert between user coordinates and screen coordinates.

Returns

Array consisting of two arrays containing the x-coordinates and the y-coordinates of the resulting path.

Type: Array

Details

See

Source

math/clip.js, line 1929

(private, static) handleEmptyIntersection(S, C, clip_type) → {Array}

Handle cases when there are no intersection points of the two paths. This is the case if the paths are disjoint or one is contained in the other.

Parameters

Name	Type	Description
`S`	Array	First path, array of JXG.Coords
`C`	Array	Second path, array of JXG.Coords
`clip_type`	String	Type of Boolean operation: 'intersection', 'union', 'differrence'.

Returns

Array consisting of two arrays containing the x-coordinates and the y-coordinates of the resulting path.

Type: Array

Details

Source: math/clip.js, line 1466

(static) intersection(subject, clip, board) → {Array}

Intersection of two closed paths. The paths could be JSXGraph elements circle, curve, or polygon. Computed by the Greiner-Hormann algorithm.

Example

var p = [];
p.push(board.create('point', [0, -5]));
p.push(board.create('point', [-5, 0]));
p.push(board.create('point', [-3, 3]));

var curve1 = board.create('ellipse', p,
                {strokeColor: 'black'});

var curve2 = board.create('curve', [function(phi){return 4 * Math.cos(2*phi); },
                                    [0, 0],
                                    0, 2 * Math.PI],
                      {curveType:'polar', strokeColor: 'blue', strokewidth:1});

var clip_path = board.create('curve', [[], []], {strokeWidth: 3, fillColor: 'yellow', fillOpacity: 0.3});
clip_path.updateDataArray = function() {
    var a = JXG.Math.Clip.intersection(curve2, curve1, this.board);

    this.dataX = a[0];
    this.dataY = a[1];
};

board.update();

Parameters

Name	Type	Description
`subject`	Circle \| Curve \| Polygon	First closed path.
`clip`	Circle \| Curve \| Polygon	Second closed path.
`board`	JXG.Board	JSXGraph board object. It is needed to convert between user coordinates and screen coordinates.

Returns

Array consisting of two arrays containing the x-coordinates and the y-coordinates of the resulting path.

Type: Array

Details

See

Source

math/clip.js, line 2151

(private, static) isEmptyCase(S, C, clip_type) → {Boolean}

Handle path clipping if one of the two paths is empty.

Parameters

Name	Type	Description
`S`	Array	First path, array of JXG.Coords
`C`	Array	Second path, array of JXG.Coords
`clip_type`	String	Type of Boolean operation: 'intersection', 'union', 'differrence'.

Returns

true, if one of the input paths is empty, false otherwise.

Type: Boolean

Details

Source: math/clip.js, line 1413

(private, static) makeDoublyLinkedList(S) → {Array}

Add pointers to an array S such that it is a circular doubly-linked list.

Parameters

Name	Type	Description
`S`	Array	Array

Returns

return containing the starter indices of each component.

Type: Array

Details

Source: math/clip.js, line 68

(private, static) markEntryExit(path1, path2)

Mark the intersection vertices of path1 as entry points or as exit points in respect to path2.

This is the simple algorithm as in Greiner, Günther; Kai Hormann (1998). "Efficient clipping of arbitrary polygons". ACM Transactions on Graphics. 17 (2): 71–83

The algorithm handles also "delayed crossings" from Erich, L. Foster, and Kai Hormann, Kai, and Romeo Traaian Popa (2019), "Clipping simple polygons with degenerate intersections", Computers & Graphics:X, 2. and - as an additional improvement - handles self intersections of delayed crossings (A.W. 2021).

Parameters

Name	Type	Description
`path1`	Array	First path
`path2`	Array	Second path

Details

Source: math/clip.js, line 1038

(private, static) sortIntersections(P_crossings) → {Array}

Sort the intersection points into their path.

Parameters

Name	Type	Description
`P_crossings`	Array	Array of arrays. Each array contains the intersections of the path with one segment of the other path.

Returns

Array of intersection points ordered by first occurrence in the path.

Type: Array

Details

Source: math/clip.js, line 177

(private, static) tracing(S, S_intersect, clip_type) → {Array}

Tracing phase of the Greiner-Hormann algorithm, see Greiner, Günther; Kai Hormann (1998). "Efficient clipping of arbitrary polygons". ACM Transactions on Graphics. 17 (2): 71–83

Boolean operations on polygons are distinguished: 'intersection', 'union', 'difference'.

Parameters

Name	Type	Description
`S`	Array	Subject path
`S_intersect`	Array	Array containing the intersection vertices of the subject path
`clip_type`	String	contains the Boolean operation: 'intersection', 'union', or 'difference'

Returns

Array consisting of two arrays containing the x-coordinates and the y-coordintaes of the resulting path.

Type: Array

Details

Source: math/clip.js, line 1245

(static) union(subject, clip, board) → {Array}

Union of two closed paths. The paths could be JSXGraph elements circle, curve, or polygon. Computed by the Greiner-Hormann algorithm.

Example

var curve1 = board.create('curve', [
            [-3, 3, 0, -3],
            [3, 3, 0, 3]
        ],
        {strokeColor: 'black'});

    var curve2 = board.create('polygon', [[3, 4], [-4, 0], [-4, 4]],
            {strokeColor: 'blue', fillColor: 'none'});

    var clip_path = board.create('curve', [[], []], {strokeWidth: 3, fillColor: 'yellow', fillOpacity: 0.3});
    clip_path.updateDataArray = function() {
        var a = JXG.Math.Clip.union(curve1, curve2, this.board);
        this.dataX = a[0];
        this.dataY = a[1];
    };

    board.update();

Parameters

Name	Type	Description
`subject`	Circle \| Curve \| Polygon	First closed path.
`clip`	Circle \| Curve \| Polygon	Second closed path.
`board`	JXG.Board	JSXGraph board object. It is needed to convert between user coordinates and screen coordinates.

Returns

Array consisting of two arrays containing the x-coordinates and the y-coordinates of the resulting path.

Type: Array

Details

See

Source

math/clip.js, line 2072

Inherited

none

Details

Source: math/clip.js, line 48