Ring intersection question

classic Classic list List threaded Threaded
12 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Ring intersection question

Will Lucas
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
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Ring intersection question

Menelaos Karavelas
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
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry


_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry

polygon_intersection.cpp (681 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Ring intersection question

Will Lucas
On Thu, Nov 6, 2014 at 3:07 PM, Menelaos Karavelas <[hidden email]> 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
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry


_______________________________________________
Geometry mailing list
[hidden email]
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.

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?

_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Ring intersection question

Menelaos Karavelas
Hi Will.

On 06/11/2014 11:26 μμ, Will Lucas wrote:
On Thu, Nov 6, 2014 at 3:07 PM, Menelaos Karavelas <[hidden email]> 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
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry


_______________________________________________
Geometry mailing list
[hidden email]
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

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.

- m.



_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry


_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Ring intersection question

Menelaos Karavelas
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 <[hidden email]> 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
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry


_______________________________________________
Geometry mailing list
[hidden email]
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

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.

All the best,

- m.

- m.



_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry



_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry

polygon_intersection.cpp (837 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Ring intersection question

Menelaos Karavelas
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 <[hidden email]> 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
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry


_______________________________________________
Geometry mailing list
[hidden email]
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

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
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry




_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Ring intersection question

Will Lucas
On Thu, Nov 6, 2014 at 3:47 PM, Menelaos Karavelas <[hidden email]> 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 <[hidden email]> 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
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry


_______________________________________________
Geometry mailing list
[hidden email]
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

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
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry




_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry


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

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

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 suppose worst case I can copy from OpenCV to BG data-structures, but that doesn't seem as elegant :)

Will

_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Ring intersection question

Menelaos Karavelas
Hi Will.

On 06/11/2014 11:56 μμ, Will Lucas wrote:
On Thu, Nov 6, 2014 at 3:47 PM, Menelaos Karavelas <[hidden email]> 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 <[hidden email]> 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
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry


_______________________________________________
Geometry mailing list
[hidden email]
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

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
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry




_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry


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.

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
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry


_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Ring intersection question

Menelaos Karavelas
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 <[hidden email]> 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 <[hidden email]> 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
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry


_______________________________________________
Geometry mailing list
[hidden email]
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

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
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry




_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry


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):
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
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry



_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Ring intersection question

Will Lucas
On Thu, Nov 6, 2014 at 4:31 PM, Menelaos Karavelas <[hidden email]> 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 <[hidden email]> 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 <[hidden email]> 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
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry


_______________________________________________
Geometry mailing list
[hidden email]
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

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
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry




_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry


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):
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
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry



_______________________________________________
Geometry mailing list
[hidden email]
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

_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Ring intersection question

Adam Wulkiewicz
In reply to this post by Menelaos Karavelas
Hi,

Menelaos Karavelas wrote:
On 07/11/2014 12:10 πμ, Menelaos Karavelas wrote:
On 06/11/2014 11:56 μμ, Will Lucas wrote:

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.

Actually this works for me. Though since a container of Rings isn't a "proper" Geometry other functions may not work with it, e.g. bg::wkt() from your example.
My code:

#include <boost/foreach.hpp>
#include <boost/geometry.hpp>

    
namespace bg = boost::geometry;

    
typedef bg::model::point<int, 2, bg::cs::cartesian> point_type;
typedef bg::model::ring<point_type> ring_type;
typedef std::vector<ring_type> rings_container;

    
int main()
{
    ring_type pol1, pol2;
    bg::read_wkt("POLYGON((75 75,75 175,275 175,275 75,75 75))", pol1);
    bg::read_wkt("POLYGON((50 50,50 150,250 150,250 50,50 50))", pol2);

    
    rings_container rings;
    bg::intersection(pol1, pol2, rings);
    BOOST_FOREACH(ring_type const& r, rings)
        std::cout << bg::wkt(r) << std::endl;
    return 0;
}

    FYI, it compiles also if the input Geometries are Polygons. I tried
    this:

polygon_type pol1, pol2;
bg::read_wkt("POLYGON((0 0,0 10,10 10,10 0,0 0),(4 4,6 4,6 6,4 6,4 4))", pol1);
bg::read_wkt("POLYGON((1 1,1 11,11 11,11 1,1 1))", pol2);

    
rings_container rings;
bg::intersection(pol1, pol2, rings);
BOOST_FOREACH(ring_type const& r, rings)
    std::cout << bg::wkt(r) << std::endl;

    
bg::intersection(pol2, pol1, rings);
BOOST_FOREACH(ring_type const& r, rings)
    std::cout << bg::wkt(r) << std::endl;

In this case holes aren't included in the output:

POLYGON((1 10,10 10,10 1,1 1,1 10))
POLYGON((1 10,10 10,10 1,1 1,1 10))

Is this behavior intended?

Regards,
Adam


_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Ring intersection question

Barend
Hi Adam,


Adam Wulkiewicz wrote On 7-11-2014 0:33:
Hi,

Menelaos Karavelas wrote:
On 07/11/2014 12:10 πμ, Menelaos Karavelas wrote:
On 06/11/2014 11:56 μμ, Will Lucas wrote:

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.

Actually this works for me. Though since a container of Rings isn't a "proper" Geometry other functions may not work with it, e.g. bg::wkt() from your example.
My code:

#include <boost/foreach.hpp>
#include <boost/geometry.hpp>
namespace bg = boost::geometry;
typedef bg::model::point<int, 2, bg::cs::cartesian> point_type;
typedef bg::model::ring<point_type> ring_type;
typedef std::vector<ring_type> rings_container;
int main()
{
    ring_type pol1, pol2;
    bg::read_wkt("POLYGON((75 75,75 175,275 175,275 75,75 75))", pol1);
    bg::read_wkt("POLYGON((50 50,50 150,250 150,250 50,50 50))", pol2);
    rings_container rings;
    bg::intersection(pol1, pol2, rings);
    BOOST_FOREACH(ring_type const& r, rings)
        std::cout << bg::wkt(r) << std::endl;
    return 0;
}
FYI, it compiles also if the input Geometries are Polygons. I tried this:

polygon_type pol1, pol2;
bg::read_wkt("POLYGON((0 0,0 10,10 10,10 0,0 0),(4 4,6 4,6 6,4 6,4 4))", pol1);
bg::read_wkt("POLYGON((1 1,1 11,11 11,11 1,1 1))", pol2);
rings_container rings;
bg::intersection(pol1, pol2, rings);
BOOST_FOREACH(ring_type const& r, rings)
    std::cout << bg::wkt(r) << std::endl;
bg::intersection(pol2, pol1, rings);
BOOST_FOREACH(ring_type const& r, rings)
    std::cout << bg::wkt(r) << std::endl;

In this case holes aren't included in the output:

POLYGON((1 10,10 10,10 1,1 1,1 10))
POLYGON((1 10,10 10,10 1,1 1,1 10))

Is this behavior intended?

Yes, it is. Holes are skipped for rings. There are also unit tests for this.

Regards, Barend


_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry
Loading...