bugGNU Octave - Bugs: bug #53397, Delaunay returns inconsistent...

 
 

bug #53397: Delaunay returns inconsistent (cw/ccw) orientations in 2-D (needs overhaul)

Submitter:  -X- <jsh>
Submitted:  Wed 21 Mar 2018 01:48:31 AM UTC
   
 
Category:  Octave Function Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Matlab Compatibility
Status:  Fixed Assigned to:  None
Originator Name:  Open/Closed:  * Closed
Release:  * dev Operating System:  * Any
Fixed Release:  8.1.0 Planned Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

Jump to the original submission

Mon 30 Jan 2023 02:35:08 PM UTC, comment #7: 

no comments in a few months. closing as fixed.

Nicholas Jankowski <nrjank>
Group Member
Fri 30 Sep 2022 01:49:30 PM UTC, comment #6: 

noting arb's comment #5, this is now actually fairly trivial to implement since now that the bug #60818 patch made simplex checking for all dimensionalities consistently calculate the determinant(volume). can conditionally flip nodes 2 and 3 to change sign of determinant.  checking against matlab, for many cases where delaunay produces the same simplexes, the ordering is now identical.  the only one that seems to ignore this is the trivial 1D case where matlab allows negative oriented vectors in the output.

implemented with addition of the following to the end of the function:

if ((dim > 1) && any (negvol = (vol (!idx) < 0)))
  T(negvol, [2, 3]) = T(negvol, [3, 2]);
endif


(could add a dim==1 path in there where it switches 1 and 2, but i don't think it's necessary. easy enough to add later if anyone objects.)

added a couple BISTs for 2d and 3d.  updated the NEWS paragraph about delaunayn improvement with this bit.  pushed to default as
https://hg.savannah.gnu.org/hgweb/octave/rev/8b75954a4670
marking as Ready for Test.

Nicholas Jankowski <nrjank>
Group Member
Sat 19 Feb 2022 09:45:41 PM UTC, comment #5: 

The proposed m-code solution in the original submission is still valid, and is fully vectorized, so no urgent need to go to c++? We are calculating the cross product already anyway. (wasn't the case at the time when this bug was submitted)

Could be as simple as this (untested)


diff -r 753e48aa488c scripts/geometry/delaunayn.m
--- a/scripts/geometry/delaunayn.m      Sat Feb 19 13:14:44 2022 -0500
+++ b/scripts/geometry/delaunayn.m      Sat Feb 19 22:41:37 2022 +0100
@@ -110,6 +110,8 @@
     det = cross (p12, p23, 2);
     idx = abs (det (:,3) ./ sqrt (sumsq (p12, 2))) < tol & ...
           abs (det (:,3) ./ sqrt (sumsq (p23, 2))) < tol;
+    is_clockwise = det(:,3) > 0;
+    T(is_clockwise,2:3) =  T(is_clockwise,[3,2]);
   else
     ## FIXME: Vectorize this for loop or convert delaunayn to .oct function
     idx = [];


A.R. Burgers <arb>
Mon 30 Apr 2018 03:15:01 PM UTC, comment #4: 

The QHull FAQ has this question and answer:


When I compute a plane equation from a facet, I sometimes get an outward-pointing normal and sometimes an inward-pointing normal

    Qhull orients simplicial facets, and prints oriented output for 'i', 'Ft', and other options. The orientation depends on both the vertex order and the flag facet->toporient.

    Qhull does not orient non-simplicial facets. Instead it orients the facet's ridges. These are printed with the 'Qt' and 'Ft' option. The facet's hyperplane is oriented.


So, some combination of options to QHull + post-processing is probably required.

Rik <rik5>
Group administrator
Mon 30 Apr 2018 03:07:57 PM UTC, comment #3: 

This probably is part of a bigger project.  The implementation of Delaunay is currently split between the QHull library, the _delaunayn_.cc C++ file, and delauanayn.m file.

For performance reasons, Octave should delegate as much as possible to QHull.  It is possible that Octave is simply not giving the correct option to the QHull API in order to get all clockwise or all counter-clockwise facets.  Or it may be that Matlab has the same problem and that they implement a post-processing step after calling QHull in which they weed out zero-volume facets and re-order all facets to a common direction.

In any case, it would be better for that routine to be done in C++ where for loops are cheap, rather than in an m-file where they are expensive.

Marking the bug as confirmed, but also adding to the summary that this requires an overhaul of how Octave implements delauanay.

Rik <rik5>
Group administrator
Fri 23 Mar 2018 08:55:39 AM UTC, comment #2: 
-X- <jsh>
Thu 22 Mar 2018 12:50:26 AM UTC, comment #1: 

Hi, it seems that this is a duplication of bug #46341 ?

Anonymous
Wed 21 Mar 2018 01:48:31 AM UTC, original submission:  

In Octave the delaunay/delaunayn function calls returns inconsistent (both clockwise and counter-clockwise) orientations in 2d, while Matlab seems to return only counter-clockwise oriented triangulations:


p = [0 0;1 0;1 1;0 1;.5 .5]
t = delaunay( p );

d12 = p(t(:,2),:) - p(t(:,1),:);
d13 = p(t(:,3),:) - p(t(:,1),:);
a = ( d12(:,1).*d13(:,2) - d12(:,2).*d13(:,1) )/2;

is_clockwise = a<0


This can easily be fixed in post triangulation with


t(is_clockwise,2:3) =  t(is_clockwise,[3,2]);


but it could be good to make it consistent and built-in by default.



-X- <jsh>

 

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

Attach Files:
   
   
Comment:
   

No files currently attached

 

Carbon-Copy List
  • -email is unavailable- added by nrjank (Posted a comment)
  • -email is unavailable- added by arb (Posted a comment)
  • -email is unavailable- added by rik5 (Posted a comment)
  • -email is unavailable- added by jsh (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 9 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2023-01-30 nrjank StatusReady For Test Fixed
        Open/ClosedOpen Closed
        Fixed ReleaseNone 8.1.0
    2022-10-25 nrjank Dependencies- Depends on bugs #60818
    2022-09-30 nrjank StatusConfirmed Ready For Test
    2018-04-30 rik5 StatusNone Confirmed
        Release4.2.2 dev
        SummaryDelaunay returns inconsistent (cw/ccw) orientations in 2d Delaunay returns inconsistent (cw/ccw) orientations in 2-D (needs overhaul)
    2018-04-29 rik5 Dependencies- Depends on bugs #46341

    Back to the top

    Powered by Savane 3.13-d3ae.
    Corresponding source code