boostorg / boostorg/geometry

Proposal: Adding the specializations difference<box,box,collection<box>>, sym_difference<box,box,collection<box>>

Open
#539 9 comments 0 reactions 0 assignees View on GitHub
enhancement
Dominant language
C++
Stars
517
Forks
232
PR merge metrics
No merged PRs in 30d

Description

I want to propose adding the specializations difference> and sym_difference> to the geometric set operations difference and sym_difference. It is easy to see that the set difference between two boxes is not generally a box but instead may require multiple boxes to cover the resulting set.

### Example:
Consider the 2D-boxes A=box(point(0,0),point(10,10)) and B=box(point(0,0),point(5,5)). For difference(A,B,result), the result would contain at least two boxes, a valid result consisting of as few boxes as possible and without overlapping boxes would be {box(point(5,0),point(10,5)),box(point(0,5),point(10,10))}.

### Rationale
To justify the proposal, I'll briefly outline some problems in which I needed the set difference between boxes as a collection of boxes.
I use Boost.Geometry for a number of problems that involve optimizing placements of boxes (2D and 3D) under a variety of constraints. The need for difference> came up multiple times, here are a few examples of applications:

1. I have a vector V of n-dimensional boxes and need (as part of a larger problem) to compute the complement of their union as a vector of boxes, so I get a large boxes B that covers the whole space, compute B minus V[0], then the difference of the resulting boxes and V[1] and so on (of course, rtree helps to do that only for boxes that overlap with V[1], V[2], and so on).

2. I need (as part of a much larger problem) to know whom's shadows would touch a given if the y-axis would be a light source, i.e.: for rectangles 1,2,3, given as ((0,2),(1,4)), ((2,1),(3,5)), ((4,3),(5,4)), the rectangle 4 ((6,0),(7,6)) would be touched by the light of the y-axis (for y=0 to 1 and y=5 to 6), by the shadow of 2 (for y=1 to 3 and y=4 to 5) and by the shadow of 3 (for y=3 to 4)). The shadow of 1 is completely blocked off by 2. The solution involves a sweep line that is parallel to the y-axis, moves in x-direction and holds the projection (as 1D-boxes, i.e. intervals) unto itself of every box it passes through and computes the difference of existing projections and the next projection of the upcoming box (which reflects the shadow of the old boxes being blocked off by the upcoming ones).
Variations of this problem (including a 3D version) keep coming up in my work, all requiring the difference operation.

It would also go a small step towards closing this one: https://github.com/boostorg/geometry/issues/483

### Implementation

I have a draft implementation for "difference" here: https://github.com/tinko92/boost_geometry_difference_demo/blob/master/boost_difference.patch

It computes the difference of two boxes, regardless of dimension as a collection of at most 2*d boxes where d is the dimension of the point type.

Based on difference it would be trivial to add sym_difference (which is just the union of A minus B and B minus A) and union_ (if the user wants the union of two boxes as a collection of non-overlapping boxes, like in the proposed implementation of difference, we could compute union_ as the union of A minus B and {B}).

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.