Geometry Boost List: [ggl] "touches" in boost.geometry?

Subject: [ggl] "touches" in boost.geometry?
From: Adam Wulkiewicz (adam.wulkiewicz)
Date: 2011-10-10 01:44:19

Barend Gehrels wrote:
> Hi Adam,
>
> On 9-10-2011 22:30, Adam Wulkiewicz wrote:
>> Barend Gehrels wrote:
>>> Hi Aleksandar,
>>>
>>> The touches algorithm is planned but not included, also not in the
>>> extensions. I once started it and today looked at it, but it is not
>>> suitable for inclusion yet. However it is on the list.
>>>
>>> As far as I know it cannot be done by using existing algorithms.
>>
>>
>> Hi Barand,
>>
>> Please add to the todo list an algorithm checking if geometries
>> intersects but not taking boundries into account (intersects() &&
>> !touches()). It would be used e.g. in rtree traversing in tests for
>> nodes'/boxes containing geometries which may be within some area.
>> Still there is no need to hurry since there is no big difference
>> between this and plain intersects() which is used now.
>>
> Is that not the "within" algorithm? Because "within" means is completely
> within, so should not touch any boundary... But it should then probably
> be implemented for e.g. polygon/box polygon/polygon, for your purposes.
>
> By the way, touches() in OGC perspective means never an intersection, so
> only two borders touching, or a point lying on a border.

I have in mind something like intersects() except it would give false 
for touching geometries.

intersects(B(P(0,0),P(1,1)), B(P(0.5,0.5),P(2,2))) -> true
intersects(B(P(0,0),P(1,1)), B(P(1,1),P(2,2))) -> TRUE (boundry)
intersects(B(P(0,0),P(1,1)), B(P(1.5,1.5),P(2,2))) -> false

Lets say it's weak_intersects (i don't know how it should be called). It 
would give these results:

weak_intersects(B(P(0,0),P(1,1)), B(P(0.5,0.5),P(2,2))) -> true
weak_intersects(B(P(0,0),P(1,1)), B(P(1,1),P(2,2))) -> FALSE (boundry)
weak_intersects(B(P(0,0),P(1,1)), B(P(1.5,1.5),P(2,2))) -> false

I think it corresponds to intersects() && !touches().

If rtree's nodes structure is traversed, at each step there must be 
choosen nodes which will be traversed in the next step. Decision depends 
on passed predicates. If we want to find points within some area, nodes 
intersecting this area must be traversed. But there is no need to 
traverse nodes touching it because there will be no objects in the node 
which are within this area. On boundry yes, but not within.

It's just a little optimization.

Regards,
Adam