Geometry Boost List: [ggl] Within polygon detection including the polygon borders

Subject: [ggl] Within polygon detection including the polygon borders
From: Barend Gehrels (Barend.Gehrels)
Date: 2009-09-21 17:13:05

Hi Ivan,

>
>     Note that it was not the *clockwise* *order* which was not
>     correct, but the points were ordered wrong (hard to explain).
>     Because you're  calling "correct", you can enter them in any
>     order. If not, you have to enter them in clockwise order.
>     Lower-left is not relevant here, you can also start with
>     upperright and in polygons with more than 4 points this is
>     actually hard to define. You can start anywhere.
>
>
> Is there any documentation about this point order thing? I'm 
> interested, as this is important for my simulation, and if there is 
> some sort of standard I would like very much to read it. I will call 
> correct to order the points, thought.

We follow the OGC conventions, loosely. They define a polygon as having 
an clockwise exterior ring, and (optionally) counter-clockwise interior 
rings (holes). The corresponding OGC standard can be downloaded here: 
http://www.opengeospatial.org/standards/sfa#downloads

This is also (I think) the most common way to define a polygon, but, 
however, some libraries or tools use a counter-clockwise polygon as 
their default.

In the future we would like to make this direction flexible for GGL too.

>     So it probably does not happen if the points are clockwise or
>     anti-clockwise, but it happens if points are in orders like
>     1,3,2,4. It then gets a self-intersection and indeed, a function
>     to test that is valid, is required for OGC compliance, but is not
>     yet implemented...
>
>
> Is there any prevision for the intersection test routine?
Yes, there is, because our new intersection/union algorithms are divided 
into several steps and the first step, get intersection point, should be 
called for only one polygon. If there is an intersection, it is not 
valid. This is however not the most efficient way because if there is 
one, it can return and does not need to calculate other intersections.

> Or maybe I can help with this routine, if possible - this also 
> interests me a lot.

In general, any help of experienced C++ programmers is welcome! Your 
postings already help.
 

>
>  
>
>
>
>>      
>>
>>         >
>>         > 2) In the library (preview 4): the results are still wrong
>>         indeed, using
>>         > preview 4. Using the head (hosted at Geodan SVN) it is OK.
>>         The code in
>>         > preview4 didn't handle points on segments correctly, this
>>         was solved in the
>>         > meantime. So I updated preview 4, hosted at Boost SVN, with
>>         the new code and
>>         > it is OK now.
>>
>>
>>
>>     Yes, I've just downloaded the svn version, and it's working.
>     You mean the Boost.SVN version?
>
>
> No, the Geodan SVN. I was able to put to work together the boost trunk 
> and Geodan svn, boost 1.40 and Geodan svn, but not boost sandbox and 
> ggl from Geodan or the sandbox itself. Really don't know why not, it 
> just doesn't find ggl, no matter the paths for the files in /usr/include.

I don't understand this completely. You can get access to Geodan SVN, 
but currently you don't have (just checked). It is username/password 
protected. So unless you're hacking, you cannot reach the trunk ;-). 
However, I can give you access if you want.

If you download it, point your makefile or IDE to that folder and it 
should be able to find it, it is header only. Or use the -I directive 
for gcc

>
> If there is any references, or if I can help, please contact me.

As before, help is welcome, in the form of testing the library, just 
using it, reading/commenting documentation, writing documentation, 
reading code, writing code...

Just for my interest, are you going to use it for a project or product? 
Or just evaluating it? Just interested?

Regards, Barend

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/ggl/attachments/20090921/4d7560e3/attachment.html