Bug #26675 for Math-Polygon: polygon intersection

Wed Apr 25 21:45:06 2007 ville9 [...] softpres.org - Ticket created

Subject:

polygon intersection

I'd like to have something like $poly->intersect($other_poly) which returns a new Math::Polygon object representing the intersection of $poly and $other_poly, or undef if both polygons don't intersect. Do you have planned something like this? Regards, Christian

Thu Apr 26 03:31:04 2007 solutions [...] overmeer.net - Correspondence added

Subject:	Re: [rt.cpan.org #26675] polygon intersection
Date:	Thu, 26 Apr 2007 09:30:38 +0200
To:	Christian Sauer via RT <bug-Math-Polygon [...] rt.cpan.org>
From:	Mark Overmeer <solutions [...] overmeer.net>

* Christian Sauer via RT (bug-Math-Polygon@rt.cpan.org) [070426 01:45]: Show quoted text

> I'd like to have something like $poly->intersect($other_poly) which > returns a new Math::Polygon object representing the intersection of > $poly and $other_poly, or undef if both polygons don't intersect. > > Do you have planned something like this?

At least, this will return a (maybe empty) LIST of objects in the general case. No, I have no plans for this, but if you show me the algorithm (maybe limited to convex polys, for which you test), I will add it. I do require some tests and docs as well. Is not easy. -- MarkOv ------------------------------------------------------------------------ Mark Overmeer MSc MARKOV Solutions drs Mark A.C.J. Overmeer MARKOV Solutions Mark@Overmeer.net solutions@overmeer.net http://Mark.Overmeer.net http://solutions.overmeer.net

Thu Apr 26 03:31:05 2007 The RT System itself - Status changed from 'new' to 'open'

Thu Apr 26 21:20:31 2007 ville9 [...] softpres.org - Correspondence added

From:

ville9 [...] softpres.org

On Do. 26. Apr. 2007, 03:31:04, solutions@overmeer.net wrote: Show quoted text

> * Christian Sauer via RT (bug-Math-Polygon@rt.cpan.org) [070426 01:45]:

> > I'd like to have something like $poly->intersect($other_poly) which > > returns a new Math::Polygon object representing the intersection of > > $poly and $other_poly, or undef if both polygons don't intersect. > > > > Do you have planned something like this?

> > At least, this will return a (maybe empty) LIST of objects in the > general case. > > No, I have no plans for this, but if you show me the algorithm (maybe > limited to convex polys, for which you test), I will add it. I do > require some tests and docs as well. Is not easy.

Sorry, I don't have an algorithm yet - but I found that paper: http://citeseer.ist.psu.edu/cache/papers/cs/25021/http:zSzzSzfractal.dam.fmph.uniba.skzSz~sccgzSzproceedingszSz1998zSzZalik.pdf/zalik98quick.pdf A limitation to convex polygons would be ok of course! Regards, Christian

Fri Apr 27 03:41:00 2007 solutions [...] overmeer.net - Correspondence added

Subject:	Re: [rt.cpan.org #26675] polygon intersection
Date:	Fri, 27 Apr 2007 09:40:40 +0200
To:	Christian Sauer via RT <bug-Math-Polygon [...] rt.cpan.org>
From:	Mark Overmeer <solutions [...] overmeer.net>

* Christian Sauer via RT (bug-Math-Polygon@rt.cpan.org) [070427 01:20]: Show quoted text

> Ticket <URL: http://rt.cpan.org/Ticket/Display.html?id=26675 > > > Sorry, I don't have an algorithm yet - but I found that paper: > http://citeseer.ist.psu.edu/cache/papers/cs/25021/http:zSzzSzfractal.dam.fmph.uniba.skzSz~sccgzSzproceedingszSz1998zSzZalik.pdf/zalik98quick.pdf

Looks like a nice project for a long Winter-evening. Probably a few of them. I'll not be the one who implements and tests this: too many other modules which have higher priorities. If you (can find someone) create the perl implementation an tests, then I will glue that into the package nicely. -- Regards, MarkOv ------------------------------------------------------------------------ Mark Overmeer MSc MARKOV Solutions Mark@Overmeer.net solutions@overmeer.net http://Mark.Overmeer.net http://solutions.overmeer.net

Sat Apr 28 11:47:45 2007 ville9 [...] softpres.org - Correspondence added

From:

ville9 [...] softpres.org

On Fr. 27. Apr. 2007, 03:41:00, solutions@overmeer.net wrote: Show quoted text

> * Christian Sauer via RT (bug-Math-Polygon@rt.cpan.org) [070427 > 01:20]:

> > Ticket <URL: http://rt.cpan.org/Ticket/Display.html?id=26675 > > > > > Sorry, I don't have an algorithm yet - but I found that paper: > >

>

http://citeseer.ist.psu.edu/cache/papers/cs/25021/http:zSzzSzfractal.dam.fmph.uniba.skzSz~sccgzSzproceedingszSz1998zSzZalik.pdf/zalik98quick.pdf Show quoted text

> > Looks like a nice project for a long Winter-evening. Probably a few > of > them. > > I'll not be the one who implements and tests this: too many other > modules > which have higher priorities. If you (can find someone) create the > perl > implementation an tests, then I will glue that into the package > nicely.

Ok, it's really not trivial and I understand you. :) Currently I can get along with a combination of rotate() and fillClip1() as one of the polygons that I need to intersect is always a (rotated) rectangle. And I'll try to implement a more generic intersection algorithm when needed... Regards, Christian