MergeIdx returned in mergeHulls is -1.

[duser5]

Hi,

I am seeing an error in certain cases in mergeHulls. Upon debugging I see the mergeIdx returned by bsearch is -1.

Uncaught TypeError: Cannot read property 'upperIds' of undefined at mergeHulls (dbs.html:1346) at monotoneTriangulate (dbs.html:1401) at cdt2d (dbs.html:883)

I am working around this right now by avoiding the merge step if the mergeIdx<1. Would you recommend this?

[mikolalysenko]

Can you post an input?

[jbghoul]

As said in binary-search-bound readme.md : https://github.com/mikolalysenko/binary-search-bounds#notes

Assumes the array is sorted as would be the case if you called Array.sort(cmp) on it

When a compare function is given, it assumes that the array has been sorted before.

In monotone.js the hulls array is not sorted with findSplit before using bseach methods

Here is an example :

compareFn = (o1, o2) => o1.a - o2.a
// output: (o1, o2) => o1.a - o2.a
bsearch.eq([{a:1}, {a: 0}, {a: 2}], {a:1}, compareFn)
// output: -1
bsearch.eq([{a:1}, {a: 0}, {a: 2}].sort(compareFn), {a:1}, compareFn)
// output: 1

[jbghoul]

Here is a sample of a shape that causes the error

'use strict'

var tape = require('tape')
var orient = require('robust-orientation')
var monotone = require('../lib/monotone')
var verifyTriangulation = require('./verify-triangulation')

tape('monotone triangulation - polygon', function(t) {

  var points = [
      // 0-7
      [1877455680,-3185714800],
      [1793030210,-2952356290],
      [1356548000,-3110268710],
      [1263368310,-3143978590],
      [1356547570,-3110267800],
      [933170110,-2221968040],
      [864435730,-2306967300],
      [1370649970,-3369069150],
      // 8-13
      [1264056890,-3144261190],
      [1356292240,-3110891890],
      [1356292670,-3110892800],
      [1792730130,-2952996580],
      [1876815390,-3185414720],
      [1370906240,-3368444710],
  ];

  var edges = [
    //  0-7
    [0,1],
    [1,2],
    [2,3],
    [3,4],
    [4,5],
    [5,6],
    [6,7],
    [7,0],
    // 8-13
    [8,9],
    [9,10],
    [10,11],
    [11,12],
    [12,13],
    [13,8],
  ];

  verifyTriangulation(t, points, edges , monotone(points, edges));

  t.end()
})

[unageek]

@jbghoul Your sample looks erroneous. Some pairs of segments have intersections in their interior; edges[2] and edges[6] intersect at point (488631877382598139980470/386769141387059, -1215993899479476882645450/386769141387059), and edges[3] and edges[6] intersect at point (244315947010920392397170/193384577278801, -607996970443686806823400/193384577278801).