CGAL users discussion list

["Sebastien Loriot (GeometryFactory)" <>]

On 02/27/2012 10:08 PM, Zohar wrote:
> Hi Sebastien,
>
> I read this faq already, and I'm aware that the double is less robust, but I
> thought that only for complicated algorithm, I need more than it. Frankly I
> expected the double to be able to intersect two segments with common edge.
> Otherwise I think this should be emphasized (this specific point regarding
> intersection) in the intersection / Cartesian / faq (which is too mild IMO
> on this point).
There is no magic, a computation made in double in not exact. The
problem of segments intersecting is not simple because in particular the 
four points need to be coplanar which is not possible to evaluate 
correctly in double in general.

If you want to do something using only double take segments s1 and s2, 
and consider the vector v="segment cross-product".
Compute:
* p1=intersection of s1 with the plane containing s2 and v.
* p2=intersection of s2 with the plane containing s1 and v.

Then if the distance between p1 and p2 is less than a threshold you
define according to your problem, take the midpoint of p1 and p2 as
intersection point of the segments. Note that the point will not lie
on s1 and s2 but will only almost lie on them.

This works only if the segment are not parallel.

Sebastien.

> Anyway I tried the exact_exact and it's terribly slow.
>
> See if you can help me please with another approach to my problem. I'm
> flipping edges in a polyhedron in order to optimize some function. Is there
> a robust way to check if an edge is flippable?
>
> 1. Currently I flip the edge, then check its two consecutive facets if they
> intersect other triangles in the vicinity (31). Besides being slow (due to
> the exact_exact) my mesh for some reason becomes non-manifold, and has a
> dangling ear in the middle of the triangulation. I still need to debug this,
> probably something I've done wrong when I analyzed the triangles
> intersections.
>
> 2. The next option that comes to mind is the CGAL/triangulate_polyhedron.h
> that you recommended me, which estimates the normal at some neighborhood,
> and project it into a 2D constrained triangulation. Then I can flip the edge
> and it would warn me if it intersects anything (I think). The problem with
> this is that I don't actually traverse all the possible triangulations, but
> only those that are legitimate from this projection angle.
>
>
>
>
> --
> View this message in context: 
> http://cgal-discuss.949826.n4.nabble.com/Intersecting-with-Cartesian-kerenl-tp4425392p4426070.html
> Sent from the cgal-discuss mailing list archive at Nabble.com.