bugGNU Octave - Bugs: bug #62079, delaunayn function returns...

 
 

bug #62079: delaunayn function returns incorrect vertex order

Submitter:  None
Submitted:  Fri 18 Feb 2022 04:10:48 PM UTC
   
 
Category:  Octave Function Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Inaccurate Result
Status:  Duplicate Assigned to:  None
Originator Name:  Trevor B Originator Email:  -email is unavailable-
Open/Closed:  * Closed Release:  * dev
Operating System:  * Any Fixed Release:  None
Planned Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

Fri 18 Feb 2022 06:39:32 PM UTC, comment #3: 

right, hadn't seen that one.  that seems to cover this bug report pretty completely.  closing this one as a duplicate, and further discussion can happen over there.

Nicholas Jankowski <nrjank>
Group Member
Fri 18 Feb 2022 06:05:20 PM UTC, comment #2: 

See also bug #53397

A.R. Burgers <arb>
Fri 18 Feb 2022 05:23:29 PM UTC, comment #1: 

there's been some work on delaunayn, see bug #60818, but that is mostly focused on sliver removal consistency and performace improvement, and it's sort of stalled out. However I did notice in the working files, especially when trying to write compatibility tests, that node and triangle ordering can differ significantly.

Most of the actual work is performed by _delaunayn_.cc, which calls the QHull library functions. My understanding is that matlab also uses qhull, so it's unclear where in there Octave makes choices that result in different output node order. It's entirely possible there's a handedness error that could be corrected.  If it's something your're able to examine, without needing to clone the entire repository a recent revision for that file's source can be found at:

http://hg.savannah.gnu.org/hgweb/octave/file/e4428d01f863/libinterp/dldfcn/__delaunayn__.cc

Nicholas Jankowski <nrjank>
Group Member
Fri 18 Feb 2022 04:10:48 PM UTC, original submission:  

If I define a vector of points as

    P = [-2.6105e-01,3.5877e-01; 2.6105e-01, 3.5877e-01; -1.2939e-09, -4.4029e-01];

I can use the delaunayn(P) command to obtain the triangulation that forms from those points. The result I get is [1, 2, 3]. This is wrong because of the direction of the vertices; for a positive (right hand rule in 2D) triangle, the node order should be [1,3,2]. The result [1,3,2] is returned by a similar software ‘Matlab’. The issue with the order of these vertices is that it can cause ill-defined behavior when porting some scripts to Octave.

Anonymous

 

(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 arb (Posted a comment)
  • -email is unavailable- added by nrjank (Posted a comment)
  • -email is unavailable- added by None (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 5 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2022-02-18 nrjank StatusConfirmed Duplicate
        Open/ClosedOpen Closed
    2022-02-18 nrjank StatusNone Confirmed
        Release6.4.0 dev
        Operating SystemGNU/Linux Any

    Back to the top

    Powered by Savane 3.13-4b48.
    Corresponding source code