# Geometry :

Subject: Re: [geometry] Ring intersection question
From: Menelaos Karavelas (menelaos.karavelas_at_[hidden])
Date: 2014-11-06 17:31:50

Hi Will.

On 07/11/2014 12:10 ??, Menelaos Karavelas wrote:
> Hi Will.
>
> On 06/11/2014 11:56 ??, Will Lucas wrote:
>> On Thu, Nov 6, 2014 at 3:47 PM, Menelaos Karavelas
>> <menelaos.karavelas_at_[hidden] <mailto:menelaos.karavelas_at_[hidden]>>
>> wrote:
>>
>> Yet one more comment.
>>
>>
>> On 06/11/2014 11:44 ??, Menelaos Karavelas wrote:
>>> Hi again.
>>>
>>> On 06/11/2014 11:34 ??, Menelaos Karavelas wrote:
>>>> Hi Will.
>>>>
>>>> On 06/11/2014 11:26 ??, Will Lucas wrote:
>>>>> On Thu, Nov 6, 2014 at 3:07 PM, Menelaos Karavelas
>>>>> <menelaos.karavelas_at_[hidden]
>>>>> <mailto:menelaos.karavelas_at_[hidden]>> wrote:
>>>>>
>>>>> Dear Will,
>>>>>
>>>>> I tried your polygons and the intersection seems to work.
>>>>> Please checkout the attached program, and let us know if
>>>>> you get a similar output. The output that I get is:
>>>>> MULTIPOLYGON(((75 150,250 150,250 75,75 75,75 150)))
>>>>>
>>>>> Best,
>>>>>
>>>>> - m.
>>>>>
>>>>>
>>>>> On 06/11/2014 10:44 ??, Will Lucas wrote:
>>>>>> Hi all,
>>>>>>
>>>>>> I have a question regarding the intersection of ring
>>>>>> concepts using Boost.Geometry. I currently have two
>>>>>> overlapping rectangles defined by the following WKTs:
>>>>>>
>>>>>> POLYGON((75 75,75 175,275 175,275 75,75 75))
>>>>>> POLYGON((50 50,50 150,250 150,250 50,50 50))
>>>>>>
>>>>>> When I perform the intersection of these rectangles, I
>>>>>> get the intersection points:
>>>>>>
>>>>>> POLYGON((75 150,250 75))
>>>>>>
>>>>>> The intersection points do not allow me to compute the
>>>>>> area correctly after the intersection. Is there way to
>>>>>> get a fully valid ring/polygon out of intersection, so
>>>>>> that the area will be equal to the overlapping region?
>>>>>>
>>>>>> Thanks!
>>>>>> Will
>>>>>>
>>>>>>
>>>>>> _______________________________________________
>>>>>> Geometry mailing list
>>>>>> Geometry_at_[hidden] <mailto:Geometry_at_[hidden]>

>>>>>
>>>>>
>>>>> _______________________________________________
>>>>> Geometry mailing list
>>>>> Geometry_at_[hidden] <mailto:Geometry_at_[hidden]>

>>>>>
>>>>>
>>>>> Menelaos,
>>>>>
>>>>> Thanks for the quick response! I have tested your code, and it
>>>>> correctly outputs
>>>>>
>>>>> MULTIPOLYGON(((75 150,250 150,250 75,75 75,75 150)))
>>>>>
>>>>> I had to comment out the is_valid calls as I'm running the
>>>>> Ubuntu package (boost 1.54.0), which doesn't contain that
>>>>> helper method.
>>>>>
>>>>
>>>> Sure, this was just a sanity test.
>>>>
>>>>> I'm guess the problem may be my re-mapping of the OpenCV
>>>>> data-types. Here is what I currently am working with

>>>>>
>>>>> Do I need to define a polygon wrapper for the custom Contour
>>>>> type I have?
>>>>
>>>> I think that the problem is that your intersection output type
>>>> should be a multipolygon rather than a ring/polygon. Please
>>>> checkout the relevant doc page:

>>>>
>>>> Try replacing the intersection output type by a multipolygon,
>>>> or a vector/deque of polygons and see what the output is.
>>>>
>>>
>>> Please see the updated attached program. I added one more call
>>> to bg::intersection specifying a ring as the output (like you
>>> do), and I get the result you get. I am now convinced that the
>>> problem is what I describe above.
>>>
>>
>> I think what is happening is that the BG code understands your
>> ring as a container of points (a multipoint/vector of
>> points/etc), rather than a multipolygon, in which case it is
>> setup to output just the intersection points.
>>
>> - m.
>>
>>> All the best,
>>>
>>> - m.
>>>
>>>> - m.
>>>>
>>>>>
>>>>>
>>>>> _______________________________________________
>>>>> Geometry mailing list
>>>>> Geometry_at_[hidden] <mailto:Geometry_at_[hidden]>

>>>>
>>>
>>
>>
>> _______________________________________________
>> Geometry mailing list
>> Geometry_at_[hidden] <mailto:Geometry_at_[hidden]>

>>
>>
>> So, it sounds as if I should follow along with this custom polygon
>> example?

>>
>
> Yes.
>
>> This would hopefully allow me to define a custom multi_polygon. As my
>> initial attempt to just create an std::vector<dft::Contour> as a
>> multi_polygon, resulted in a bunch of compiler complaints :D
>>
>
> I think this is because your vector's value type is a ring rather than
> a polygon.
>
>> For my specific problem, I'm not concerned with "holes" that may
>> exist in a polygon (I actually indicate to OpenCV, to only return the
>> exterior contours to me). Is there a way to indicate to BG that only
>> exterior contours are used via the polygon traits?
>
> I think that one way is to define your polygon type such that it
> always has an empty container for the interior rings (holes).
> Registering such a polygon should do what you want.
>

I am having second thoughts about my proposal above.

What you need is to register your custom polygon type. This polygon type
will be used to either register a multipolygon or as the value type of a
container (vector/deque/etc.), which will then be passed to
bg::intersection.

The intersection algorithm expects a real polygon, so it might be the
case that the fake/ring-like polygon I suggested may not work correctly
with bg::intersection if it cannot store interior rings.
On the other hand if your input to bg::intersection is just the outer
rings of polygons, then their intersection cannot really produce holes,
so it could well be the case that bg::intersection works nicely with the
fake/ring-like polygons I suggested.

So, I guess, the safe way is to fully register your polygons and then
call bg::intersection using only their exterior rings.
Then you can try to modify your custom polygon to never store interior
rings, and see if this works with bg::intersection.
I do not have the time to try this right away (use these fake/ring-like
polygons in bg::intersection), but I would be very interested in knowing
if it works (assuming you want/have the time to try it).

Assuming that the solution with fake/ring-like polygons works, I see the
two solutions as equivalent from the performance point of view.

Best,

- m.

> The other option is to pass to the intersection algorithm only the
> exterior ring of your polygons. Please take a look at the
> documentation for bg::exterior_ring (there is a const and a non-const
> version):

>
> Best,
>
> - m.
>
>>
>> I suppose worst case I can copy from OpenCV to BG data-structures,
>> but that doesn't seem as elegant :)
>>
>> Will
>>
>>
>> _______________________________________________
>> Geometry mailing list
>> Geometry_at_[hidden]

>

Geometry list run by mateusz at loskot.net