bugGNU Octave - Bugs: bug #64658, delaunayn - calculations with...

 
 

bug #64658: delaunayn - calculations with integer inputs removes valid simplices

Submitter:  Nicholas Jankowski <nrjank>
Submitted:  Tue 12 Sep 2023 04:26:28 PM UTC
   
 
Category:  Octave Function Severity:  2 - Minor
Priority:  5 - Normal Item Group:  Incorrect Result
Status:  Fixed Assigned to:  None
Originator Name:  Nicholas Jankowski Open/Closed:  * Closed
Release:  * 8.3.0 Operating System:  * Any
Fixed Release:  8.4.0 Planned Release:  8.4.0
* Mandatory Fields

Add a New Comment Rich Markup
   

Jump to the original submission

Fri 13 Oct 2023 07:19:08 PM UTC, comment #8: 

No problems reported in a month. Closing as fixed.

Arun Giridhar <arungiridhar>
Group Member
Wed 13 Sep 2023 02:30:52 PM UTC, comment #7: 

I pushed a followup to also emit a warning for negative integers with large magnitude:
https://hg.savannah.gnu.org/hgweb/octave/rev/0e033c4385a5

Markus Mützel <mmuetzel>
Group administrator
Wed 13 Sep 2023 02:29:49 AM UTC, comment #6: 

 i played around a bit with some large int values. the conversion didn't seem to affect the actual triangulation (i suspect __delaunayn__ might already be doing a double conversion), just the simplex checking.  I moved the type conversion after the triangulation and added the warning, and pushed that as
http://hg.savannah.gnu.org/hgweb/octave/rev/eccbf170743f

Nicholas Jankowski <nrjank>
Group Member
Tue 12 Sep 2023 07:38:42 PM UTC, comment #5: 

that's a good idea, maybe along with a TODO note to actually address the issue.

One thought, the __delaunay__ calculation seems to have no issues with int inputs. I haven't tested it for large ints, but if the conversion could cause problems, putting it after the __delaunayn__ call might be a better option. I might try to test a few cases to see if it matters.

Nicholas Jankowski <nrjank>
Group Member
Tue 12 Sep 2023 07:31:36 PM UTC, comment #4: 

Oops. I meant `any (pts(:) > flintmax ('double'))`.
But you probably figured that already.

Markus Mützel <mmuetzel>
Group administrator
Tue 12 Sep 2023 07:22:55 PM UTC, comment #3: 

Like you wrote that change could cause different issues for input larger than flintmax.
Maybe emitting a warning if `any (pts(:)) > flintmax ('double')` just before casting to double could be helpful.

Markus Mützel <mmuetzel>
Group administrator
Tue 12 Sep 2023 05:34:05 PM UTC, comment #2: 

i will note that while this fix does take care of the primary problem, it could run into issues for very large ints where conversion to double results in accuracy problems.

 matlab disallows int inputs to the delaunay functions, so it's not a compatibility concern.  we could always do the same if we wanted to avoid the potential numerical problems and complexity of dealing with it.

Nicholas Jankowski <nrjank>
Group Member
Tue 12 Sep 2023 05:23:06 PM UTC, comment #1: 

Confirmed the simplex checking math was incorrectly truncating with int point values.  Patch that converts int inputs to double before processing and adds a BIST to catch the error pushed to stable as:

http://hg.savannah.gnu.org/hgweb/octave/rev/b262966c853c

(just noticed the typo in the commit message filename, apologies)

Marking as ready for test.

Nicholas Jankowski <nrjank>
Group Member
Tue 12 Sep 2023 04:26:28 PM UTC, original submission:  

for some inputs, delaunayn is fine if the points are specified as doubles or ints:

for one simplex:

>> pts  =  [0 0 0; 0 10 0; 10 0 0; 0 0 10]
>> delaunayn(pts)
ans =

   1   3   2   4
>> delaunayn(int32(pts))
ans =

   1   3   2   4


or multiple:


>> pts  =  [0 0 0; 0 10 0; 10 0 0; 0 0 10; 5 5 5]
>> delaunayn(pts)
ans =

   5   2   3   1
   5   3   4   1
   5   4   2   1
>> delaunayn(int32(pts))
ans =

   5   2   3   1
   5   3   4   1
   5   4   2   1


but at some point, the type seems to make a difference:


>> pts = [0 0 0; 0 0 10; 0 10 0; 0 10 10; 10 0 0; 10 0 10; 10 10 0; 10 10 10; 5 5 5];

>> delaunayn(pts)
ans =

   7   5   9   1
   7   9   3   1
   6   9   5   1
   6   2   9   1
   6   9   7   5
   6   8   7   9
   4   3   9   1
   4   9   2   1
   4   7   9   3
   4   7   8   9
   4   9   6   2
   4   8   6   9

>> delaunayn(int32(pts))
ans = [](0x4)



stepping through delaunayn for the case above, both come out of the __delaunayn__ simplex calculation the same.  it seems having the pts as ints going into the volume check creates erroneous evaluations of the simplex volume, and it removes them all as 'trivial' simplexes.  recasting pts as double should be the easiest fix.

Nicholas Jankowski <nrjank>
Group Member

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach Files:
   
   
Comment:
   

No files currently attached

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by arungiridhar (Posted a comment)
  • -email is unavailable- added by mmuetzel (Posted a comment)
  • -email is unavailable- added by nrjank (Submitted the item)
  •  

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

    Only group members can vote.

     

    Follow 7 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2023-10-13 arungiridhar StatusReady For Test Fixed
        Open/ClosedOpen Closed
        Operating SystemMicrosoft Windows Any
        Fixed ReleaseNone 8.4.0
    2023-09-13 nrjank Summarydelaunay / delaunayn - sometimes return empty if inputs are of type int delaunayn - calculations with integer inputs removes valid simplices
    2023-09-12 nrjank StatusNone Ready For Test
        Planned ReleaseNone 8.4.0

    Back to the top

    Powered by Savane 3.13-0329.
    Corresponding source code