Ошибка в функции определения местоположения?

Я новичок в CGAL, и когда я использую функцию .locate() для поиска точки в треугольнике, возникают некоторые проблемы. Сначала я строю треугольник с тремя точками (-1,0) (1,0) (0,1), затем я проверяю взаимное расположение некоторых точек с треугольником, точки:

p0(0.8, 0.1) ---- locate in the triangle；
p1(0.95, 0) ---- locate on the edge (-1,0) ---- (1,0)；
p2(0.8, 0.2) ---- locate on the edge (1,0) ---- (0,1)；
p3(0.6, 0.4) ---- locate on the edge (1,0) ---- (0,1)；
p4(0.7,0.3) ---- locate on the edge (1,0) ---- (0,1)；

Но результаты поиска:

p0 ---- FACE, right!
p1 ---- EDGE, right!
p2 ---- OUTSIDE_CONVEX_HULL, wrong!
p3 ---- EDGE, right!
p4 ---- FACE, wrong!

а точки p2, p3, p4 лежат на одном ребре (1,0) ---- (0,1)

В чем причина проблемы?

Код:

typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef CGAL::Delaunay_triangulation_2<K> Delaunay_triangulation;

void main()
{
    //generate the triangles
    std::vector<Point2> pts;
    pts.push_back(Point2(1,0));
    pts.push_back(Point2(-1,0));
    pts.push_back(Point2(0,1));
    Delaunay_triangulation dt;
    dt.insert(pts.begin(), pts.end());

    //locate point in the triangle
    Point2 pt0 = Point2(0.8, 0.1);//the point located in the triangle.(on the FACE ?)
    Point2 pt1 = Point2(0.95, 0);//the point located on the segment ( (1,0) ---- (-1,0) ) (on the EDGE ?)
    Point2 pt2 = Point2(0.8, 0.2);//the point locate on the segment ( (1,0) ---- (0,1) ) (on the EDGE ?)
    Point2 pt3 = Point2(0.6, 0.4);//the point locate on the segment ( (1,0) ---- (0,1) ) (on the EDGE ?)
    Point2 pt4 = Point2(0.7,0.3);//the point locate on the segment ( (1,0) --- (0,1) ) (on the EDGE ?)
    Face_handle fh0, fh1, fh2, fh3, fh4;
    Delaunay_triangulation::Locate_type lt0, lt1, lt2, lt3, lt4;
    int li;
    fh0 = dt.locate(pt0, lt0, li);//for pt0, lt0 is equal to FACE, right!
    fh1 = dt.locate(pt1, lt1, li);//for pt1, lt1 is equal to EDGE, right!
    fh2 = dt.locate(pt2, lt2, li);//for pt2, lt2 is equal to OUTSIDE_CONVEX_HULL, I think it's wrong!
    fh3 = dt.locate(pt3, lt3, li);//for pt3, lt3 is equal to EDGE, right!
    fh4 = dt.locate(pt4, lt4, li);//for pt4, lt3 is equal to FACE, I thing it's wrong!
}

cgal triangulation locate
person ffmm3    schedule 22.10.2013    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Число с плавающей запятой не может представлять все десятичные числа, которые можно записать. Имеются ошибки округления. По этой причине координаты точек не такие, как вы думаете. Возьмите следующую программу:

#include <iostream>
#include <CGAL/Point_2.h>
#include <CGAL/Simple_cartesian.h>

typedef CGAL::Simple_cartesian<double> Kernel;
typedef Kernel::Point_2 Point;

int main()
{
  std::cout.precision(17);
  Point p0(0.8, 0.1);
  Point p1(0.95, 0);
  Point p2(0.8, 0.2);
  Point p3(0.6, 0.4);
  Point p4(0.7,0.3);
  std::cout << p0 << std::endl;
  std::cout << p1 << std::endl;
  std::cout << p2 << std::endl;
  std::cout << p3 << std::endl;
  std::cout << p4 << std::endl;
  return 0;
}

Он отображает координаты точек с высокой точностью. Вывод следующий:

0.80000000000000004 0.10000000000000001
0.94999999999999996 0
0.80000000000000004 0.20000000000000001
0.59999999999999998 0.40000000000000002
0.69999999999999996 0.29999999999999999

Эти координаты объясняют все местоположения, возвращенные locate().

person lrineau    schedule 22.10.2013
comment
Спасибо за помощь! - person ffmm3; 01.11.2013