Quantcast

Minowski sum for non-polygons?

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

Minowski sum for non-polygons?

KHartmann
Hi,

Is there a way to get the Minowski sum for a two-D path and a circular disc?  I would like the result to be a two-D polygon.  Or is there another way to do this?  (Without using Minowski sum?)

Here are some picture examples.  (My input would be the centerlines [and a disc width].  The output would be the boundary.)
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Minowski sum for non-polygons?

Efi Fogel
You can compute the exact offset of a polygon or an approximation using CGAL::offset_polygon_2() or CGAL::approximated_offset_2(), respectively. Your problem is similar. The difference is that your polygons degenerate to polylines. I haven't tried it out, but conceptually you should be able to use the functions above. If it doesn't work, let us know, and we might be able to make it work.

   ____  _        ____             _
  /_____/_) o    /__________  __  //
 (____ (   (    (    (_/ (_/-(-'_(/
                         _/



On Tue, Dec 20, 2016 at 5:14 PM, KHartmann <[hidden email]> wrote:
Hi,

Is there a way to get the Minowski sum for a two-D path and a circular disc?
I would like the result to be a two-D polygon.  Or is there another way to
do this?  (Without using Minowski sum?)

Here are some picture examples.  (My input would be the centerlines [and a
disc width].  The output would be the boundary.)
<http://cgal-discuss.949826.n4.nabble.com/file/n4662427/MinSum.jpg>



--
View this message in context: http://cgal-discuss.949826.n4.nabble.com/Minowski-sum-for-non-polygons-tp4662427.html
Sent from the cgal-discuss mailing list archive at Nabble.com.

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss



Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Minowski sum for non-polygons?

KHartmann
Thanks Efi.

I tried using CGAL::approximated_offset_2().

But I can't figure out how to pass it a polyline instead of a polygon.

I create my polygon_2 by push_back()ing vertices.  But cgal always assumes that
the polygon boundary is closed.  I don't know how to tell cgal that the polygon_2 boundary isn't closed.

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Minowski sum for non-polygons?

Efi Fogel
You need to provide a degenerate polygon of zero area, so you you start with the polyline itself, and then provide it again in reverse order without the first and last.

   ____  _        ____             _
  /_____/_) o    /__________  __  //
 (____ (   (    (    (_/ (_/-(-'_(/
                         _/



On Wed, Dec 21, 2016 at 9:59 PM, KHartmann <[hidden email]> wrote:
Thanks Efi.

I tried using CGAL::approximated_offset_2().

But I can't figure out how to pass it a polyline instead of a polygon.

I create my polygon_2 by push_back()ing vertices.  But cgal always assumes
that
the polygon boundary is closed.  I don't know how to tell cgal that the
polygon_2 boundary isn't closed.





--
View this message in context: http://cgal-discuss.949826.n4.nabble.com/Minowski-sum-for-non-polygons-tp4662427p4662429.html
Sent from the cgal-discuss mailing list archive at Nabble.com.

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss



Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Minowski sum for non-polygons?

KHartmann
Hi Efi,

An exception is raised for that type of degenerate polygon.

    CGAL_precondition (pgn.is_simple());

The first test in "bool is_simple_polygon(...)" checks for duplicate vertices.
Which our degenerate polygon fails.
(Then I think it tests for intersecting edges.)

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Minowski sum for non-polygons?

Efi Fogel
Remove the assertion statement(s), and try again. There are 3 different functions that can be used to compute the Minkowski sum. Perhaps one will work.
If none work compute the union of the Minkowski sums of  the line segments that comprise the polyline and the polygon. Here you will have to compute the Minkowski sum of a single segment, which is a degenerate polygon, and another polygon. Again, try all 3 versions and remove the assertion statements if necessary.

   ____  _        ____             _
  /_____/_) o    /__________  __  //
 (____ (   (    (    (_/ (_/-(-'_(/
                         _/



On Thu, Dec 22, 2016 at 4:24 PM, KHartmann <[hidden email]> wrote:
Hi Efi,

An exception is raised for that type of degenerate polygon.

    CGAL_precondition (pgn.is_simple());

The first test in "bool is_simple_polygon(...)" checks for duplicate
vertices.
Which our degenerate polygon fails.
(Then I think it tests for intersecting edges.)





--
View this message in context: http://cgal-discuss.949826.n4.nabble.com/Minowski-sum-for-non-polygons-tp4662427p4662433.html
Sent from the cgal-discuss mailing list archive at Nabble.com.

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss



Loading...