CGAL users discussion list

[Matthew Denno <>]

Hi Pierre,

Attached is my triangle_triangle_intersection.h (should probably be called Triangle_3_Triangle_3_intersection.h) function including my check for degenerate segments.  I still need to make it a template class, but it is going to be a few weeks until I can start looking at doing that.

Any feed back or suggestions would be appreciated.

Matt

On Thu, Aug 13, 2009 at 10:40 AM, Matthew Denno <> wrote:

Hi Pierre,

Thank you for your input.  I thought maybe there was a situation, that I couldn't think of, where one might want a degenerate segment instead of a point.  Sounds like no.

I would be happy to provide my current function.  I am not at my computer right now (not the right one anyway), but I will send it later.

The function that I wrote is a Triangle_3_Triangle_3_intersection function that utilizes the Triangle_3_Segment_3_intersection function to calculate the intersection of two triangles in 3D space.  As it is currently, my function checks for degenerate segments after the the object (segment in this case) is returned from the Triangle_3_Segment_3_intersection function.  Maybe it would be better to make a change to the Triangle_3_Segment_3_intersection function or even make_segment(), so that a degenerate segment is not returned.   I can look into how to do this based on what I have already.

I should mention that I am new to C++ programming.  The program that I am currently working on is the first C++ program that I have ever written.  I am very much still learning.  My T3_T3_intesection function is not yet based on the concept of a template, as it seems most CGAL functions are; this is my next task/step.

Sorry for the long response.

Matt

On Thu, Aug 13, 2009 at 3:55 AM, Pierre Alliez <> wrote:

dear Matthew,

the behavior was not intentional and yours is better: can you provide us with your current function?

thank you,

Pierre Alliez
INRIA Sophia Antipolis - Mediterranee 
Project-team GEOMETRICA 
http://www-sop.inria.fr/members/Pierre.Alliez/
Tel: +33 4 92 38 76 77
Fax: +33 4 97 15 53 95

Matthew Denno a écrit :

Hi All,

So I have implemented a solution for my question below.  If the object returned is a segment I check to see if it is degenerate.  If it is I convert its source end to a point.  This seems to work ok.  However, I am still interested to know if this is the intended behavior or not?  Anyone have any thoughts?

Regards,

Matt

---------- Forwarded message ----------
From: Matthew Denno <>
Date: Mon, Aug 10, 2009 at 10:17 PM
Subject: Triangle_3_Segment_3_intersection question
To:


Hello,

I have a question regarding the Triangle_3_Segment_3_intersection function that is in CGAL3.5b1.  Should it ever return a degenerate Segment_3?  Seems like it should return a Point_3 instead.  Not sure if this is a bug, is the intended behavior, or I am doing something wrong. 

The situation that is giving me the degenerate segment is the intersection of a coplaner triangle and segment where the end of the segment is touching the edge of the triangle.

I can send a simple example if anyone is interested.

Thanks,

Matt

#ifndef TRIANGLE_TRIANGLE_INTERSECT_H
#define TRIANGLE_TRIANGLE_INTERSECT_H

//
// CGAL Includes
#include <CGAL/AABB_intersections.h>
//#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Simple_cartesian.h>
#include <CGAL/intersections.h>

//
// CGAL Typedefs
typedef CGAL::Simple_cartesian<double> K;
//typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef K::Point_3   Point;
typedef K::Triangle_3 Triangle;
typedef K::Segment_3 Segment;


bool point_uniqueness(Point npt, std::vector<Point> v)
{
    //check if the point being added to vector<Point> is unique

    std::vector<Point>::iterator pi;
    for (pi = v.begin(); pi != v.end(); ++pi)
    {
        Point p = *pi;
        if (p == npt)
        {
            //qDebug("False");
            return false;
        }
    }
    //qDebug("True");
    return true;
}

bool segment_uniqueness(Segment nseg, std::vector<Segment> s)
{
    //check if the segment being added to the vector<Segment> is unique
    //flip and check for uniqueness also

    std::vector<Segment>::iterator si;
    for (si = s.begin(); si != s.end(); ++si)
    {
        Segment seg = *si;
        if (seg == nseg)
        {
            //qDebug("Segment is already in vector 1");
            return false;
        }
        else if (seg == nseg.opposite())
        {
            //qDebug("Segment is already in vector 2");
            return false;
        }
    }
    //qDebug("Segment added to vector");
    return true;
}

void intersect_routine(std::vector<Point> &pts, std::vector<Segment> &segs, Triangle t, Segment s)
{
        if (CGAL::do_intersect(t,s))
        {
            //qDebug("Intersection Detected");
            CGAL::Object obj = CGAL::intersection(t,s);
            if (const K::Point_3 * point = CGAL::object_cast<K::Point_3>(&obj))
            {
                //qDebug("intersection is a point");
                Point p = *point;
                if (point_uniqueness(p,pts))
                {
                    pts.push_back(p);
                }

            }
            else if (const K::Segment_3 * segment = CGAL::object_cast<K::Segment_3>(&obj))
            {
                //qDebug("intersection is a segment");
                Segment s = *segment;
                if (! s.is_degenerate())
                {
                    if (segment_uniqueness(s,segs))
                    {
                        segs.push_back(s);
                    }
                }
                else
                {
                    Point p = s.source();
                    if (point_uniqueness(p,pts))
                    {
                        pts.push_back(p);
                    }
                }
            }
        }
}

void get_triangle_points(std::vector<Point> &pts, std::vector<Segment> &segs)
{
    std::vector<Segment>::iterator si;
    for (si = segs.begin(); si != segs.end(); ++si)
    {
        Segment s = *si;
        if (point_uniqueness(s.source(),pts))
        {
           pts.push_back(s.source());
        }
        if (point_uniqueness(s.target(),pts))
        {
           pts.push_back(s.target());
        }
    }
}

CGAL::Object triangle_triangle_intersect(Triangle t1, Triangle t2)
{
    std::vector<Point> pts;
    std::vector<Segment> segs;

    if(CGAL::do_intersect(t1,t2))
    {
        const Segment s1t2 = Segment(t2.vertex(0),t2.vertex(1));
        const Segment s2t2 = Segment(t2.vertex(1),t2.vertex(2));
        const Segment s3t2 = Segment(t2.vertex(2),t2.vertex(0));
        const Segment s1t1 = Segment(t1.vertex(0),t1.vertex(1));
        const Segment s2t1 = Segment(t1.vertex(1),t1.vertex(2));
        const Segment s3t1 = Segment(t1.vertex(2),t1.vertex(0));

        intersect_routine(pts, segs, t1, s1t2);
        intersect_routine(pts, segs, t1, s2t2);
        intersect_routine(pts, segs, t1, s3t2);
        intersect_routine(pts, segs, t2, s1t1);
        intersect_routine(pts, segs, t2, s2t1);
        intersect_routine(pts, segs, t2, s3t1);

        if (pts.size() == 1)
        {
            //return point
            //qDebug("return point");
            Point p = pts[0];
            return CGAL::make_object(p);

        }
        else if (pts.size() == 2)
        {
            //return segemnt
            //qDebug("return segment");
            Segment s = Segment(pts[0], pts[1]);
            return CGAL::make_object(s);
        }
        else if (segs.size() == 2)
        {
            //return 2 segs, not sure this is possible
            qDebug("2 segments were found, this is probably an error");
            return CGAL::Object();
        }
        else if (segs.size() == 3)
        {
            //return triangle
            qDebug("return triangle");
            std::vector<Point> tpts;
            get_triangle_points(tpts,segs);
            Triangle t = Triangle(tpts[0], tpts[1], tpts[2]);
            return CGAL::make_object(t);
        }
        else if (segs.size() > 3 && segs.size() <= 6)
        {
            //return polygon, not sure what to do here as there is no
            //Polygon_3 in CGAL
            qDebug("return polygon");
            return CGAL::Object();
        }
        else
        {
            //should never get here
            qDebug("oops, there was an error constructing the intersection");
            return CGAL::Object();
        }
    }
    else
    {
        //do_intersect should be called before
        qDebug("oops, the triangles don't intersect");
        return CGAL::Object();
    }
}


#endif // TRIANGLE_TRIANGLE_INTERSECT_H