Best way to determine pad pitch

Hi,

Yes, it is true that combining 27,000 objects with themselves in the general case would be prohibitely expensive. For many common operations however, the Ravel optimization engine recognizes and optimizes the evaluation such that the full combination never has to be formed. One such operation is measuring distance. The common pattern of combining two relations and selecting tuples where the distance between objects of the two input relations is lower than a given value is optimized with a sophisticated tree algorithm. This tree algorithm builds a spatial tree, essentially dynamically creating regions based on object proximity, where small regions of objects are arranged into larger regions in a tree structure. For this reason it is likely counterproductive to attempt to create your own regions, since it does not allow the Ravel optimization to work on the whole set of objects.

I do not have your testcase here, so I created a grid of points, 165x165 = 27,225, evenly separated. Combining these points with themselves, selecting pairs closer to each other than 11 (the pitch was 10), took roughly three minutes on my laptop, so not super fast but manageable. Here is a trace with RAVEL_TRACE_OPTIMIZATION turned on; You can see that thanks to the spatial tree algorithm it only has to do 243,049 direct object comparisons out of a possible 741,200,625 if all objects were pairwise compared:

(03:12:21) |(define neighbors (select (p1 p2) (combine coordinate coordinate) (and (ordered? p1 p2) (lessp (distance p1 p2) 11))))
(03:12:21) ||(select (p1 p2) (combine coordinate coordinate) (and (ordered? p1 p2) (lessp (distance p1 p2) 11)))
(03:12:21) >>> (select (p1 p2) (combine coordinate coordinate) (and (ordered? p1 p2) (lessp (distance p1 p2) 11))) => (select_combine (p1 p2) (and (ordered? p1 p2) (lessp (distance p1 p2) 11)) (coordinate coordinate))
(03:12:21) >>> Spatial box tree optimization:
(03:12:21) >>> Building tree for p1/point in ((p1 point))
(03:12:33) >>> # elements: 27225
(03:12:33) >>> node size: 16
(03:12:33) >>> height: 5
(03:12:33) >>> Reusing identical tree
(03:15:27) >>> # of comparisons: 243049/741200625 = 0.03%
(03:15:27)
(03:15:27) ||select --> #<relation:54120:(point point)>
(03:15:27) |define --> neighbors

Now, the question of what to use for a cut-off value is tricky in the general case, but if your objects are not randomly distributed but rather arranged in a grid, you could e.g. find the two smallest x coordinates and use the difference as a starting point:

(define xcoordinate
  (transform (p) bumppad
    ((xcoordinate (center p)))))

(define x1st
  (CHOOSE_MIN xcoordinate IDENTITY))

(define x2nd
  (CHOOSE_MIN (difference xcoordinate x1st) IDENTITY))

(define cutoff
  (transform (x1st x2nd) (combine x1st x2nd)
    ((difference x2nd x1st))))

Regards,

Björn

Hi,

Yes, it is true that combining 27,000 objects with themselves in the general case would be prohibitely expensive. For many common operations however, the Ravel optimization engine recognizes and optimizes the evaluation such that the full combination never has to be formed. One such operation is measuring distance. The common pattern of combining two relations and selecting tuples where the distance between objects of the two input relations is lower than a given value is optimized with a sophisticated tree algorithm. This tree algorithm builds a spatial tree, essentially dynamically creating regions based on object proximity, where small regions of objects are arranged into larger regions in a tree structure. For this reason it is likely counterproductive to attempt to create your own regions, since it does not allow the Ravel optimization to work on the whole set of objects.

I do not have your testcase here, so I created a grid of points, 165x165 = 27,225, evenly separated. Combining these points with themselves, selecting pairs closer to each other than 11 (the pitch was 10), took roughly three minutes on my laptop, so not super fast but manageable. Here is a trace with RAVEL_TRACE_OPTIMIZATION turned on; You can see that thanks to the spatial tree algorithm it only has to do 243,049 direct object comparisons out of a possible 741,200,625 if all objects were pairwise compared:

(03:12:21) |(define neighbors (select (p1 p2) (combine coordinate coordinate) (and (ordered? p1 p2) (lessp (distance p1 p2) 11))))
(03:12:21) ||(select (p1 p2) (combine coordinate coordinate) (and (ordered? p1 p2) (lessp (distance p1 p2) 11)))
(03:12:21) >>> (select (p1 p2) (combine coordinate coordinate) (and (ordered? p1 p2) (lessp (distance p1 p2) 11))) => (select_combine (p1 p2) (and (ordered? p1 p2) (lessp (distance p1 p2) 11)) (coordinate coordinate))
(03:12:21) >>> Spatial box tree optimization:
(03:12:21) >>> Building tree for p1/point in ((p1 point))
(03:12:33) >>> # elements: 27225
(03:12:33) >>> node size: 16
(03:12:33) >>> height: 5
(03:12:33) >>> Reusing identical tree
(03:15:27) >>> # of comparisons: 243049/741200625 = 0.03%
(03:15:27)
(03:15:27) ||select --> #<relation:54120:(point point)>
(03:15:27) |define --> neighbors

Now, the question of what to use for a cut-off value is tricky in the general case, but if your objects are not randomly distributed but rather arranged in a grid, you could e.g. find the two smallest x coordinates and use the difference as a starting point:

(define xcoordinate
  (transform (p) bumppad
    ((xcoordinate (center p)))))

(define x1st
  (CHOOSE_MIN xcoordinate IDENTITY))

(define x2nd
  (CHOOSE_MIN (difference xcoordinate x1st) IDENTITY))

(define cutoff
  (transform (x1st x2nd) (combine x1st x2nd)
    ((difference x2nd x1st))))

Regards,

Björn