CGAL users discussion list

Hi,

Generally, a stricly simple polygon is one whose outer boundary  
contains every vertice only once (except the first/last vertice) while  
a simple polygon may have the same vertice appear twice or more on the  
outer boundary.
Simple, but not necessarily strictly simple, polygons are allowed as  
the outside boundaries of polygons with holes.
The is_simple() query checks for if a polygon is stirctly simple.

Here are the relevant parts from the user manual:

A polygon P is said to be simple (or Jordan) if the only points of the  
plane belonging to two polygon edges of P are the polygon vertices of  
P. Namely, the polygon edges are pairwise disjoint in their interior.  
Such a polygon has a well-defined interior and exterior and is  
topologically equivalent to a disk. A polygon in our context must be  
simple and its vertices must be ordered in a counterclockwise  
direction around the interior of the polygon.

A polygon whose boundary contains the same vertex twice or more is  
connected and simple but not necessarily strictly simple.

A polygon with holes represents a point set that may be bounded or  
unbounded. In case of a bounded set, its outer boundary is represented  
as a simple (but not necessarily strictly simple) polygon, whose  
vertices are oriented in a counterclockwise order around the interior  
of the set. In addition, the set may contain holes, where each hole is  
represented as a strictly simple polygon, whose vertices are oriented  
in a clockwise order around the interior of the hole.

Using the topological terminology, a general polygon can represent any  
simply-connected point set whose boundary is a strictly simple curve.  
Such a polygon is a model of the GeneralPolygon_2 concept.

For further elaboration look at the Boolean Set Operations_2 user manual.

Good day,

Guy

Quoting Kenneth Tham 
<>:

> Hi,
>    Thanks for your help. Yes, the polygon has 1 common point so it   
> is probably not simple, which may be the cause of the failure. I   
> have added a check using the method is_simple() to check if the   
> joined polygon is simple after joining. It seems to work better with  
>  the code now. What is the difference between simple and strictly   
> simple polygons? Thank you.
> Regards,
> Kenneth
>
>
> -----Original Message-----
> From: 
>
>  
> [mailto:]
> Sent: Tuesday, February 19, 2008 4:41 AM
> To: 
>
> Subject: RE: [cgal-discuss] CGAL::join Function
>
>
>
> Hi Kenneth,
>
> There are a few faults in your example which cause the errors.
>
> I'll refer to the following small part of Q from your example:
>
> Q.push_back (Point_2(103.63966979999999,1.2391405));
> Q.push_back (Point_2(103.64162709999999,1.2391810999999999));
> Q.push_back (Point_2(103.6397209,1.2391553));
> Q.push_back (Point_2(103.63966979999999,1.2391405));
> Q.push_back (Point_2(103.6395785,1.2391258000000001));
>
> Q.push_back (Point_2(103.6395201,1.2391295));
>
> Q.push_back (Point_2(103.6394873,1.2391405));
>
>
> 1. Polygon Q maybe simple but is definitely not strictly simple
> (points 1 and 4 are the same).The predicate
> is_counterclockwise_oriented() has a precondition that allows ony
> strictly simple polygons to be tested.
>
> 2. 1. Polygon Q is clockwise oriented. The Polygons package reqires
> the polygon boundaries to be oriented in a counter clockwise manner
> which may be the reason join() fails.
>
> I suggest you try to split your polygon Q into a series of smaller
> strictly simple  counterclockwise oriented polygons and try to perform
> the join operation.
>
> If this doesn't work, try and minimize Q to the smallest polygon that
> fails (hopefully less ten 10 vertices), and I'll have a another look...
>
> Sincerely,
>
> Guy Zucker
>
>
> -------------
>
> Quoting Kenneth Tham 
> <>:
>
> > Hi,
> >     Attached is my code that gives the error. The error occurs when
> >  the join function is called. I have commented out the code that
> > checks for orientation of the Polygon Q as that also gives an error.
> >   The interesting thing is that if the first three points are not
> > added in Polygon Q, the resulting polygon is anti-clockwise
> > oriented. But when the 3 points are added, it cannot pass the
> > checking. Thanks for your help.
> >
> > Regards,
> > Kenneth
> >
> >
> >         -----Original Message-----
> >         From: 
> >
> >  on behalf of Ophir Setter
> >         Sent: Thu 2/14/2008 4:53 PM
> >         To: 
> >
> >         Cc:
> >         Subject: Re: [cgal-discuss] CGAL::join Function
> >
> >
> >         What number type? - You shoiuld use a kernel that supports exact
> > construction and exact predicates.
> >
> >         I think the best way is if you send code and data that creates the 
> > bug.
> >
> >
> >         On Thu, Feb 14, 2008 at 10:45 AM, Kenneth Tham
> > <>
> >  wrote:
> >
> >
> >                 Hi,
> > 		    I am using a Kernel class inheriting from   
> > CGAL::Cartesian<Number_type>.
> >                 Regards,
> >                 Kenneth
> >
> >
> >                         -----Original Message-----
> >                         From: 
> >
> >  
> > [mailto:]On
> > Behalf Of Ophir Setter
> >                         Sent: Thursday, February 14, 2008 3:41 PM
> >                         To: 
> >
> >                         Subject: Re: [cgal-discuss] CGAL::join Function
> >
> >
> >                         Can send the code that generates the code?
> >                         What kernel are you using?
> >                         Can you send the data that causes this assertion?
> >
> >
> >
> >                         On Thu, Feb 14, 2008 at 8:47 AM, Kenneth Tham
> > <>
> >  wrote:
> >
> >
> >                                 Hi,
> >                                   Thanks for your help. I am now trying to 
> > debug the algorithm
> > for joining the polygons. There is one case where it needs to merge
> >  about 300 polygons. After about 200 times, the program gives the
> > error as shown in the attached file. I'm not really sure what it
> > means. Can anybody help? Thanks.
> >                                 Regards,
> >                                 Kenneth
> >
> >
> >
> >
> >                                 -----Original Message-----
> >                                 From: Efi Fogel 
> > [mailto:]
> >                                 Sent: Tuesday, February 12, 2008 10:23 PM
> >                                 To: 
> >
> >                                 Subject: Re: [cgal-discuss] CGAL::join 
> > Function
> >
> >
> >                                 Kenneth Tham wrote:
> >
> >                                 >Hi,
> >                                 >    I am using the CGAL::join function for 
> > joining
> > polygon_with_holes_2 objects. In my program, I use the join function
> >   for about 10000 times consequtively(trying to join a polygon to a
> >  set of polygons). My program takes quite a long time to process
> > this   part ( several minutes ). Is it normal for this function to
> > take   this amount of time? Thanks.
> >                                 >Regards,
> >                                 >Kenneth
> >                                 >
> >                                 >
> >                                 >
> >                                 First of all you should call the join 
> > function just once with a range of
> >                                 input polygons (or polygons with holes). If 
> > you intend to perform other
> >                                 operations in a sequence, you should call the 
> > join member function of
> >                                 Polygon_set_2 instead of the global join 
> > function. Finally, I assume you
> >                                 are using a exact-prediacte 
> > exact-construction kernel (for a good
> >                                 reason). This means that all operations are 
> > caried out in an exact
> >                                 maner. You can try to expedite the 
> > computation by reducing the bit
> >                                 length of the input coordinates.
> >
> >                                 --
> >                                  ____  _        ____             _
> >                                 /_____/_) o    /__________  __  //
> >                                 (____ (   (    (    (_/ (_/-(-'_(/
> >                                                        _/
> >
> >                                 --
> >                                 You are currently subscribed to cgal-discuss.
> >                                 To unsubscribe or access the archives, go to
> >                                 
> > https://lists-sop.inria.fr/wws/info/cgal-discuss
> >
> >
> >                                 [This e-mail is confidential and may be 
> > privileged. If you are not the
> >                                 intended recipient, please kindly notify us 
> > immediately and
> > delete the message
> >                                 from your system; please do not copy or use 
> > it for any purpose,
> >  nor disclose
> >                                 its contents to any other person. Thank you.]
> >                                 ---ST Electronics Group---
> >
> >
> >                                 --
> >                                 You are currently subscribed to cgal-discuss.
> >                                 To unsubscribe or access the archives, go to
> >                                 
> > https://lists-sop.inria.fr/wws/info/cgal-discuss
> >
> >
> >
> >
> > --
> > You are currently subscribed to cgal-discuss.
> > To unsubscribe or access the archives, go to
> > https://lists-sop.inria.fr/wws/info/cgal-discuss
>
>
>
>
> ----- End forwarded message -----
>
>
> --
> You are currently subscribed to cgal-discuss.
> To unsubscribe or access the archives, go to
> https://lists-sop.inria.fr/wws/info/cgal-discuss
>
> --
> You are currently subscribed to cgal-discuss.
> To unsubscribe or access the archives, go to
> https://lists-sop.inria.fr/wws/info/cgal-discuss