Hello,
2011/11/21 Tobias Andersson <xyzto...@hotmail.com>:
> Hi José,
> thank you for your quick reply and sorry for submitting the wrong script in
> my mail. Obviosly it does not make sense to use 'AND' in the first example
> where the polygons are separated.
> Anyway, this is the script I intended to send:
> % This is a script to generate a polygon and plot it in a figure and find
> intersection
> polygons(1).p = [ 2.2 2.2;
> 3.4 3.4;
> 6.3 3.4;
> 5.3 2.8;
> 3.3 2.4];
> polygons(2).p = polygons(1).p + 0.2;
> plot(polygons(1).p(:,1),polygons(1).p(:,2),'*-');
> hold on
> plot(polygons(1).p([end 1],1),polygons(1).p([end 1],2),'*-');
>
> plot(polygons(2).p(:,1),polygons(2).p(:,2),'*-.k');
> plot(polygons(2).p([end 1],1),polygons(2).p([end 1],2),'*:k');
> hold off
> [X,Y,nPol,nInt,nPert] = _oc_polybool(polygons(2).p,polygons(1).p,'AND');
> fprintf('runPolygonShowNonIntersecting.m\n')
> fprintf('Numbers of polygons found: %i\n',nPol)
>
>
> The polygons have an edge that follow the same line. And the result(s) are
> different from time to time:
> The function returns a correct answer most of the time (maybe 9 out of 10
> runs):
> X Y
> NaN NaN
> 6.16666667 3.40000000
> 5.50000000 3.00000000
> 3.50000000 2.60000000
> 2.40000000 2.40000000
> 3.40000000 3.40000000
> 6.16666667 3.40000000
> NaN NaN
> But at some runs the function returns:
> NaN NaN
> 6.16666667 3.40000000
> 6.50000000 3.60000000
> 3.60000000 3.60000000
> 2.40000000 2.40000000
> 3.50000000 2.60000000
> 5.50000000 3.00000000
> 6.16666667 3.40000000
> NaN NaN
>
> Now, I'm not familiar with Greiner-Hormann algorithm and have not really the
> time to go through it. So, can the result of Greiner-Hormann algorithm be
> incorrect when used for polygons that have edges that follow the same line?
> Finally, thanks for the implementation of polygon intersection! It helps a
> lot!
> / Tobias
As explained in http://davis.wpi.edu/~matt/courses/clipping/ the
Greiner-Hormann algorithm is not robust when a vertex or an edge of
the clipping polygon coincides with a point or an edge of the subject
polygon. The trick to overcome singular cases are explained in
Greiner, G.; Hormann, K.: "Efficient Clipping of Arbitrary Polygons",
ACM Trans on Graphics, 1998, and consists in the random perturbation
of the problematic vertex. Thus the results can differ from each run
to another in the special cases
However, OctCLIP had a bug in this special case. Thank you for your
report. I've corrected the bug and now it works correctly. But in the
near future the OctCLIP package will be integrated in the geometry
package, so the new corrected version won't be uploaded to
octave-forge. I maintain the OctCLIP in a mercurial repository in
bitbucket and you can download the new version from
https://bitbucket.org/jgpallero/octclip
You only need to clone the repository, compress in tar.gz the folder
and install as normally. Tell me if you have problems
Cheers
>> Date: Sun, 20 Nov 2011 02:36:46 +0100
>> Subject: Re: [OctDev] Problem with octclip
>> From: jgpall...@gmail.com
>> To: carandraug+...@gmail.com
>> CC: xyzto...@hotmail.com; octave-dev@lists.sourceforge.net
>>
>> 2011/11/20 Carnë Draug <carandraug+...@gmail.com>:
>> > On 19 November 2011 00:40, Tobias Andersson <xyzto...@hotmail.com>
>> > wrote:
>> >> First of all, hi everyone! I'm new here and hope that this is the right
>> >> way
>> >> to post bug reports. Otherwise, please inform me how to do it.
>> >> Now, I installed octclip to find intersections between polygons and
>> >> found an
>> >> odd behaviour when sections of different polygons follow the same line.
>> >> Also, Strange results are returned when a section "touches" a point in
>> >> the
>> >> other polygon.
>> >> The problem is that the result in the first example should be one
>> >> polygon
>> >> and that the result in the second example should be a polygon without
>> >> the
>> >> duplicate point [2.4 2.4].
>> >> I thank you for updating the package or advising me if I think wrong on
>> >> how
>> >> the functionality should be.
>> >>
>> >>
>> >> Two example codes are shown below so that you can rerun the script
>> >> yourselves:
>> >> 1. Sections of different polygons follow the same line:
>> >> % This is a script to generate a polygon and plot it in a figure and
>> >> find
>> >> intersection
>> >> polygons(1).p = [ 2.2 2.2;
>> >> 3.4 3.4;
>> >> 6.3 3.4;
>> >> 5.3 2.8;
>> >> 3.3 2.4];
>> >> polygons(2).p = [ 1.2 2.2;
>> >> 3.4 3.4;
>> >> 5.3 3.4;
>> >> 5.3 2.8;
>> >> 4.4 2.3;
>> >> 3.3 1.7]+5;
>> >> polygons(2).p = polygons(2).p + [1*ones(size(polygons(2).p,1),1)
>> >> 0*ones(size(polygons(2).p,1),1)];
>> >> plot(polygons(1).p(:,1),polygons(1).p(:,2),'*-');
>> >> hold on
>> >> plot(polygons(1).p([end 1],1),polygons(1).p([end 1],2),'*-');
>> >>
>> >> plot(polygons(2).p(:,1),polygons(2).p(:,2),'*-.k');
>> >> plot(polygons(2).p([end 1],1),polygons(2).p([end 1],2),'*:k');
>> >> hold off
>> >> [X,Y,nPol,nInt,nPert] =
>> >> _oc_polybool(polygons(2).p,polygons(1).p,'AND');
>> >> fprintf('runPolygonShowNonIntersecting.m\n')
>> >> fprintf('Numbers of polygons found: %i\n',nPol)
>> >>
>> >>
>> >> 2. A section "touches" a point in the other polygon:
>> >> % This is a script to generate a polygon and plot it in a figure and
>> >> find
>> >> intersection
>> >> polygons(1).p = [ 2.2 2.2;
>> >> 3.4 3.4;
>> >> 6.3 3.4;
>> >> 5.3 2.8;
>> >> 3.3 2.4];
>> >> polygons(2).p = [ 1.2 2.2;
>> >> 3.4 3.4;
>> >> 5.3 3.4;
>> >> 5.3 2.8;
>> >> 4.4 2.3;
>> >> 3.3 1.7]+0.2;
>> >> polygons(2).p = polygons(2).p + [1*ones(size(polygons(2).p,1),1)
>> >> 0*ones(size(polygons(2).p,1),1)];
>> >> plot(polygons(1).p(:,1),polygons(1).p(:,2),'*-');
>> >> hold on
>> >> plot(polygons(1).p([end 1],1),polygons(1).p([end 1],2),'*-');
>> >>
>> >> plot(polygons(2).p(:,1),polygons(2).p(:,2),'*-.k');
>> >> plot(polygons(2).p([end 1],1),polygons(2).p([end 1],2),'*:k');
>> >> hold off
>> >> [X,Y,nPol,nInt,nPert] =
>> >> _oc_polybool(polygons(2).p,polygons(1).p,'AND');
>> >> fprintf('runPolygonShowNonIntersecting.m\n')
>> >> fprintf('Numbers of polygons found: %i\n',nPol)
>> >
>> > Hi Tobias
>> >
>> > do you think you can submit a patch? Anyway, I'm also sending this
>> > e-mail to the dev who wrote this function, he's probably the best
>> > person to fix anything about the package.
>> >
>> > Carnë
>> >
>>
>> Hello,
>>
>> Tobias, I don't understand when you say that in the first example the
>> result should be one polygon. You perform the 'AND' operation but the
>> two polygons in your example are disjoints, so they have no
>> intersection. The second example runs well for me. Please, see the
>> attached *.png files with the results of your examples in my computer
>> (in the second one I have added in red the resulting polygon).
>>
>> Take in account too that I implement the Greiner-Hormann algorithm
>> which is not robust when a point or an edge of one polygon coincides
>> with a point or an edge of the other. Please, see
>> http://davis.wpi.edu/~matt/courses/clipping/ for more details.
>>
>> About OctCLIP, you should use the oc_polybool function (is a *.m
>> script) instead of the _oc_polybool one (is the *.oct function)
>>
>> Cheers
>>
>> --
>> *****************************************
>> José Luis García Pallero
>> jgpall...@gmail.com
>> (o<
>> / / \
>> V_/_
>> Use Debian GNU/Linux and enjoy!
>> *****************************************
>
--
*****************************************
José Luis García Pallero
jgpall...@gmail.com
(o<
/ / \
V_/_
Use Debian GNU/Linux and enjoy!
*****************************************
------------------------------------------------------------------------------
All the data continuously generated in your IT infrastructure
contains a definitive record of customers, application performance,
security threats, fraudulent activity, and more. Splunk takes this
data and makes sense of it. IT sense. And common sense.
http://p.sf.net/sfu/splunk-novd2d
_______________________________________________
Octave-dev mailing list
Octave-dev@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/octave-dev
