CGAL users discussion list

[Efi Fogel <>]

Hi Everton,

Now I understand.
A possible efficient solution would be based on the plane-sweep framework, but currently there is non.

The overlay can still be used. There is a call back for each intersection (vertex-vertex, edge-vertex, vertex-edge, edge-edge, etc) You can filter out everything that is not edge-edge intersection that is an overlap.

BW, the traits has an intersect predicate, but this is less important. (In some cases the traits intersect uses the kernel intersect, but not always).

Best,

Efi

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

On Wed, May 18, 2016 at 12:57 AM, Everton Constantino <> wrote:

Hi Efi,
thanks for the tips, the overlay gives the opposite of what I want,
sorry I should have made myself clearer I meant union and intersection
as set theoretic words. Anyway you sorta gave me the path, I'm iterating
edges, getting the associated curve and using Kernel::Intersect_2. Now
everything is working as intended.

Best regards,
E.

On 23:50, Efi Fogel wrote:
> Hi Everton,
>
> 1. The equivalent of the '==' operator is the 'Equal_2' functor; see
> http://doc.cgal.org/latest/Arrangement_on_surface_2/classArrTraits_1_1Equal__2.html
> 2. The overlay gives you the overlay. What do you mean by 'union of
> arrangements' or 'intersection of arrangements'?
>
> Best,
> Efi
>
>    ____  _        ____             _
>   /_____/_) o    /__________  __  //
>  (____ (   (    (    (_/ (_/-(-'_(/
>                          _/
>
>
>
> On Tue, May 17, 2016 at 9:40 PM, Everton Constantino <
> > wrote:
>
> > Hi Efi,
> > reading CGAL's documentation I failed to find the definition of the ==
> > operator for edges so I ended up using brute force. The overlay free
> > function gives me the union of the arrangements (I dunno if there's an
> > option for the intersection).
> >
> > Thanks,
> > E.
> >
> > On 21:14, Efi Fogel wrote:
> > > 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"
> > > >
> > >
> > > --
> > > 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"
> >
>
> --
> 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"