CGAL users discussion list

[Efi Fogel <>]

I'm not sure why you compare points but say that you intend to intersect edges, but it seems to me that you should use the overlay() free function; see, e.g., http://doc.cgal.org/latest/Arrangement_on_surface_2/group__PkgArrangement2Funcs.html#gaddb9e44b14b27e4cf0c7bb26b27d8518

Also, notice that the traits contains a predicate that compares two points. You should use it instead of the '==' operator.

   ____  _        ____             _
  /_____/_) o    /__________  __  //
 (____ (   (    (    (_/ (_/-(-'_(/
                         _/

On Tue, May 17, 2016 at 8:45 PM, Everton Constantino <> wrote:

So, changing the algorithm as you mentioned I realised something. One
edge on a Arrangement might represent the same line as several edges on
the other or, even worse, one edge of an Arrangement might contain
several edges of the other and even more so my way of checking the
intersection fails.

What I think I should be doing is to check which segments of one
arrangement are contained in the other not edges in particular. I know a
naive, brute force, way to solve this. Do I have something in CGAL that
could help me?

E.

On 18:14, Sebastien Loriot (GeometryFactory) wrote:
> One way to speed things up is to put arrangement edges in a std::set<
> std::pair<vertex_handle,vertex_handle> > with a custom less functor
> comparing the points of the vertices (if you don't care about
> orientation then also sort the pair before insertion).
> You can then use the set for queries.
>
> About the missing edges, it would be interesting to see those missing.
> Did you try another visibility algorithm provided in CGAL, just so see
> if the results are the same?
>
> Sebastien.
>
>
> On 05/17/2016 05:50 PM, Everton Constantino wrote:
> > The source is on github https://github.com/everton1984/Malex the file is
> > src/get_chunks.cpp. Thanks for the == tip, I already started using it
> > btw.
> >
> > The data, unfortunately, is private and I can't share it.
> >
> > E.
> >
> > On 17:17, Sebastien Loriot (GeometryFactory) wrote:
> > > We're looking for a pb here. If we can't see a full example
> > > (in particular the typedefs) and try compiling it to reproduce the
> > > issue it is harder to help because we can only guess.
> > >
> > > I know it is some extra work but it is needed if you want to maximize
> > > the chances to get an answer.
> > >
> > > Sebastien.
> > >
> > > PS: Note that operator==()(Point_2, Point_2) is implemented in CGAL.
> > >
> > > On 05/17/2016 04:59 PM, Everton Constantino wrote:
> > > > Oh ok, here is the part where I do the intersection:
> > > >
> > > > Arrangement_2 res;
> > > > vector<Kernel::Segment_2> bounding_roads;
> > > > for( Edge_const_iterator eit = output_arr.edges_begin(); eit != output_arr.edges_end(); ++eit){
> > > >       bool found = false;
> > > >       for( Edge_const_iterator envit = env.edges_begin(); envit != env.edges_end() && !found; ++envit ){
> > > >           if( envit->source()->point().x() == eit->source()->point().x() &&
> > > >                   envit->source()->point().y() == eit->source()->point().y() &&
> > > >                   envit->target()->point().x() == eit->target()->point().x() &&
> > > >                   envit->target()->point().y() == eit->target()->point().y() ){
> > > >               found = true;
> > > >           }else if(envit->source()->point().x() == eit->target()->point().x() &&
> > > >                   envit->source()->point().y() == eit->target()->point().y() &&
> > > >                   envit->target()->point().x() == eit->source()->point().x() &&
> > > >                   envit->target()->point().y() == eit->source()->point().y() ){
> > > >               found = true;
> > > >           }
> > > >       }
> > > >       if( found ) {
> > > >           Kernel::Segment_2 seg( eit->source()->point(), eit->target()->point() );
> > > >           bounding_roads.push_back(seg);
> > > >       }
> > > > }
> > > > CGAL::insert(res, bounding_roads.begin(), bounding_roads.end());
> > > >
> > > >
> > > > On 16:26, Sebastien Loriot (GeometryFactory) wrote:
> > > > > Sorry I meant a minimal code example to see where the pb could be.
> > > > > The problem was clear.
> > > > >
> > > > > Sebastien.
> > > > >
> > > > > On 05/17/2016 04:22 PM, Everton Constantino wrote:
> > > > > > Hi Sebastien,
> > > > > > you can find a file at http://braindump.com.br/arr.pdf with sets of 3
> > > > > > images, one is a map of roads, the 'raw' shows the computed visibility
> > > > > > Arrangement (for the point on the image, there's also a not shown square
> > > > > > drawn around the point) and the other shows the intersection of edges
> > > > > > form by the roads and the visibility region.
> > > > > >
> > > > > > What I want to do is to calculate the roads that belong to the
> > > > > > visibility of a certain point. You will notice that some roads that are
> > > > > > present both on the 'raw' image and on the full map are not present on
> > > > > > the intersection.
> > > > > >
> > > > > > The way I'm calculating right now is iterating through edges of both
> > > > > > arrangements and comparing source() and target() points (since they are
> > > > > > directed segments I compare both directions because I don't care).
> > > > > >
> > > > > > Hope that clarifies something.
> > > > > >
> > > > > > Thanks,
> > > > > > E.
> > > > > >
> > > > > > On 16:02, Sebastien Loriot (GeometryFactory) wrote:
> > > > > > > Please share a minimal example showing what is not working correctly.
> > > > > > >
> > > > > > > Thanks,
> > > > > > >
> > > > > > > Sebastien.
> > > > > > >
> > > > > > > On 05/17/2016 03:52 PM, Everton Constantino wrote:
> > > > > > > > Hi,
> > > > > > > > I'm trying to intersect two Arrangement_2 edge's but iterating through
> > > > > > > > both sets of edges and checking the source(), target() is not only slow
> > > > > > > > but wrong (some edges are missing). Is there a canonical way to do this?
> > > > > > > >
> > > > > > > > Thanks,
> > > > > > > >
> > > > > > >
> > > > > > >
> > > > > > > --
> > > > > > > You are currently subscribed to cgal-discuss.
> > > > > > > To unsubscribe or access the archives, go to
> > > > > > > https://sympa.inria.fr/sympa/info/cgal-discuss
> > > > > > >
> > > > > > >
> > > > > >
> > > > >
> > > > >
> > > > > --
> > > > > You are currently subscribed to cgal-discuss.
> > > > > To unsubscribe or access the archives, go to
> > > > > https://sympa.inria.fr/sympa/info/cgal-discuss
> > > > >
> > > > >
> > > >
> > >
> > >
> > > --
> > > You are currently subscribed to cgal-discuss.
> > > To unsubscribe or access the archives, go to
> > > https://sympa.inria.fr/sympa/info/cgal-discuss
> > >
> > >
> >
>
>
> --
> You are currently subscribed to cgal-discuss.
> To unsubscribe or access the archives, go to
> https://sympa.inria.fr/sympa/info/cgal-discuss
>
>

--
Everton R. Constantino <>
"Success is overrated"