JavaScript must be enabled in order for you to use JSXGraph and JSXGraph reference. However, it seems JavaScript is either disabled or not supported by your browser.

Class Index | File Index
Elements
Classes

Namespace JXG.Math.Clip


      ↳ JXG.Math.Clip



Defined in: clip.js.

Namespace Summary
Constructor Attributes Constructor Name and Description
 
JXG.Math.Clip
Math.Clip namespace definition.
Method Summary
Method Attributes Method Name and Description
<private> <static>  
JXG.Math.Clip._addVertex(path, vertex, DEBUG)
Add a point to the clipping path and returns if the algorithms arrived at an intersection point which has already been visited.
<private> <static>  
JXG.Math.Clip._classifyDegenerateIntersections(P)
Determine the delayed status of degenerated intersection points.
<private> <static>  
JXG.Math.Clip._countCrossingIntersections(intersections)
Count intersection points of type 'X'.
<private> <static>  
JXG.Math.Clip._getPath(obj, board)
Create path from all sorts of input elements and convert it to a suitable input path for greinerHormann().
<private> <static>  
JXG.Math.Clip._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].
<private> <static>  
JXG.Math.Clip._handleFullyDegenerateCase(S, C, board)
Handle the case that all vertices of one path are contained in the other path.
<private> <static>  
JXG.Math.Clip._handleIntersectionChains(P)
At this point the degenerated intersections have been classified.
<private> <static>  
JXG.Math.Clip._stayOnPath(P, isBackward)
<static>  
JXG.Math.Clip.difference(subject, clip, board)
Difference of two closed paths, i.e.
<private> <static>  
JXG.Math.Clip.findIntersections(S, C, board)
Find all intersections between two paths.
<static>  
JXG.Math.Clip.greinerHormann(subject, clip, clip_type, board)
Determine the intersection, union or difference of two closed paths.
<private> <static>  
JXG.Math.Clip.handleEmptyIntersection(S, C, clip_type)
Handle cases when there are no intersection points of the two paths.
<static>  
JXG.Math.Clip.intersection(subject, clip, board)
Intersection of two closed paths.
<private> <static>  
JXG.Math.Clip.isEmptyCase(S, C, clip_type)
Handle path clipping if one of the two paths is empty.
<private> <static>  
JXG.Math.Clip.makeDoublyLinkedList(S)
Add pointers to an array S such that it is a circular doubly-linked list.
<private> <static>  
JXG.Math.Clip.markEntryExit(path1, path2, starters)
Mark the intersection vertices of path1 as entry points or as exit points in respect to path2.
<private> <static>  
JXG.Math.Clip.sortIntersections(P_crossings)
Sort the intersection points into their path.
<private> <static>  
JXG.Math.Clip.tracing(S, S_intersect, clip_type)
Tracing phase of the Greiner-Hormann algorithm, see Greiner, Günther; Kai Hormann (1998).
<static>  
JXG.Math.Clip.union(subject, clip, board)
Union of two closed paths.
<private> <static>  
JXG.Math.Clip.Vertex(coords, i, alpha, path, pathname, type)
JavaScript object containing the intersection of two paths.
Namespace Detail
JXG.Math.Clip
Math.Clip namespace definition. This namespace contains algorithms for Boolean operations on paths, i.e. intersection, union and difference of paths. Base is the Greiner-Hormann algorithm.
Method Detail
<private> <static> {Boolean} JXG.Math.Clip._addVertex(path, vertex, DEBUG)
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:
{Array} path
Resulting path
{JXG.Math.Clip.Vertex} vertex
Point to be added
{Boolean} DEBUG
debug output to console.log
Returns:
{Boolean} true: point has been visited before, false otherwise
<private> <static> JXG.Math.Clip._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:
{JXG.Math.Clip.Vertex} P
Start of path
See:
JXG.Math.Clip.markEntryExit
JXG.Math.Clip._handleIntersectionChains
<private> <static> JXG.Math.Clip._countCrossingIntersections(intersections)
Count intersection points of type 'X'.
Parameters:
{JXG.Mat.Clip.Vertex} intersections
Returns:
Number
<private> <static> {Array} JXG.Math.Clip._getPath(obj, board)
Create path from all sorts of input elements and convert it to a suitable input path for greinerHormann().
Parameters:
{Object} obj
Maybe curve, arc, sector, circle, polygon, array of points, array of JXG.Coords, array of coordinate pairs.
{JXG.Board} board
JSXGraph board object. It is needed to convert between user coordinates and screen coordinates.
Returns:
{Array} Array of JXG.Coords elements containing a path.
See:
JXG.Math.Clip.greinerHormann
<private> <static> JXG.Math.Clip._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:
{Array} q
User coords array
{Array} p1
User coords array
{Array} p2
User coords array
{Array} p3
User coords array
Returns:
string 'left' or 'right'
<private> <static> JXG.Math.Clip._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:
{Array} S
Subject path
{Array} C
Clip path
{JXG.board} board
JSXGraph board object. It is needed to convert between user coordinates and screen coordinates.
<private> <static> JXG.Math.Clip._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:
{JXG.Math.Clip.Vertex} P
Start of path
See:
JXG.Math.Clip.markEntryExit
JXG.Math.Clip._classifyDegenerateIntersections
<private> <static> {Boolean} JXG.Math.Clip._stayOnPath(P, isBackward)
Parameters:
{Array} P
{Boolean} isBackward
Returns:
{Boolean} True, if the node is an intersection and is of type 'X'
<static> {Array} JXG.Math.Clip.difference(subject, clip, board)
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.
Parameters:
{JXG.Circle|JXG.Curve|JXG.Polygon} subject
First closed path.
{JXG.Circle|JXG.Curve|JXG.Polygon} clip
Second closed path.
{JXG.Board} board
JSXGraph board object. It is needed to convert between user coordinates and screen coordinates.
Returns:
{Array} Array consisting of two arrays containing the x-coordinates and the y-coordinates of the resulting path.
See:
JXG.Math.Clip.greinerHormann
JXG.Math.Clip.intersection
JXG.Math.Clip.union
Examples:
    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();



					
					

					

					

				
					 
					
<private> <static> 

					{Array}
					JXG.Math.Clip.findIntersections(S, C, board)

					

					

						Find all intersections between two paths.
						
						
					


						
							

							
Parameters:

							
								

									{Array} S
									
								

								
Subject path

							
								

									{Array} C
									
								

								
Clip path

							
								

									{JXG.Board} board
									
								

								
JSXGraph board object. It is needed to convert between
user coordinates and screen coordinates.

							
							

						
						
						
						
						
							

							
Returns:

							
								
{Array} 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.

							
							

						
						
						
							

							
See:

							
								
JXG.Math.Clip.Vertex

							
							

						

					

					

				
					 
					
<static> 

					{Array}
					JXG.Math.Clip.greinerHormann(subject, clip, clip_type, board)

					

					

						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:


						
						
					


						
							

							
Parameters:

							
								

									{JXG.Circle|JXG.Curve|JXG.Polygon} subject
									
								

								
First closed path, usually called 'subject'.
Maybe curve, arc, sector, circle, polygon, array of points, array of JXG.Coords,
array of coordinate pairs.

							
								

									{JXG.Circle|JXG.Curve|JXG.Polygon} clip
									
								

								
Second closed path, usually called 'clip'.
Maybe curve, arc, sector, circle, polygon, array of points, array of JXG.Coords,
array of coordinate pairs.

							
								

									{String} clip_type
									
								

								
Determines the type of boolean operation on the two paths.
 Possible values are 'intersection', 'union', or 'difference'.

							
								

									{JXG.Board} board
									
								

								
JSXGraph board object. It is needed to convert between
user coordinates and screen coordinates.

							
							

						
						
						
						
						
							

							
Returns:

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

							
							

						
						
						
							

							
See:

							
								
JXG.Math.Clip.intersection

							
								
JXG.Math.Clip.union

							
								
JXG.Math.Clip.difference

							
							

						

					
					

					
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];
};





					
					

					

					

				
					 
					
<private> <static> 

					{Array}
					JXG.Math.Clip.handleEmptyIntersection(S, C, clip_type)

					

					

						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:

							
								

									{Array} S
									
								

								
First path, array of JXG.Coords

							
								

									{Array} C
									
								

								
Second path, array of JXG.Coords

							
								

									{String} clip_type
									
								

								
Type of Boolean operation: 'intersection', 'union', 'differrence'.

							
							

						
						
						
						
						
							

							
Returns:

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

							
							

						
						
						

					

					

				
					 
					
<static> 

					{Array}
					JXG.Math.Clip.intersection(subject, clip, board)

					

					

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


						
							

							
Parameters:

							
								

									{JXG.Circle|JXG.Curve|JXG.Polygon} subject
									
								

								
First closed path.

							
								

									{JXG.Circle|JXG.Curve|JXG.Polygon} clip
									
								

								
Second closed path.

							
								

									{JXG.Board} board
									
								

								
JSXGraph board object. It is needed to convert between
user coordinates and screen coordinates.

							
							

						
						
						
						
						
							

							
Returns:

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

							
							

						
						
						
							

							
See:

							
								
JXG.Math.Clip.greinerHormann

							
								
JXG.Math.Clip.union

							
								
JXG.Math.Clip.difference

							
							

						

					
					

					
Examples:

					
					
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();





					
					

					

					

				
					 
					
<private> <static> 

					{Boolean}
					JXG.Math.Clip.isEmptyCase(S, C, clip_type)

					

					

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


						
							

							
Parameters:

							
								

									{Array} S
									
								

								
First path, array of JXG.Coords

							
								

									{Array} C
									
								

								
Second path, array of JXG.Coords

							
								

									{String} clip_type
									
								

								
Type of Boolean operation: 'intersection', 'union', 'differrence'.

							
							

						
						
						
						
						
							

							
Returns:

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

							
							

						
						
						

					

					

				
					 
					
<private> <static> 

					{Array}
					JXG.Math.Clip.makeDoublyLinkedList(S)

					

					

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


						
							

							
Parameters:

							
								

									{Array} S
									
								

								
Array

							
							

						
						
						
						
						
							

							
Returns:

							
								
{Array} return containing the starter indices of each component.

							
							

						
						
						

					

					

				
					 
					
<private> <static> 

					
					JXG.Math.Clip.markEntryExit(path1, path2, starters)

					

					

						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:

							
								

									{Array} path1
									
								

								
First path

							
								

									{Array} path2
									
								

								
Second path

							
								

									starters
									
								

								

							
							

						
						
						
						
						
						
						

					

					

				
					 
					
<private> <static> 

					{Array}
					JXG.Math.Clip.sortIntersections(P_crossings)

					

					

						Sort the intersection points into their path.
						
						
					


						
							

							
Parameters:

							
								

									{Array} P_crossings
									
								

								
Array of arrays. Each array contains the intersections of the path
     with one segment of the other path.

							
							

						
						
						
						
						
							

							
Returns:

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

							
							

						
						
						

					

					

				
					 
					
<private> <static> 

					{Array}
					JXG.Math.Clip.tracing(S, S_intersect, clip_type)

					

					

						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:

							
								

									{Array} S
									
								

								
Subject path

							
								

									{Array} S_intersect
									
								

								
Array containing the intersection vertices of the subject path

							
								

									{String} clip_type
									
								

								
contains the Boolean operation: 'intersection', 'union', or 'difference'

							
							

						
						
						
						
						
							

							
Returns:

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

							
							

						
						
						

					

					

				
					 
					
<static> 

					{Array}
					JXG.Math.Clip.union(subject, clip, board)

					

					

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


						
							

							
Parameters:

							
								

									{JXG.Circle|JXG.Curve|JXG.Polygon} subject
									
								

								
First closed path.

							
								

									{JXG.Circle|JXG.Curve|JXG.Polygon} clip
									
								

								
Second closed path.

							
								

									{JXG.Board} board
									
								

								
JSXGraph board object. It is needed to convert between
user coordinates and screen coordinates.

							
							

						
						
						
						
						
							

							
Returns:

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

							
							

						
						
						
							

							
See:

							
								
JXG.Math.Clip.greinerHormann

							
								
JXG.Math.Clip.intersection

							
								
JXG.Math.Clip.difference

							
							

						

					
					

					
Examples:

					
					
    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();





					
					

					

					

				
					 
					
<private> <static> 

					
					JXG.Math.Clip.Vertex(coords, i, alpha, path, pathname, type)

					

					

						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:

							
								

									{JXG.Coords} coords
									
								

								
JSXGraph Coords object containing the coordinates of the intersection

							
								

									{Number} i
									
								

								
Number of the segment of the subject path (first path) containing the intersection.

							
								

									{Number} alpha
									
								

								
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.

							
								

									{Array} path
									
								

								
Pointer to the path containing the intersection point

							
								

									{String} pathname
									
								

								
Name of the path: 'S' or 'C'.

							
								

									type
									
								

								

							
							

						
						
						
						
						
						
						

					

					
				
			


			

			


			

		




		

			
			Documentation generated by JsDoc Toolkit 2.4.0 on Fri Nov 08 2024 12:13:05 GMT+0100 (Mitteleuropäische Normalzeit)