bugGNU Octave - Bugs: bug #34604, Trivial delaunay throws qhull error

 
 

bug #34604: Trivial delaunay throws qhull error

Submitted by:  Ben Abbott <bpabbott>
Submitted on:  Thu 20 Oct 2011 03:21:38 PM UTC  
 
Category: NoneSeverity: 4 - Important
Priority: 5 - NormalItem Group: Incorrect Result
Status: FixedAssigned to: None
Originator Name: Ben AbbottOpen/Closed: Closed
Release: devOperating System: Any

Add a New Comment(Rich Markup)
   

You are not logged in

Please log in, so followups can be emailed to you.

 

(Jump to the original submission Jump to the original submission)

Tue 25 Oct 2011 05:40:41 PM UTC, comment #11:

Rik,

Thanks for taking care of this. I'm still working on my patch idea.

Ben Abbott <bpabbott>
Project Member
Tue 25 Oct 2011 05:28:45 PM UTC, comment #10:

Ben, I checked in a patch that fixes your problem by adding 'Qz' to the list of Qhull options for low-dimensional data. From all that I understand about Qhull this will not a concern. Just to be sure, I ran multiple sets of random vectors through Qhull with and without the Qz option and the Delaunay triangulation is always the same.

The changeset is here (http://hg.savannah.gnu.org/hgweb/octave/rev/7ff0bdc3dc4c)

Rik <rik5>
Project Administrator
Fri 21 Oct 2011 06:32:10 PM UTC, comment #9:

Rik,

I've been looking at improving the compatibility of the patch() command. My thought was to mesh patches into triangles to allow them to have interpolated colors. I was going to use delaunay() to mesh convex patches.

I don't expect to finish this effort this week.

Please include the addition of "Qz" to the defaults when you push your changeset.

I don't know enough about the internals of qhull to have an opinion on whether or not not "Qz" can cause problems in some cases. Thus, I'm inclined to be conservative and only include it when precision error result (as jwe suggested). Is that possible?

Ben Abbott <bpabbott>
Project Member
Fri 21 Oct 2011 05:44:31 PM UTC, comment #8:

Is there any possible harm in adding Qz by default, or should it only be added if there is a failure without it?

John W. Eaton <jwe>
Project Administrator
Fri 21 Oct 2011 05:32:35 PM UTC, comment #7:

Yes to adding 'Qz' to the defaults. I am working on what has grown to be an enormous patch for all the geometry functions. Octave was not cleaning up memory correctly which was why 'clear all' was needed. I've changed a bunch of other things to clean up the code as well. I expect by the end of the weekend to check something in.

Rik <rik5>
Project Administrator
Fri 21 Oct 2011 03:34:02 AM UTC, comment #6:

Rik,

What do you think, should the "Qz" option be added by default?

Ben Abbott <bpabbott>
Project Member
Thu 20 Oct 2011 08:23:45 PM UTC, comment #5:

The error message does appear to be accurate. The center point of the square is exactly on a facet line (the diagonal from the corners of the square). The warning message suggests using two options--both of which work for me.

The first option is 'QJ' which "Joggles" the input points. This does eliminate the exact co-planarity. However, its use isn't particularly recommended because it reduces the accuracy of the triangulation.

The second option is 'Qz' which adds a point at infinity. This option seems to work well.

Perhaps this option should always be added to low-dimensional data? The relevant code is in src/__delaunayn__.cc:89.

Interestingly, I tried the same trial figure in three dimensions, i.e., a unit cube and delaunay3 fails in exactly the same way. By adding 'Qz' I can get delaunay3 to pass as well.

Rik <rik5>
Project Administrator
Thu 20 Oct 2011 07:10:07 PM UTC, comment #4:

opps, I had a typo that swallowed the rest of my comment.

Ben Abbott <bpabbott>
Project Member
Thu 20 Oct 2011 07:08:50 PM UTC, comment #3:

In case it might give some hint as to what is wrong, I Just noticed that adding a point to the interior resolves the problem.

Ben Abbott <bpabbott>
Project Member
Thu 20 Oct 2011 06:58:22 PM UTC, comment #2:

Thanks Rik.

I've changed the OS field to "any".

Ben Abbott <bpabbott>
Project Member
Thu 20 Oct 2011 06:55:11 PM UTC, comment #1:

The same error message appears for a Linux build (Kubuntu 10.04) and qhull version 2009.1-1. The same problems with further delaunay operations are also confirmed. This is with a development tip from 10/20/2011.

Rik <rik5>
Project Administrator
Thu 20 Oct 2011 03:21:38 PM UTC, original submission:

Matlab gives,

After this error, the dellunay test also fails.

If I run "clear all" then the test passes.

This may be a problem local to building on MacOS, with MacPorts, or something I am doing. I'd appreciate the effort if someone else would try the example.

Ben Abbott <bpabbott>
Project Member

 

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

Attach File(s):
   
   
Comment:
   

No files currently attached

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -unavailable- added by jwe (Posted a comment)
  • -unavailable- added by rik5 (Posted a comment)
  • -unavailable- added by bpabbott (Submitted the item)
  •  

    Do you think this task is very important?
    If so, you can click here to add your encouragement to it.
    This task has 0 encouragements so far.

    Only project members can vote.

     

    Please enter the title of George Orwell's famous dystopian book (it's a date):

     

     

    Follow 5 latest changes.

    Date Changed By Updated Field Previous Value => Replaced By
    Tue 25 Oct 2011 05:28:45 PM UTCrik5StatusIn Progress=>Fixed
      Open/ClosedOpen=>Closed
    Fri 21 Oct 2011 05:32:35 PM UTCrik5StatusConfirmed=>In Progress
    Thu 20 Oct 2011 06:58:22 PM UTCbpabbottOperating SystemMac OS=>Any
    Thu 20 Oct 2011 06:55:11 PM UTCrik5StatusNone=>Confirmed

    Back to the top


    Powered by Savane 3.1-cleanup1