polygon_2_simplicity.h

很多二维 三维几何计算算法 C++ 类库

    return m_vertex_data->less_xy_2(
            m_vertex_data->point(i), m_vertex_data->point(j));
}

template <class ForwardIterator, class PolygonTraits>
Vertex_data_base<ForwardIterator, PolygonTraits>::
Vertex_data_base(ForwardIterator begin, ForwardIterator end,
                 const PolygonTraits& pgn_traits)
: orientation_2(pgn_traits.orientation_2_object()),
  less_xy_2(pgn_traits.less_xy_2_object())
{
    m_size = std::distance(begin, end);
    is_simple_result = true;
    m_idx_at_rank.reserve(m_size);
    iterators.reserve(m_size);
    m_order_of.insert(m_order_of.end(), m_size, Vertex_order(0));
    for (Index_t i = 0; i< m_size; ++i, ++begin) {
        m_idx_at_rank.push_back(Vertex_index(i));
	iterators.push_back(begin);
    }
    std::sort(m_idx_at_rank.begin(), m_idx_at_rank.end(),
              Less_vertex_data<Vertex_data_base>(this));
    for (Index_t j = 0; j < m_size; ++j) {
	Vertex_order vo(j);
        m_order_of[index_at_rank(vo).as_int()] = vo;
    }
}

template <class ForwardIterator, class PolygonTraits>
void Vertex_data<ForwardIterator, PolygonTraits>::
left_and_right_index(Vertex_index &left, Vertex_index &right,
            Vertex_index edge)
{
    if (edges[edge.as_int()].is_left_to_right) {
        left = edge; right = next(edge);
    } else {
        right = edge; left = next(edge);
    }
}

template <class ForwardIterator, class PolygonTraits>
Vertex_data<ForwardIterator, PolygonTraits>::
Vertex_data(ForwardIterator begin, ForwardIterator end,
            const PolygonTraits& pgn_traits)
  : Base_class(begin, end, pgn_traits) {}

template <class ForwardIterator, class PolygonTraits>
void Vertex_data<ForwardIterator, PolygonTraits>::init(Tree *tree)
{
    // The initialization cannot be done in the constructor,
    // otherwise we copy singular valued iterators.
    edges.insert(edges.end(), this->m_size, Edge_data<Less_segs>(tree->end()));
}


template <class ForwardIterator, class PolygonTraits>
bool Vertex_data<ForwardIterator, PolygonTraits>::
insertion_event(Tree *tree, Vertex_index prev_vt,
            Vertex_index mid_vt, Vertex_index next_vt)
{
    // check which endpoint is above the other
    bool left_turn;
    switch(this->orientation_2(point(prev_vt), point(mid_vt), point(next_vt))) {
      case LEFT_TURN: left_turn = true; break;
      case RIGHT_TURN: left_turn = false; break;
      default: return false;
      
    }
    Edge_data<Less_segs>
        &td_prev = edges[prev_vt.as_int()],
        &td_mid = edges[mid_vt.as_int()];
    td_prev.is_in_tree = false;
    td_prev.is_left_to_right = false;
    td_mid.is_in_tree = false;
    td_mid.is_left_to_right = true;
    // insert the highest chain first
    std::pair<typename Tree::iterator, bool> result;
    if (left_turn) {
        result = tree->insert(prev_vt);
	// CGAL_polygon_assertion(result.second)
	td_prev.tree_it = result.first;
        td_prev.is_in_tree = true;
        result = tree->insert(mid_vt);
	// CGAL_polygon_assertion(result.second)
	td_mid.tree_it = result.first;
        td_mid.is_in_tree = true;
    } else {
        result = tree->insert(mid_vt);
	// CGAL_polygon_assertion(result.second)
	td_mid.tree_it = result.first;
        td_mid.is_in_tree = true;
        result = tree->insert(prev_vt);
	// CGAL_polygon_assertion(result.second)
	td_prev.tree_it = result.first;
        td_prev.is_in_tree = true;
    }
    return true;
}

template <class ForwardIterator, class PolygonTraits>
bool Vertex_data<ForwardIterator, PolygonTraits>::
on_right_side(Vertex_index vt, Vertex_index edge_id, bool above)
{
    Orientation turn =
        this->orientation_2(point(edge_id), point(vt), point(next(edge_id)));
    bool left_turn = edges[edge_id.as_int()].is_left_to_right ? above : !above;
    if (left_turn) {
        if (turn != RIGHT_TURN) {
            return false;
        }
    } else {
        if (turn != LEFT_TURN) {
            return false;
        }
    }
    return true;
}

template <class ForwardIterator, class PolygonTraits>
bool Vertex_data<ForwardIterator, PolygonTraits>::
replacement_event(Tree *tree, Vertex_index cur_edge, Vertex_index next_edge)
{
    // check if continuation point is on the right side of neighbor segments
    typedef typename Tree::iterator It;
    Edge_data<Less_segs> &td = edges[cur_edge.as_int()];
    CGAL_polygon_assertion(td.is_in_tree);
    It cur_seg = td.tree_it;
    Vertex_index cur_vt = (td.is_left_to_right) ? next_edge : cur_edge;
    if (cur_seg != tree->begin()) {
        It seg_below = cur_seg;
	--seg_below;
	if (!on_right_side(cur_vt, *seg_below, true)) {
	    return false;
        }
    }
    It seg_above = cur_seg;
    ++ seg_above;
    if (seg_above != tree->end()) {
        if (!on_right_side(cur_vt, *seg_above, false)) {
	    return false;
        }
    }
    // replace the segment
    Edge_data<Less_segs> &new_td =
            edges[next_edge.as_int()];
    new_td.is_left_to_right = td.is_left_to_right;
    new_td.is_in_tree = false;
    tree->erase(cur_seg);
    td.is_in_tree = false;
    new_td.tree_it = tree->insert(seg_above, next_edge);
    new_td.is_in_tree = true;
    return true;
}

template <class ForwardIterator, class PolygonTraits>
bool Vertex_data<ForwardIterator, PolygonTraits>::
deletion_event(Tree *tree, Vertex_index prev_vt, Vertex_index mid_vt)
{
    // check if continuation point is on the right side of neighbor segments
    typedef typename Tree::iterator It;
    Edge_data<Less_segs>
        &td_prev = edges[prev_vt.as_int()],
        &td_mid = edges[mid_vt.as_int()];
    It prev_seg = td_prev.tree_it, mid_seg = td_mid.tree_it;
    Vertex_index cur_vt = (td_prev.is_left_to_right) ? mid_vt : prev_vt;
    It seg_above = prev_seg;
    ++seg_above;
    if (seg_above == mid_seg) {
        ++seg_above;
    } else {
        // mid_seg was not above prev_seg, so prev_seg should be above mid_seg
        // We check this to see if the edges are really neighbors in the tree.
        It prev_seg_copy = mid_seg;
        ++prev_seg_copy;
        if (prev_seg_copy != prev_seg)
            return false;
    }
    // remove the segments
    tree->erase(prev_seg);
    td_prev.is_in_tree = false;
    tree->erase(mid_seg);
    td_mid.is_in_tree = false;
    // Check if the vertex that is removed lies between the two tree edges.
    if (seg_above != tree->end()) {
        if (!on_right_side(cur_vt, *seg_above, false))
	    return false;
    }
    if (seg_above != tree->begin()) {
        --seg_above; // which turns it in seg_below
        if (!on_right_side(cur_vt, *seg_above, true))
	    return false;
    }
    return true;
}

template <class ForwardIterator, class PolygonTraits>
void Vertex_data<ForwardIterator, PolygonTraits>::
sweep(Tree *tree)
{
    if (this->m_size < 3)
    	return;
    bool succes = true;
    for (Index_t i=0; i< this->m_size; ++i) {
        Vertex_index cur = index_at_rank(Vertex_order(i));
	    Vertex_index prev_vt = prev(cur), next_vt = next(cur);
	    if (ordered_left_to_right(cur, next_vt)) {
	        if (ordered_left_to_right(cur, prev_vt))
	            succes = insertion_event(tree, prev_vt, cur, next_vt);
	        else
	            succes = replacement_event(tree, prev_vt, cur);
	    } else {
	        if (ordered_left_to_right(cur, prev_vt))
	            succes = replacement_event(tree, cur, prev_vt);
	        else
	            succes = deletion_event(tree, prev_vt, cur);
	    }
	    if (!succes)
	        break;
    }
    if (!succes)
    	this->is_simple_result = false;
}
}
// ----- End of implementation of i_polygon functions. -----


template <class Iterator, class PolygonTraits>
bool is_simple_polygon(Iterator points_begin, Iterator points_end,
                       const PolygonTraits& polygon_traits)
{
    typedef Iterator ForwardIterator;
    typedef i_polygon::Vertex_data<ForwardIterator, PolygonTraits> Vertex_data;
    typedef std::set<i_polygon::Vertex_index,
                     i_polygon::Less_segments<Vertex_data> >       Tree;
    Vertex_data   vertex_data(points_begin, points_end, polygon_traits);
    Tree tree(&vertex_data);
    vertex_data.init(&tree);
    vertex_data.sweep(&tree);
    return vertex_data.is_simple_result;
}

} // end of namespace CGAL

#endif