Skip to Content.
Sympa Menu

cgal-discuss - Re: [cgal-discuss] Bug in halfspaces_intersection.h - or - How to efficiently compute intersection of half-planes (continued)

Subject: CGAL users discussion list

List archive

Re: [cgal-discuss] Bug in halfspaces_intersection.h - or - How to efficiently compute intersection of half-planes (continued)


Chronological Thread 
  • From: "Sebastien Loriot (GeometryFactory)" <>
  • To:
  • Subject: Re: [cgal-discuss] Bug in halfspaces_intersection.h - or - How to efficiently compute intersection of half-planes (continued)
  • Date: Fri, 07 Nov 2014 09:55:30 +0100
  • Organization: GeometryFactory

On 11/06/2014 06:25 PM, Илья Палачев wrote:
Hi,
Thanks for answers.
I'm not the first who asks about this function, so maybe it will be
worthwhile to include halfspaces_intersection.h to official CGAL source
code?

It should be included in the next release of CGAL thanks to the work
of Jocelyn during his Google Summer of Code internship.

Sebastien.

Best regards,
Ilya Palachev
06.11.2014, 12:11, "Quentin Merigot"
<>:
Hi,

I did not try actually running your code, but there is no reason why
the convex hull of a set of points should be *strongly* convex, which
means that all points are extreme points (think of the convex hull of
the eight vertices of a cube, plus a point that lies on one of the
facets of the cube: the ninth point is not an extreme point, but
nonetheless belongs to the convex hull).

Best,
Quentin

2014-11-05 19:20 GMT+01:00 Илья Палачев
<
<mailto:>>:

Hi,
I'm using 4.3 version of CGAL. Do you advise to update it?

Ilya uses 'true' for the second parameter:

I did not change anything in Quentin's code except one that line.
BTW, I've found another issue related with this function.
After construction of the intersection, the assertion
is_strongly_convex_3 fails.
Here is my code:
static VectorXd buildStartingVector(SupportFunctionDataPtr data)
{
// Some code
/* Construct intersection of support halfspaces represented by
planes */
std::vector<Plane_3> planes = data->supportPlanes();
Polyhedron_3 intersection;
globalPCLDumper(PCL_DUMPER_LEVEL_DEBUG,
".support-planes-for-halfspaces_intersection.txt")
<< planes;
CGAL::internal::halfspaces_intersection(planes.begin(), planes.end(),
intersection, Kernel());
ASSERT(is_strongly_convex_3(intersection));
// Some code
}
I have printed planes to file and attached them to this mail. Here
is the way they were printed:
std::ostream &operator<<(std::ostream &stream,
std::vector<Plane_3> planes)
{
for (auto plane = planes.begin(); plane != planes.end(); ++plane)
stream << plane->a() << " " << plane->b() << " " << plane->c()
<< " " << plane->d() << std::endl;
return stream;
}
It is interesting that even if I remove check
"ASSERT(is_strongly_convex_3(intersection))" and if I get the hull
of its points, the assertion also fails:
Polyhedron_3 hull;
std::vector<Point_3> points;
for (auto vertex = intersection.vertices_begin();
vertex != intersection.vertices_end(); ++vertex)
{
points.push_back(vertex->point());
}
CGAL::convex_hull_3(points.begin(), points.end(), hull);
ASSERT(is_strongly_convex_3(hull));
Do you think that upgrade to CGAL 4.5 can resolve this issue?
Best regards,
Ilya
03.11.2014, 19:14, "Laurent Rineau (CGAL/GeometryFactory)"

<

<mailto:>>:

Le Monday 03 November 2014 15:23:09 Quentin Merigot a écrit :

Thank you for this bug report, it is now fixed in my
repository. However, I
must say that I am surprised that it did not work before
this change: the
numbers provided to the constructor of
Polyhedron_incremental_builder_3 are
in principle only used as estimations to reserve memory.
What version of
CGAL are you using ?

The constructor of CGAL::Polyhedron_incremental_builder has a
second parameter
that is a Boolean:

http://doc.cgal.org/latest/Polyhedron/classCGAL_1_1Polyhedron__incremental__builder__3.html#acb8216ef40323e777f57cd4656d98c83

When it is set to 'true', then that class template does extra
checks, and
display diagnostics.

Ilya uses 'true' for the second parameter:

typename CGAL::Polyhedron_incremental_builder_3<HDS>
B( hds, true);

B.begin_surface(_primal.size_of_facets(),
_primal.size_of_vertices(),
_primal.size_of_vertices());

That explains the reported behavior.

--
Laurent Rineau, PhD
R&D Engineer at GeometryFactory http://www.geometryfactory.com/
Release Manager of the CGAL Project http://www.cgal.org/


--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss





Archive powered by MHonArc 2.6.18.

Top of Page