CGAL users discussion list

[Natanael Ramos <>]

Hi all,

I'm using CGAL (v. 4.14-2) to compute the visibility region (polygon) within a simple polygon from one of its vertices, using the Simple_polygon_visibility_2 class.

On a particular combination of polygon/vertex, I'm getting the following assertion error:

terminate called after throwing an instance of 'CGAL::Assertion_exception'
  what():  CGAL ERROR: assertion violation!
Expr: k+1<vertices.size()
File: /usr/include/CGAL/Simple_polygon_visibility_2.h
Line: 678

This occurs in the method scan_edges of the class Simple_polygon_visibility_2, it seems like there should be some intersection with the given segment/ray, but none was found.

When I run the same code with the class Triangular_expansion_visibility_2, it seems to work, giving the output:

regularized visibility region of q has 8 edges:
[7968/1 492/1 -> 7938/1 428/1]
[7884/1 408/1 -> 7968/1 492/1]
[8040/1 428/1 -> 7884/1 408/1]
[1318831/163 428/1 -> 8040/1 428/1]
[550099518/67867 31141784/67867 -> 1318831/163 428/1]
[8090/1 456/1 -> 550099518/67867 31141784/67867]
[7968/1 446/1 -> 8090/1 456/1]
[7938/1 428/1 -> 7968/1 446/1]

I'm attaching a minimal work example, together with the input file.

The input file has in each line the polygon vertex id, followed by its x- and-coordinates. The query point is the one with id 1716.

Could anyone help me with this issue?

Thank you all in advance.

# Created by the script cgal_create_CMakeLists
# This is the CMake script for compiling a set of CGAL applications.

project( vis-poly )


cmake_minimum_required(VERSION 2.8.11)
set(CMAKE_CXX_STANDARD 14)
set(CMAKE_CXX_STANDARD_REQUIRED ON)

# CGAL and its components
find_package( CGAL QUIET COMPONENTS  )

if ( NOT CGAL_FOUND )

  message(STATUS "This project requires the CGAL library, and will not be 
compiled.")
  return()  

endif()


# Boost and its components
find_package( Boost REQUIRED )

if ( NOT Boost_FOUND )

  message(STATUS "This project requires the Boost library, and will not be 
compiled.")

  return()  

endif()

# include for local directory

# include for local package


# Creating entries for all C++ files with "main" routine
# ##########################################################


create_single_source_cgal_program( "vis_poly.cpp" )


#include <CGAL/Arr_naive_point_location.h>
#include <CGAL/Arr_segment_traits_2.h>
#include <CGAL/Arrangement_2.h>
#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Polygon_2.h>
#include <CGAL/Simple_polygon_visibility_2.h>
#include <CGAL/Triangular_expansion_visibility_2.h>
#include <fstream>
#include <iostream>
#include <string>
#include <list>
#include <vector>

typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel;
typedef Kernel::Point_2 Point_2;
typedef Kernel::Segment_2 Segment_2;
typedef CGAL::Polygon_2<Kernel, std::list<Point_2>> Polygon_2;
typedef CGAL::Arr_segment_traits_2<Kernel> Traits_2;
typedef CGAL::Arrangement_2<Traits_2> Arrangement_2;
typedef Arrangement_2::Face_handle Face_handle;
typedef Arrangement_2::Vertex_handle ArrVertex_handle;
typedef Arrangement_2::Edge_const_iterator Edge_const_iterator;
typedef Arrangement_2::Ccb_halfedge_circulator Ccb_halfedge_circulator;

using namespace std;

vector<Point_2> readInput() {
  vector<Point_2> Points;
  ifstream File;
  File.open("polygon");

  string Line;
  long int Idx, XCoord, YCoord;
  while (getline(File, Line)) {
    istringstream Iss(Line);
    Iss >> Idx >> XCoord >> YCoord;
    Points.push_back({XCoord, YCoord});
  }
  return Points;
}

int main() {
  // create environment
  std::vector<Segment_2> segments;
  Arrangement_2 env;
  Segment_2 CurrSegment;
  Polygon_2 AuxPoly;
  auto Points = readInput();
  auto QueryPt = Points[0];
  ArrVertex_handle CurrPtHandle =
      env.insert_in_face_interior(QueryPt, env.unbounded_face());
  AuxPoly.push_back(Points[0]);
  ArrVertex_handle NextPtHandle = CurrPtHandle;
  ArrVertex_handle QueryPtHandle = CurrPtHandle;
  for (auto i = 1; i < Points.size(); ++i) {
    NextPtHandle = env.insert_in_face_interior(Points[i], env.unbounded_face());
    CurrSegment = Segment_2(CurrPtHandle->point(), NextPtHandle->point());
    env.insert_at_vertices(CurrSegment, CurrPtHandle, NextPtHandle);
    CurrPtHandle = NextPtHandle;
    AuxPoly.push_back(Points[i]);
  }
  assert(AuxPoly.is_simple());
  CurrSegment = Segment_2(CurrPtHandle->point(), QueryPtHandle->point());
  auto HalfEHandle =
      env.insert_at_vertices(CurrSegment, CurrPtHandle, QueryPtHandle);

  // compute non regularized visibility area
  // Define visibiliy object type that computes regularized visibility area
  typedef CGAL::Simple_polygon_visibility_2<Arrangement_2, CGAL::Tag_true> RSPV;
  // typedef CGAL::Triangular_expansion_visibility_2<Arrangement_2, CGAL::Tag_true>  RSPV;
  Arrangement_2 regular_output;
  RSPV regular_visibility(env);
  regular_visibility.compute_visibility(QueryPtHandle->point(), HalfEHandle, regular_output);
  std::cout << "Regularized visibility region of q has "
            << regular_output.number_of_edges() << " edges:" << std::endl;
  for (Edge_const_iterator eit = regular_output.edges_begin();
       eit != regular_output.edges_end(); ++eit)
    std::cout << "[" << eit->source()->point() << " -> "
              << eit->target()->point() << "]" << std::endl;

  return 0;
}

Attachment: polygon
Description: Binary data