boostorg / boostorg/geometry

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

オープン
#539 コメント 9 件 リアクション 0 件 担当者 0 名 GitHub で見る
enhancement
主要言語
C++
スター
517
フォーク
232
PR マージ指標
30日以内にマージされた PR はありません

説明

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}).

コントリビューションガイド

コントリビューションガイドを開く

評価

この issue はまだ評価されていません。

新しい issue をメールで受け取る

初心者向けの GitHub issue を短くまとめたダイジェスト。