CGAL users discussion list

[Ben Supnik <>]

Sorry for the half-send...performance will depend on the nature of the 
dataset and what is desired.  Random thoughts:

- True intersection is going to be expensive.  For example, when you 
consider the effects of polygons that are disjoint except at 
edges/vertices, you might need a true polygon boolean intersection, 
which requires an exact numeric type.

- The intersection will be superior to the previous technique 
(containment tests on each edge) - intersection is O(N+MlogN+M) whereas 
the intersection test I think is O(NM).

- It might be possible to do sweeps on all vertices of the polygon at 
once, e.g. "which of this set of points are in the polygon" which would 
be faster than individual tests.  I'm not sure what the best interface 
for that is...possibly to build an arrangement off of the polygon using 
accelerated insertions, then do a bulk point locate on the arrangement 
(which sweeps).

- A filtered or lazy adapter might speed gmp up, especially if your 
input numbers are IEEE doubles.

- The only CGAL tools that will work reliably with IEEE doubles that are 
applicable that I know of are:

1. Bbox2 for a quick check - if most polygons don't contain each other, 
a few fast bbox tests might save you a lot of time.

2. You can do a do_intersect on line segments on the union of all edges 
of both polygons, even with an exact-predicate inexact construction 
kernel, which will be faster.  But you'd have to be careful about how 
exactly overlapping polygons are handled.

cheers
ben

Marcos R. P. wrote:
> Try this:
> Test if there are intersection between polygons and test if a point of 
> one is an interior point of other.
>  
> Marcos
>
> ------------------------------------------------------------------------
> *De:* Cristiano Nattero 
> <>
> *Para:* 
>
> *Enviadas:* Quarta-feira, 25 de Novembro de 2009 8:14:19
> *Assunto:* [cgal-discuss] testing for polygon containment
>
> Hello everybody,
>
>   how would you test if a polygon is contained inside another?
>
>   I used the condition that a polygon A is contained in a polygon B
> iff all the edges of A are contained in B.
>
>   Unfortunately - and it might be a problem of my implementation: I
> use Polygon_2 with Gmpq point coordinates - I am not satisfied with
> its speed. Can you think of a quicker way?
>
>   Thank you very much.
>
> --
> Ciao,
> Cristiano
>
> http://cristianonattero.com/blog
>
> MSN messenger: 
>
>  
> <mailto:>
> yahoo IM: cristiano.nattero
> jabber/GoogleTalk:  
> <mailto:>
> AIM: 
>
>  
> <mailto:>
> skype: cristianonattero
> SIP: 
>
>  
> <mailto:>
>
> Linux User #368283
> http://counter.li.org/
>
> --
> You are currently subscribed to cgal-discuss.
> To unsubscribe or access the archives, go to
> https://lists-sop.inria.fr/wws/info/cgal-discuss
>
>
> ------------------------------------------------------------------------
> Veja quais são os assuntos do momento no Yahoo! + Buscados: Top 10 
> <http://br.rd.yahoo.com/mail/taglines/mail/*http://br.maisbuscados.yahoo.com/> 
> - Celebridades 
> <http://br.rd.yahoo.com/mail/taglines/mail/*http://br.maisbuscados.yahoo.com/celebridades/> 
> - Música 
> <http://br.rd.yahoo.com/mail/taglines/mail/*http://br.maisbuscados.yahoo.com/m%C3%BAsica/> 
> - Esportes 
> <http://br.rd.yahoo.com/mail/taglines/mail/*http://br.maisbuscados.yahoo.com/esportes/>

--
Scenery Home Page: http://scenery.x-plane.com/
Scenery blog: http://xplanescenery.blogspot.com/
Plugin SDK: http://www.xsquawkbox.net/xpsdk/
X-Plane Wiki: http://wiki.x-plane.com/
Scenery mailing list: 

Developer mailing list: