Mon 25 Jun 2007 10:29:16 AM UTC, original submission:
The triangulation code doesn't work for
1. a convex polygon [ a simple example would be (0,0), (1,0), (1,1), (0,1) ]
2. a concave polygon, the reflex vertices of which form a zero-area boundingbox.
A simple test program just crashes.
Reason:
=======
In poly<coord_t>::init_for_ear_clipping in triangulate_impl.h, if there is no reflex vertex or the reflex vertices form a zero-area boundingbox, e.g., there is only one reflex vertex, the m_reflex_point_index will have a zero-area boundingbox as its member variable.
Later in the function get_containing_cell_clamped in grid_index.h,
there will be a divide-by-zero exception.
Possible fix:
============
add the following code
if(reflex_bound.get_width() == 0)
{
reflex_bound.min.x -= 1;
reflex_bound.max.x += 1;
}
if(reflex_bound.get_height() == 0)
{
reflex_bound.min.y -= 1;
reflex_bound.max.y += 1;
}
before this line:
m_reflex_point_index = new grid_index_point<coord_t, int>(reflex_bound, x_cells, y_cells);
in poly<coord_t>::init_for_ear_clipping in triangulate_impl.h.
|