ℹ️ Select 'Choose Exercise', or randomize 'Next Random Exercise' in selected language.

Choose Exercise:
Timer 00:00
WPM --
Score --
Acc --
Correct chars --

G-Code Toolpath Optimization: Collision Avoidance with Bounding Box

CNC G-Code

Goal -- WPM

Ready
Exercise Algorithm Area
1package main

2

3import "fmt"

4

5type Point struct {

6	X float64

7	Y float64

8}

9

10type BoundingBox struct {

11	Min Point

12	Max Point

13}

14

15// isPointInsideBox checks if a point is within the bounding box (inclusive).

16func isPointInsideBox(p Point, box BoundingBox) bool {

17	return p.X >= box.Min.X && p.X <= box.Max.X && p.Y >= box.Min.Y && p.Y <= box.Max.Y

18}

19

20// lineSegmentIntersectsBox checks if a line segment (from p1 to p2) intersects with a bounding box.

21// This uses the Liang-Barsky algorithm for clipping line segments against a rectangle.

22func lineSegmentIntersectsBox(p1, p2 Point, box BoundingBox) bool {

23	// Ensure box coordinates are ordered correctly

24	minX, maxX := box.Min.X, box.Max.X

25	if minX > maxX {

26		minX, maxX = maxX, minX

27	}

28	minY, maxY := box.Min.Y, box.Max.Y

29	if minY > maxY {

30		minY, maxY = maxY, minY

31	}

32

33	dx := p2.X - p1.X

34	dy := p2.Y - p1.Y

35

36	t := [4]float64{0.0, 1.0, 0.0, 1.0} // t_enter, t_exit, initial t_enter, initial t_exit

37	p := [4]float64{-dx, dx, -dy, dy} // p_k values for clipping planes

38	q := [4]float64{p1.X - minX, maxX - p1.X, p1.Y - minY, maxY - p1.Y} // q_k values

39

40	for k := 0; k < 4; k++ {

41		if p[k] == 0.0 {

42			// Line is parallel to this clipping edge

43			if q[k] < 0.0 {

44				// Line is outside and parallel, no intersection

45				return false

46			}

47		} else {

48			r := q[k] / p[k]

49			if p[k] < 0.0 {

50				// Line enters from outside

51				if r > t[1] {

52					return false // Enters after exiting

53				}

54				if r > t[0] {

55					t[0] = r // Update entry point

56				}

57			} else { // p[k] > 0.0

58				// Line exits from inside

59				if r < t[0] {

60					return false // Exits before entering

61				}

62				if r < t[1] {

63					t[1] = r // Update exit point

64				}

65			}

66		}

67	}

68

69	// If t[0] <= t[1], the line segment intersects the box.

70	return t[0] <= t[1]

71}

72

73// checkCollision determines if a tool's next move from p1 to p2 collides with the obstacle box.

74func checkCollision(p1, p2 Point, obstacle BoundingBox) bool {

75	// Check if either endpoint is inside the box

76	if isPointInsideBox(p1, obstacle) || isPointInsideBox(p2, obstacle) {

77		return true

78	}

79

80	// Check if the line segment path intersects the box

81	return lineSegmentIntersectsBox(p1, p2, obstacle)

82}

83

84func main() {

85	// Example 1: Collision detected

86	currentPos := Point{X: 5.0, Y: 5.0}

87	nextPos := Point{X: 15.0, Y: 15.0}

88	obstacle := BoundingBox{Min: Point{X: 10.0, Y: 10.0}, Max: Point{X: 20.0, Y: 20.0}}

89

90	fmt.Println("--- Example 1: Collision Expected ---")

91	if checkCollision(currentPos, nextPos, obstacle) {

92		fmt.Printf("Collision detected! Tool path from (%.2f, %.2f) to (%.2f, %.2f) intersects obstacle.\n", currentPos.X, currentPos.Y, nextPos.X, nextPos.Y)

93	} else {

94		fmt.Printf("No collision detected for path from (%.2f, %.2f) to (%.2f, %.2f).\n", currentPos.X, currentPos.Y, nextPos.X, nextPos.Y)

95	}

96

97	// Example 2: No collision

98	currentPos2 := Point{X: 0.0, Y: 0.0}

99	nextPos2 := Point{X: 5.0, Y: 5.0}

100

101	fmt.Println("\n--- Example 2: No Collision Expected ---")

102	if checkCollision(currentPos2, nextPos2, obstacle) {

103		fmt.Printf("Collision detected! Tool path from (%.2f, %.2f) to (%.2f, %.2f) intersects obstacle.\n", currentPos2.X, currentPos2.Y, nextPos2.X, nextPos2.Y)

104	} else {

105		fmt.Printf("No collision detected for path from (%.2f, %.2f) to (%.2f, %.2f).\n", currentPos2.X, currentPos2.Y, nextPos2.X, nextPos2.Y)

106	}

107

108	// Edge Case: Endpoint inside box

109	fmt.Println("\n--- Edge Case: Endpoint Inside Box ---")

110	currentPos3 := Point{X: 5.0, Y: 5.0}

111	nextPos3 := Point{X: 12.0, Y: 12.0} // This point is inside the obstacle

112	if checkCollision(currentPos3, nextPos3, obstacle) {

113		fmt.Printf("Collision detected! Tool path from (%.2f, %.2f) to (%.2f, %.2f) intersects obstacle.\n", currentPos3.X, currentPos3.Y, nextPos3.X, nextPos3.Y)

114	} else {

115		fmt.Printf("No collision detected for path from (%.2f, %.2f) to (%.2f, %.2f).\n", currentPos3.X, currentPos3.Y, nextPos3.X, nextPos3.Y)

116	}

117

118	// Edge Case: Line parallel to an edge, outside

119	fmt.Println("\n--- Edge Case: Parallel Line Outside ---")

120	currentPos4 := Point{X: 0.0, Y: 25.0}

121	nextPos4 := Point{X: 5.0, Y: 25.0}

122	if checkCollision(currentPos4, nextPos4, obstacle) {

123		fmt.Printf("Collision detected! Tool path from (%.2f, %.2f) to (%.2f, %.2f) intersects obstacle.\n", currentPos4.X, currentPos4.Y, nextPos4.X, nextPos4.Y)

124	} else {

125		fmt.Printf("No collision detected for path from (%.2f, %.2f) to (%.2f, %.2f).\n", currentPos4.X, currentPos4.Y, nextPos4.X, nextPos4.Y)

126	}

127}
Algorithm description viewbox

G-Code Toolpath Optimization: Collision Avoidance with Bounding Box

Algorithm description:

This algorithm implements a collision detection mechanism for CNC toolpaths. It checks if a linear move (defined by two points) intersects with a rectangular obstacle (defined by a bounding box). This is a fundamental component of advanced CAM software and machine controllers to prevent damage to the workpiece, tool, or machine.

Algorithm explanation:

The `checkCollision` function determines if a tool's movement from `p1` to `p2` will intersect with an `obstacle` bounding box. It first uses `isPointInsideBox` to check if either the start or end point of the toolpath lies within the obstacle. If not, it calls `lineSegmentIntersectsBox` to perform a more rigorous check. `lineSegmentIntersectsBox` implements the Liang-Barsky line clipping algorithm, which is efficient for clipping a line segment against a rectangular window. It calculates parameters `t` representing the intersection points along the line segment relative to its endpoints. If the calculated `t` values indicate an intersection within the segment's bounds (0 to 1), it returns `true`. The time complexity is O(1) because the number of operations is constant, regardless of the input points or box dimensions. The space complexity is also O(1). Edge cases handled include endpoints inside the box, lines parallel to box edges (both inside and outside), and correctly ordered box coordinates. The algorithm's correctness relies on the established geometric principles of line-rectangle intersection.

Pseudocode:

FUNCTION checkCollision(p1, p2, obstacle):
  IF isPointInsideBox(p1, obstacle) OR isPointInsideBox(p2, obstacle):
    RETURN true

  RETURN lineSegmentIntersectsBox(p1, p2, obstacle)

FUNCTION lineSegmentIntersectsBox(p1, p2, box):
  // Ensure box min/max are ordered correctly
  minX = min(box.Min.X, box.Max.X)
  maxX = max(box.Min.X, box.Max.X)
  minY = min(box.Min.Y, box.Max.Y)
  maxY = max(box.Min.Y, box.Max.Y)

  dx = p2.X - p1.X
  dy = p2.Y - p1.Y

  t_enter = 0.0
  t_exit = 1.0

  // Check against 4 clipping planes (left, right, bottom, top)
  FOR k FROM 0 TO 3:
    IF p[k] == 0.0: // Parallel to edge
      IF q[k] < 0.0: RETURN false // Outside and parallel
    ELSE:
      r = q[k] / p[k]
      IF p[k] < 0.0: // Entering edge
        IF r > t_exit: RETURN false
        IF r > t_enter: t_enter = r
      ELSE: // Exiting edge
        IF r < t_enter: RETURN false
        IF r < t_exit: t_exit = r

  RETURN t_enter <= t_exit