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

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