# Geometry :

Subject: Re: [geometry] Ring intersection question
From: Will Lucas (wlucas_at_[hidden])
Date: 2014-11-06 18:29:31

On Thu, Nov 6, 2014 at 4:31 PM, Menelaos Karavelas <
menelaos.karavelas_at_[hidden]> wrote:

> 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]> 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]> 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 listGeometry_at_[hidden]http://lists.boost.org/mailman/listinfo.cgi/geometry
>>>
>>>
>>>
>>> _______________________________________________
>>> Geometry mailing list
>>> 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 listGeometry_at_[hidden]http://lists.boost.org/mailman/listinfo.cgi/geometry
>>
>>
>>
>>
>>
>> _______________________________________________
>> Geometry mailing list
>> 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 listGeometry_at_[hidden]http://lists.boost.org/mailman/listinfo.cgi/geometry
>
>
>
>
> _______________________________________________
> Geometry mailing list
> Geometry_at_[hidden]

>
>
Hi Menelaos,

Thanks so much for the help! It really helped get me over this hurdle! I
tried registering the OpenCV Contour (std::vector<cv::Point>) type to a BG
polygon and got multiple definition errors due to the ring already being a
tagged type to BG. It seems like the only way around that was to add a
struct that had a Contour inside, and register that new datatype. So,
rather than adding an additional datatype, I ended up just copying the
OpenCV types to BG ones. While not the most elegant solution, it is working
perfectly now!

Thanks again!
Will

Geometry list run by mateusz at loskot.net