Invalid turns generation (detected as inconsistency in set and relational operations).
- 主要言語
- C++
- スター
- 517
- フォーク
- 232
- PR マージ指標
- 30日以内にマージされた PR はありません
説明
@barendgehrels I've noticed that some operations became inconsistent after recent changes in set operations (with VS2015, msvc-14.0, x86). Consider:
```
red = POLYGON((5 0,7 10,0 15,10 15,15 25,20 15,30 15,22 10,25 0,15 5,5 0))
green = POLYGON((15 0,17 10,10 15,20 15,25 25,30 15,40 15,32 10,35 0,25 5,15 0))
blue = MULTIPOLYGON(((10 15,15 25,20 15,10 15)),((10 15,17 10,15.90909090909091 4.545454545454546,15 5,5 0,7 10,0 15,10 15)),((23.69565217391304 4.347826086956522,25 0,20 2.5,23.69565217391304 4.347826086956522)))
```

where:
```
bg::difference(red, green, blue)
```
`blue` should therefore be within `red`:
```
assert(bg::within(blue, red) == true)
```
but it is not. Here it is how it looks like with turns calculated internally in `within` or `relation`:

The lower right `blue` triangle has the following points:
```
{23.695652173913043, 4.3478260869565215}
{25.000000000000000, 0.00000000000000000}
{20.000000000000000, 2.5000000000000000}
{23.695652173913043, 4.3478260869565215}
```
the lower right arm of the `red` star is formed from the points:
```
{22.000000000000000, 10.000000000000000}
{25.000000000000000, 0.00000000000000000}
{15.000000000000000, 5.0000000000000000}
```
and the corresponding turns are:
```
0: touch u/i at {25.000000000000000, 0.00000000000000000}
1: crosses i/u at {20.000001500000678, 2.5000007500003396}
2: crosses u/i at {23.695651652173520, 4.3478258260867602}
```
(note: turns indexes are different than in `within`)
So it looks like at `{25, 0}` (turn 0) the blue triangle goes outside the red and then crosses it from the outside at `{20.000001500000678, 2.5000007500003396}` (turn 1), goes inside and then at `{23.695651652173520, 4.3478258260867602}` (turn 2) outside again. Also the coordinates looks consistent with topology since `{20.000001500000678, 2.5000007500003396}` is above and on the right of `{20.000000000000000, 2.5000000000000000}` and `{23.695651652173520, 4.3478258260867602}` is below and on the left of `{23.695652173913043, 4.3478260869565215}`.
However this should not be the case. All turns for this triangle should be detected as lying on the edges. And this is not some numerical floating point error. Consider the `POINT(20.0 2.5)`. It's exactly in the half of the `SEGMENT(25 0, 15 5)` but the turn point calculated for this point is `{20.000001500000678, 2.5000007500003396}`. The error is huge.
Btw, turns in relate are calculated like this: https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/algorithms/detail/relate/areal_areal.hpp#L225
Or am I missing something?
EDIT:
Is this a bug?
Should turns be generated in a different way now?
Is this low accuracy expected?
Note that if such low accuracy was expected (e.g. was a side effect of your changes) we would have to for instance compare all of the points (for equality) in the library WRT to this accuracy.
コントリビューションガイド
評価
この issue はまだ評価されていません。