edge_crosser_test.go

Documentation: github.com/golang/geo/s2

     1  // Copyright 2017 Google Inc. All rights reserved.
     2  //
     3  // Licensed under the Apache License, Version 2.0 (the "License");
     4  // you may not use this file except in compliance with the License.
     5  // You may obtain a copy of the License at
     6  //
     7  //     http://www.apache.org/licenses/LICENSE-2.0
     8  //
     9  // Unless required by applicable law or agreed to in writing, software
    10  // distributed under the License is distributed on an "AS IS" BASIS,
    11  // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    12  // See the License for the specific language governing permissions and
    13  // limitations under the License.
    14  
    15  package s2
    16  
    17  import (
    18  	"fmt"
    19  	"math"
    20  	"testing"
    21  
    22  	"github.com/golang/geo/r3"
    23  )
    24  
    25  func TestEdgeCrosserCrossings(t *testing.T) {
    26  	na1 := math.Nextafter(1, 0)
    27  	na2 := math.Nextafter(1, 2)
    28  
    29  	tests := []struct {
    30  		msg          string
    31  		a, b, c, d   Point
    32  		robust       Crossing
    33  		edgeOrVertex bool
    34  	}{
    35  		{
    36  			msg:          "two regular edges that cross",
    37  			a:            Point{r3.Vector{1, 2, 1}},
    38  			b:            Point{r3.Vector{1, -3, 0.5}},
    39  			c:            Point{r3.Vector{1, -0.5, -3}},
    40  			d:            Point{r3.Vector{0.1, 0.5, 3}},
    41  			robust:       Cross,
    42  			edgeOrVertex: true,
    43  		},
    44  		{
    45  			msg:          "two regular edges that intersect antipodal points",
    46  			a:            Point{r3.Vector{1, 2, 1}},
    47  			b:            Point{r3.Vector{1, -3, 0.5}},
    48  			c:            Point{r3.Vector{-1, 0.5, 3}},
    49  			d:            Point{r3.Vector{-0.1, -0.5, -3}},
    50  			robust:       DoNotCross,
    51  			edgeOrVertex: false,
    52  		},
    53  		{
    54  			msg:          "two edges on the same great circle that start at antipodal points",
    55  			a:            Point{r3.Vector{0, 0, -1}},
    56  			b:            Point{r3.Vector{0, 1, 0}},
    57  			c:            Point{r3.Vector{0, 0, 1}},
    58  			d:            Point{r3.Vector{0, 1, 1}},
    59  			robust:       DoNotCross,
    60  			edgeOrVertex: false,
    61  		},
    62  		{
    63  			msg:          "two edges that cross where one vertex is the OriginPoint",
    64  			a:            Point{r3.Vector{1, 0, 0}},
    65  			b:            OriginPoint(),
    66  			c:            Point{r3.Vector{1, -0.1, 1}},
    67  			d:            Point{r3.Vector{1, 1, -0.1}},
    68  			robust:       Cross,
    69  			edgeOrVertex: true,
    70  		},
    71  		{
    72  			msg:          "two edges that intersect antipodal points where one vertex is the OriginPoint",
    73  			a:            Point{r3.Vector{1, 0, 0}},
    74  			b:            OriginPoint(),
    75  			c:            Point{r3.Vector{1, 0.1, -1}},
    76  			d:            Point{r3.Vector{1, 1, -0.1}},
    77  			robust:       DoNotCross,
    78  			edgeOrVertex: false,
    79  		},
    80  		{
    81  			msg:          "two edges that cross antipodal points",
    82  			a:            Point{r3.Vector{1, 0, 0}},
    83  			b:            Point{r3.Vector{0, 1, 0}},
    84  			c:            Point{r3.Vector{0, 0, -1}},
    85  			d:            Point{r3.Vector{-1, -1, 1}},
    86  			robust:       DoNotCross,
    87  			edgeOrVertex: false,
    88  		},
    89  		{
    90  			// The Ortho() direction is (-4,0,2) and edge CD
    91  			// is further CCW around (2,3,4) than AB.
    92  			msg:          "two edges that share an endpoint",
    93  			a:            Point{r3.Vector{2, 3, 4}},
    94  			b:            Point{r3.Vector{-1, 2, 5}},
    95  			c:            Point{r3.Vector{7, -2, 3}},
    96  			d:            Point{r3.Vector{2, 3, 4}},
    97  			robust:       MaybeCross,
    98  			edgeOrVertex: false,
    99  		},
   100  		{
   101  			// The edge AB is approximately in the x=y plane, while CD is approximately
   102  			// perpendicular to it and ends exactly at the x=y plane.
   103  			msg:          "two edges that barely cross near the middle of one edge",
   104  			a:            Point{r3.Vector{1, 1, 1}},
   105  			b:            Point{r3.Vector{1, na1, -1}},
   106  			c:            Point{r3.Vector{11, -12, -1}},
   107  			d:            Point{r3.Vector{10, 10, 1}},
   108  			robust:       Cross,
   109  			edgeOrVertex: true,
   110  		},
   111  		{
   112  			msg:          "two edges that barely cross near the middle separated by a distance of about 1e-15",
   113  			a:            Point{r3.Vector{1, 1, 1}},
   114  			b:            Point{r3.Vector{1, na2, -1}},
   115  			c:            Point{r3.Vector{1, -1, 0}},
   116  			d:            Point{r3.Vector{1, 1, 0}},
   117  			robust:       DoNotCross,
   118  			edgeOrVertex: false,
   119  		},
   120  		{
   121  			// This example cannot be handled using regular double-precision
   122  			// arithmetic due to floating-point underflow.
   123  			msg:          "two edges that barely cross each other near the end of both edges",
   124  			a:            Point{r3.Vector{0, 0, 1}},
   125  			b:            Point{r3.Vector{2, -1e-323, 1}},
   126  			c:            Point{r3.Vector{1, -1, 1}},
   127  			d:            Point{r3.Vector{1e-323, 0, 1}},
   128  			robust:       Cross,
   129  			edgeOrVertex: true,
   130  		},
   131  		{
   132  			msg:          "two edges that barely cross each other near the end separated by a distance of about 1e-640",
   133  			a:            Point{r3.Vector{0, 0, 1}},
   134  			b:            Point{r3.Vector{2, 1e-323, 1}},
   135  			c:            Point{r3.Vector{1, -1, 1}},
   136  			d:            Point{r3.Vector{1e-323, 0, 1}},
   137  			robust:       DoNotCross,
   138  			edgeOrVertex: false,
   139  		},
   140  		{
   141  			msg: "two edges that barely cross each other near the middle of one edge",
   142  			// Computing the exact determinant of some of the triangles in this test
   143  			// requires more than 2000 bits of precision.
   144  			a:            Point{r3.Vector{1, -1e-323, -1e-323}},
   145  			b:            Point{r3.Vector{1e-323, 1, 1e-323}},
   146  			c:            Point{r3.Vector{1, -1, 1e-323}},
   147  			d:            Point{r3.Vector{1, 1, 0}},
   148  			robust:       Cross,
   149  			edgeOrVertex: true,
   150  		},
   151  		{
   152  			msg:          "two edges that barely cross each other near the middle separated by a distance of about 1e-640",
   153  			a:            Point{r3.Vector{1, 1e-323, -1e-323}},
   154  			b:            Point{r3.Vector{-1e-323, 1, 1e-323}},
   155  			c:            Point{r3.Vector{1, -1, 1e-323}},
   156  			d:            Point{r3.Vector{1, 1, 0}},
   157  			robust:       DoNotCross,
   158  			edgeOrVertex: false,
   159  		},
   160  	}
   161  
   162  	for _, test := range tests {
   163  		// just normalize them once
   164  		a := Point{test.a.Normalize()}
   165  		b := Point{test.b.Normalize()}
   166  		c := Point{test.c.Normalize()}
   167  		d := Point{test.d.Normalize()}
   168  		testCrossing(t, test.msg, a, b, c, d, test.robust, test.edgeOrVertex)
   169  		testCrossing(t, test.msg, b, a, c, d, test.robust, test.edgeOrVertex)
   170  		testCrossing(t, test.msg, a, b, d, c, test.robust, test.edgeOrVertex)
   171  		testCrossing(t, test.msg, b, a, d, c, test.robust, test.edgeOrVertex)
   172  
   173  		// test degenerate cases
   174  		testCrossing(t, test.msg, a, a, c, d, DoNotCross, false)
   175  		testCrossing(t, test.msg, a, b, c, c, DoNotCross, false)
   176  		testCrossing(t, test.msg, a, a, c, c, DoNotCross, false)
   177  
   178  		testCrossing(t, test.msg, a, b, a, b, MaybeCross, true)
   179  		testCrossing(t, test.msg, c, d, a, b, test.robust, test.edgeOrVertex != (test.robust == MaybeCross))
   180  	}
   181  }
   182  
   183  func testCrossing(t *testing.T, msg string, a, b, c, d Point, robust Crossing, edgeOrVertex bool) {
   184  	// Modify the expected result if two vertices from different edges match.
   185  	if a == c || a == d || b == c || b == d {
   186  		robust = MaybeCross
   187  	}
   188  
   189  	input := fmt.Sprintf("%s: a: %v, b: %v, c: %v, d: %v", msg, a, b, c, d)
   190  
   191  	crosser := NewChainEdgeCrosser(a, b, c)
   192  	if got, want := crosser.ChainCrossingSign(d), robust; got != want {
   193  		t.Errorf("%v, ChainCrossingSign(d) = %d, want %d", input, got, want)
   194  	}
   195  	if got, want := crosser.ChainCrossingSign(c), robust; got != want {
   196  		t.Errorf("%v, ChainCrossingSign(c) = %d, want %d", input, got, want)
   197  	}
   198  	if got, want := crosser.CrossingSign(d, c), robust; got != want {
   199  		t.Errorf("%v, CrossingSign(d, c) = %d, want %d", input, got, want)
   200  	}
   201  	if got, want := crosser.CrossingSign(c, d), robust; got != want {
   202  		t.Errorf("%v, CrossingSign(c, d) = %d, want %d", input, got, want)
   203  	}
   204  
   205  	crosser.RestartAt(c)
   206  	if got, want := crosser.EdgeOrVertexChainCrossing(d), edgeOrVertex; got != want {
   207  		t.Errorf("%v, EdgeOrVertexChainCrossing(d) = %t, want %t", input, got, want)
   208  	}
   209  	if got, want := crosser.EdgeOrVertexChainCrossing(c), edgeOrVertex; got != want {
   210  		t.Errorf("%v, EdgeOrVertexChainCrossing(c) = %t, want %t", input, got, want)
   211  	}
   212  	if got, want := crosser.EdgeOrVertexCrossing(d, c), edgeOrVertex; got != want {
   213  		t.Errorf("%v, EdgeOrVertexCrossing(d, c) = %t, want %t", input, got, want)
   214  	}
   215  	if got, want := crosser.EdgeOrVertexCrossing(c, d), edgeOrVertex; got != want {
   216  		t.Errorf("%v, EdgeOrVertexCrossing(c, d) = %t, want %t", input, got, want)
   217  	}
   218  }
   219  
   220  // TODO(roberts): Differences from C++:
   221  // TestEdgeCrosserCollinearEdgesThatDontTouch
   222  // TestEdgeCrosserCoincidentZeroLengthEdgesThatDontTouch
   223
View as plain text