Opened 3 years ago
Closed 2 years ago
#29176 closed defect (fixed)
Bug in Voronoi Diagram
Reported by: | jipilab | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-9.1 |
Component: | geometry | Keywords: | cdd, incidence matrix |
Cc: | jipilab, gh-LaisRast | Merged in: | |
Authors: | Jonathan Kliem | Reviewers: | Jean-Philippe Labbé |
Report Upstream: | N/A | Work issues: | |
Branch: | fb2d66a (Commits, GitHub, GitLab) | Commit: | fb2d66a0e71f164e9bef37922c8d544b9b270c9c |
Dependencies: | Stopgaps: |
Description (last modified by )
We fix a bug that was exposed computing an inexact Voronoi Diagram (see below).
cdd
already computes the incidence matrix, we expose it in this ticket.
When deciding whether or not a vertex lies on a hyperplane for inexact polyhedra, we allow numerical noise up to absolute value of 1e-6
. This might be a bad choice depending on the size of the polyhedron as witnessed in the following example:
sage: e = [[11582947.657000002, 5374.38, 4177.06, 1.0], [11562795.9322, 5373.62, 4168.38, 1.0]] sage: p = Polyhedron(ieqs=e); p A 3-dimensional polyhedron in RDF^3 defined as the convex hull of 1 vertex, 2 rays, 1 line sage: p.incidence_matrix() [0 0] [0 0] [0 1] [0 0]
Setting the cache of incidence matrix to the matrix that cdd
already computed for us produces the correct output:
sage: p.incidence_matrix() [1 1] [1 0] [0 1] [1 1]
This fixes the error reported here:
https://ask.sagemath.org/question/49749/voronoidiagram-returns-empty-regions/
The following should give two non-empty regions
sage: P = [[-2687.19, -2088.53], [-2686.81, -2084.19]] ....: V = VoronoiDiagram(P) ....: R = V.regions() ....: sage: R {P(-2687.19000000000, -2088.53000000000): The empty polyhedron in RDF^0, P(-2686.81000000000, -2084.19000000000): A 1-dimensional polyhedron in RDF^2 defined as the convex hull of 1 vertex and 1 ray
With this ticket we obtain:
sage: R {P(-2687.19000000000, -2088.53000000000): A 2-dimensional polyhedron in RDF^2 defined as the convex hull of 1 vertex, 1 ray, 1 line, P(-2686.81000000000, -2084.19000000000): A 2-dimensional polyhedron in RDF^2 defined as the convex hull of 1 vertex, 1 ray, 1 line}
Change History (14)
comment:1 Changed 2 years ago by
comment:2 Changed 2 years ago by
- Branch set to public/29176
- Cc jipilab gh-LaisRast added
- Commit set to 33b59112324e37dcbdab7706047e47cf9dbf5568
- Description modified (diff)
- Keywords cdd incidence matrix added
- Status changed from new to needs_review
comment:3 Changed 2 years ago by
- Reviewers set to Jean-Philippe Labbé
- Status changed from needs_review to positive_review
Thanks! Looks good to me.
comment:4 Changed 2 years ago by
Thank you.
comment:5 Changed 2 years ago by
- Status changed from positive_review to needs_work
On Python 2 Debian 9 x86_64:
********************************************************************** File "src/sage/geometry/polyhedron/backend_cdd.py", line 231, in sage.geometry.polyhedron.backend_cdd.Polyhedron_cdd._init_from_cdd_output Failed example: R Expected: {P(-2686.81000000000, -2084.19000000000): A 2-dimensional polyhedron in RDF^2 defined as the convex hull of 1 vertex, 1 ray, 1 line, P(-2687.19000000000, -2088.53000000000): A 2-dimensional polyhedron in RDF^2 defined as the convex hull of 1 vertex, 1 ray, 1 line} Got: {P(-2687.19000000000, -2088.53000000000): A 2-dimensional polyhedron in RDF^2 defined as the convex hull of 1 vertex, 1 ray, 1 line, P(-2686.81000000000, -2084.19000000000): A 2-dimensional polyhedron in RDF^2 defined as the convex hull of 1 vertex, 1 ray, 1 line} ********************************************************************** 1 item had failures:
comment:6 Changed 2 years ago by
- Commit changed from 33b59112324e37dcbdab7706047e47cf9dbf5568 to 9352525b50851921f000335615e75e0f1bdd5f2e
Branch pushed to git repo; I updated commit sha1. New commits:
9352525 | fixed dictionary in python2
|
comment:7 Changed 2 years ago by
- Status changed from needs_work to needs_review
I tested this in python2:
>>> {(-2686.81000000000, -2084.19000000000): 0, (-2687.19000000000, -2088.53000000000): 0} {(-2687.19, -2088.53): 0, (-2686.81, -2084.19): 0}
So the fix should work fine.
comment:8 Changed 2 years ago by
- Status changed from needs_review to positive_review
Thanks for the quick fix.
comment:9 Changed 2 years ago by
- Branch changed from public/29176 to 9352525b50851921f000335615e75e0f1bdd5f2e
- Resolution set to fixed
- Status changed from positive_review to closed
comment:10 Changed 2 years ago by
- Commit 9352525b50851921f000335615e75e0f1bdd5f2e deleted
- Resolution fixed deleted
- Status changed from closed to new
********************************************************************** File "src/sage/geometry/polyhedron/backend_cdd.py", line 234, in sage.geometry.polyhedron.backend_cdd.Polyhedron_cdd._init_from_cdd_output Failed example: R # py2 Expected: {P(-2687.19000000000, -2088.53000000000): A 2-dimensional polyhedron in RDF^2 defined as the convex hull of 1 vertex, 1 ray, 1 line, P(-2686.81000000000, -2084.19000000000): A 2-dimensional polyhedron in RDF^2 defined as the convex hull of 1 vertex, 1 ray, 1 line} Got: {P(-2686.81000000000, -2084.19000000000): A 2-dimensional polyhedron in RDF^2 defined as the convex hull of 1 vertex, 1 ray, 1 line, P(-2687.19000000000, -2088.53000000000): A 2-dimensional polyhedron in RDF^2 defined as the convex hull of 1 vertex, 1 ray, 1 line} ********************************************************************** 1 item had failures: 1 of 10 in sage.geometry.polyhedron.backend_cdd.Polyhedron_cdd._init_from_cdd_output [46 tests, 1 failure, 0.59 s] **********************************************************************
comment:11 Changed 2 years ago by
- Branch changed from 9352525b50851921f000335615e75e0f1bdd5f2e to public/29176-reb
- Commit set to fb2d66a0e71f164e9bef37922c8d544b9b270c9c
- Status changed from new to needs_review
comment:12 Changed 2 years ago by
- Status changed from needs_review to positive_review
comment:13 Changed 2 years ago by
Thank you.
comment:14 Changed 2 years ago by
- Branch changed from public/29176-reb to fb2d66a0e71f164e9bef37922c8d544b9b270c9c
- Resolution set to fixed
- Status changed from positive_review to closed
This can and should be solved by fetching the incidences from cdd.
I will try to do so. This might get rid of a lot of numerical inconsistencies.