CGAL users discussion list

[Ralph Boland <>]

On 22 June 2010 07:43, Francesc Vila 
<>
 wrote:
> El 21/06/2010 18:23, Sebastien Loriot (GeometryFactory) escribió:
>>
>> Francesc Vila wrote:
>>>
>>> El 21/06/2010 17:44, Sebastien Loriot (GeometryFactory) escribió:
>>>>
>>>> Francesc Vila wrote:
>>>>>
>>>>> Hi all,
>>>>>
>>>>> I am using CGAL to make some transformations on a GDSII (stream format)
>>>>> file. Within this file, I can read polygons that aren't always simple. 
>>>>> Is
>>>>> there any way to partition a polygon that is not simple? In fact, the
>>>>> polygon is weakly simple (has a coincident edge).
>>>>>
>>>>> Thanks in advance,
>>>>>
>>>>> Francesc Vila
>>>>>
>>>>
>>>> I think you will need to use a pre-processing step to extract simple
>>>> polygons from each weakly simple polygon.
>>>>
>>>> S.

There is a paper which describes how to to decompose a self overlapping 
polygon
into trapezoids  O(n^3) time.  Sorry I don't have the reference right
now but I could look it up.
You can still compute the "Area" of the polygon by a straightforward
algorithm in linear
time though.  If all you have are weakly coincident polygons then many
triangulation algorithms
should still work or work with only simple modifications; e.g.  plane
sweep based algorithms or
the sinuosity based algorithm (my favourite).

Regards,

Ralph Boland
>>>>
>>> I thought so..... :(
>>>
>>> Further reading this list, I found a method to create polygons with holes
>>> from Polygon_2. But it is dated 2009 and the code doesn't compile on my
>>> system.... Maybe it is my fault, but I think I can benefit from the 
>>> general
>>> idea it implements.
>>>
>>> Regards,
>>>
>>> Francesc Vila
>>>
>> An alternative that may fit you need is to use a constrained
>> triangulation to partition your weakly simple polygon,
>> constraints being polygon edges.
>>
>> S.
>>
> Hi,
>
> I tried the constrained triangulation, but some of the triangles it
> generated were part of the hole and not the polygon. Finally I preprocessed
> the polygon to make it simple. I have iterated through all vertices, and
> once I find a repeated one, I create a new polygon and save into a list.
> When I have finished I join all polygons in that list to obtain the polygon
> with holes.
>
> Best regards,
>
> Francesc
>
> --
> You are currently subscribed to cgal-discuss.
> To unsubscribe or access the archives, go to
> https://lists-sop.inria.fr/wws/info/cgal-discuss
>
>



-- 
Quantum Theory cannot save us from the tyranny of a deterministic universe
but it does give God something to do