Geometry Boost List: Re: [geometry] Ring intersection question

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]>
>>>>>>         http://lists.boost.org/mailman/listinfo.cgi/geometry
>>>>>
>>>>>
>>>>>         _______________________________________________
>>>>>         Geometry mailing list
>>>>>         Geometry_at_[hidden] <mailto:Geometry_at_[hidden]>
>>>>>         http://lists.boost.org/mailman/listinfo.cgi/geometry
>>>>>
>>>>>
>>>>>     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
>>>>>     https://gist.github.com/wlucas-DFT/0b8e1e07f34ee7e489c6
>>>>>
>>>>>     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:
>>>>     http://www.boost.org/doc/libs/1_56_0/libs/geometry/doc/html/geometry/reference/algorithms/intersection.html
>>>>
>>>>     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]>
>>>>>     http://lists.boost.org/mailman/listinfo.cgi/geometry
>>>>
>>>
>>
>>
>>     _______________________________________________
>>     Geometry mailing list
>>     Geometry_at_[hidden] <mailto:Geometry_at_[hidden]>
>>     http://lists.boost.org/mailman/listinfo.cgi/geometry
>>
>>
>> So, it sounds as if I should follow along with this custom polygon 
>> example?
>> https://github.com/boostorg/geometry/blob/master/example/c06_custom_polygon_example.cpp
>>
>
> 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):
> http://www.boost.org/doc/libs/1_57_0/libs/geometry/doc/html/geometry/reference/access/exterior_ring/exterior_ring_1.html
> http://www.boost.org/doc/libs/1_57_0/libs/geometry/doc/html/geometry/reference/access/exterior_ring/exterior_ring_1_const_version.html
>
> 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]
>> http://lists.boost.org/mailman/listinfo.cgi/geometry
>