plplot-devel

[Plplot-devel] Bug in notcrossed() function of plfill.c

[Phil R. <p.d...@gm...>]

 Hi All
I have just been dealing with a bug where I was drawing a contour plot
and my entire plot was being filled with one contour level. I have
fought my way through the code and it turned out to be a perfect storm
of a bug which begins with the notcrossed function returning a
PL_NEAR_PARALLEL status for two lines which are actually near
perpendicular (and cross) which then causes the top left corner of my
plot to be incorrectly labelled as inside a fill region. However
because the fill region is actually outside the plot plplot sees no
intersections with the plot boundaries so checks if the top left
corner of the plot is inside the fill region. In this case it sees
that it is flagged as inside so assumes the whole plot must be inside
and fills the whole plot.

I have fixed my code, but I actually don't understand the exixting
logic inside notcrossed(). This might be because it is an error or it
might be because I just don't get it. So before I push my change I
just wanted to check if whoever authored this function is still
around?

Phil

Re: [Plplot-devel] Bug in notcrossed() function of plfill.c

[Arjen M. <Arj...@de...>]

Hi Phil,



I do not remember who wrote it, I may have made some changes to it in a now distant past, but I could have a look at your fix.



Regards,



Arjen



> -----Original Message-----
> From: Phil Rosenberg [mailto:p.d...@gm...]
> Sent: Monday, June 15, 2015 11:35 AM
> To: plp...@li...
> Subject: [Plplot-devel] Bug in notcrossed() function of plfill.c
>
>  Hi All
> I have just been dealing with a bug where I was drawing a contour plot and my entire
> plot was being filled with one contour level. I have fought my way through the code
> and it turned out to be a perfect storm of a bug which begins with the notcrossed
> function returning a PL_NEAR_PARALLEL status for two lines which are actually
> near perpendicular (and cross) which then causes the top left corner of my plot to be
> incorrectly labelled as inside a fill region. However because the fill region is actually
> outside the plot plplot sees no intersections with the plot boundaries so checks if the
> top left corner of the plot is inside the fill region. In this case it sees that it is flagged
> as inside so assumes the whole plot must be inside and fills the whole plot.
>
> I have fixed my code, but I actually don't understand the exixting logic inside
> notcrossed(). This might be because it is an error or it might be because I just don't
> get it. So before I push my change I just wanted to check if whoever authored this
> function is still around?
>
> Phil
>
> ------------------------------------------------------------------------------
> _______________________________________________
> Plplot-devel mailing list
> Plp...@li...
> https://lists.sourceforge.net/lists/listinfo/plplot-devel

DISCLAIMER: This message is intended exclusively for the addressee(s) and may contain confidential and privileged information. If you are not the intended recipient please notify the sender immediately and destroy this message. Unauthorized use, disclosure or copying of this message is strictly prohibited. The foundation 'Stichting Deltares', which has its seat at Delft, The Netherlands, Commercial Registration Number 41146461, is not liable in any way whatsoever for consequences and/or damages resulting from the improper, incomplete and untimely dispatch, receipt and/or content of this e-mail.

Re: [Plplot-devel] Bug in notcrossed() function of plfill.c

[Phil R. <p.d...@gm...>]

Hi Arjen

I've just copied the code below as I don't just have time at the
moment to sort a git patch (The plot I was making is for a
presentation this afternoon!).  The old code has been commented out
with /* */ and my new code is directly above that from the #ifdef
onwards.

Basically I get that the variable factor will be zero for parallel
lines and I get that there is a precision limit on that due to
floating point rounding. However I don't understand how factor_NBCC
works as a test.

For the bug in question the inputs were xA1=20994, yA1=12219,
xA2=4915, yA2=12561 xB1=20979, yB1=12219, xB2=20979, yB2=12221.
Although perhaps the As and Bs were reversed, but the flagging should
be identical.

Phil


Code Below:

int

notcrossed( PLINT * xintersect, PLINT * yintersect,

PLINT xA1, PLINT yA1, PLINT xA2, PLINT yA2,

PLINT xB1, PLINT yB1, PLINT xB2, PLINT yB2 )

{

PLFLT factor, factor_NBCC, fxintersect, fyintersect, limit;

// These variables are PLFLT not for precision, but to

// avoid integer overflows if they were typed as PLINT.

PLFLT xA2A1, yA2A1, xB2B1, yB2B1;

PLFLT xB1A1, yB1A1, xB2A1, yB2A1;

PLINT status = 0;

//

// Two linear equations to be solved for x and y.

// y = ((x - xA1)*yA2 + (xA2 - x)*yA1)/(xA2 - xA1)

// y = ((x - xB1)*yB2 + (xB2 - x)*yB1)/(xB2 - xB1)

//

// Transform those two equations to coordinate system with origin

// at (xA1, yA1).

// y' = x'*yA2A1/xA2A1

// y' = ((x' - xB1A1)*yB2A1 + (xB2A1 - x')*yB1A1)/xB2B1

// ==>

// x' = -(

// (-xB1A1*yB2A1 + xB2A1*yB1A1)/xB2B1)/

// (yB2B1/xB2B1 - yA2A1/xA2A1)

// = (xB1A1*yB2A1 - xB2A1*yB1A1)*xA2A1/

// (xA2A1*yB2B1 - yA2A1*xB2B1)

//

//

xA2A1 = xA2 - xA1;

yA2A1 = yA2 - yA1;

xB2B1 = xB2 - xB1;

yB2B1 = yB2 - yB1;

factor = xA2A1 * yB2B1 - yA2A1 * xB2B1;

#ifdef PL_DOUBLE

limit= sqrt( FLT_MIN );

#else

limit = sqrt( DBL_MIN );

#endif

if( factor == 0 )

status = status | PL_PARALLEL;

else if( fabs( factor ) < limit )

status = status | PL_NEAR_PARALLEL;

/*factor_NBCC = PL_NBCC * ( fabs( xA2A1 ) + fabs( yB2B1 ) + fabs(
yA2A1 ) + fabs( xB2B1 ) );

if ( fabs( factor ) <= factor_NBCC )

{

if ( fabs( factor ) > 0. )

status = status | PL_NEAR_PARALLEL;

else

status = status | PL_PARALLEL;

}*/

else

{

xB1A1 = xB1 - xA1;

yB1A1 = yB1 - yA1;

xB2A1 = xB2 - xA1;

yB2A1 = yB2 - yA1;

factor = ( xB1A1 * yB2A1 - yB1A1 * xB2A1 ) / factor;

fxintersect = factor * xA2A1 + xA1;

fyintersect = factor * yA2A1 + yA1;

// The "redundant" x and y segment range checks (which include near the

// end points) are needed for the vertical and the horizontal cases.

if ( ( BETW_NBCC( fxintersect, xA1, xA2 ) && BETW_NBCC( fyintersect,
yA1, yA2 ) ) &&

( BETW_NBCC( fxintersect, xB1, xB2 ) && BETW_NBCC( fyintersect, yB1, yB2 ) ) )

{

// The intersect is close (within +/- PL_NBCC) to an end point or

// corresponds to a definite crossing of the two line segments.

// Find out which.

if ( fabs( fxintersect - xA1 ) <= PL_NBCC && fabs( fyintersect - yA1 )
<= PL_NBCC )

status = status | PL_NEAR_A1;

else if ( fabs( fxintersect - xA2 ) <= PL_NBCC && fabs( fyintersect -
yA2 ) <= PL_NBCC )

status = status | PL_NEAR_A2;

else if ( fabs( fxintersect - xB1 ) <= PL_NBCC && fabs( fyintersect -
yB1 ) <= PL_NBCC )

status = status | PL_NEAR_B1;

else if ( fabs( fxintersect - xB2 ) <= PL_NBCC && fabs( fyintersect -
yB2 ) <= PL_NBCC )

status = status | PL_NEAR_B2;

// N.B. if none of the above conditions hold then status remains at

// zero to signal we have a definite crossing.

}

else

status = status | PL_NOT_CROSSED;

}

if ( !status )

{

*xintersect = (PLINT) fxintersect;

*yintersect = (PLINT) fyintersect;

}

return status;

}

On 15 June 2015 at 10:46, Arjen Markus <Arj...@de...> wrote:
> Hi Phil,
>
>
>
> I do not remember who wrote it, I may have made some changes to it in a now
> distant past, but I could have a look at your fix.
>
>
>
> Regards,
>
>
>
> Arjen
>
>
>
>> -----Original Message-----
>> From: Phil Rosenberg [mailto:p.d...@gm...]
>> Sent: Monday, June 15, 2015 11:35 AM
>> To: plp...@li...
>> Subject: [Plplot-devel] Bug in notcrossed() function of plfill.c
>>
>>  Hi All
>> I have just been dealing with a bug where I was drawing a contour plot and
>> my entire
>> plot was being filled with one contour level. I have fought my way through
>> the code
>> and it turned out to be a perfect storm of a bug which begins with the
>> notcrossed
>> function returning a PL_NEAR_PARALLEL status for two lines which are
>> actually
>> near perpendicular (and cross) which then causes the top left corner of my
>> plot to be
>> incorrectly labelled as inside a fill region. However because the fill
>> region is actually
>> outside the plot plplot sees no intersections with the plot boundaries so
>> checks if the
>> top left corner of the plot is inside the fill region. In this case it
>> sees that it is flagged
>> as inside so assumes the whole plot must be inside and fills the whole
>> plot.
>>
>> I have fixed my code, but I actually don't understand the exixting logic
>> inside
>> notcrossed(). This might be because it is an error or it might be because
>> I just don't
>> get it. So before I push my change I just wanted to check if whoever
>> authored this
>> function is still around?
>>
>> Phil
>>
>>
>> ------------------------------------------------------------------------------
>> _______________________________________________
>> Plplot-devel mailing list
>> Plp...@li...
>> https://lists.sourceforge.net/lists/listinfo/plplot-devel
>
> DISCLAIMER: This message is intended exclusively for the addressee(s) and
> may contain confidential and privileged information. If you are not the
> intended recipient please notify the sender immediately and destroy this
> message. Unauthorized use, disclosure or copying of this message is strictly
> prohibited. The foundation 'Stichting Deltares', which has its seat at
> Delft, The Netherlands, Commercial Registration Number 41146461, is not
> liable in any way whatsoever for consequences and/or damages resulting from
> the improper, incomplete and untimely dispatch, receipt and/or content of
> this e-mail.

Re: [Plplot-devel] Bug in notcrossed() function of plfill.c

[Alan W. I. <ir...@be...>]

Hi Phil:

"git blame" is your friend for figuring out who authored what, and it
turns out I am virtually (except for a change by Hez) the sole author
of notcrossed, but IIRC, that built on top of what Arjen had done before
with (embedded logic rather than a function)
which built on top of what Maurice had done before....


On 2015-06-15 11:10+0100 Phil Rosenberg wrote:

> Hi Arjen
>
> I've just copied the code below as I don't just have time at the
> moment to sort a git patch (The plot I was making is for a
> presentation this afternoon!).  The old code has been commented out
> with /* */ and my new code is directly above that from the #ifdef
> onwards.
>
> Basically I get that the variable factor will be zero for parallel
> lines and I get that there is a precision limit on that due to
> floating point rounding. However I don't understand how factor_NBCC
> works as a test.
>
> For the bug in question the inputs were xA1=20994, yA1=12219,
> xA2=4915, yA2=12561 xB1=20979, yB1=12219, xB2=20979, yB2=12221.
> Although perhaps the As and Bs were reversed, but the flagging should
> be identical.

I (and presumably the rest here) were having a hard time figuring out
whether those two lines mathematically intersected or not. So I have
prepared a plot (see attached) that demonstrates that the two lines _do_
mathematically intersect (where the red line is a clipped portion of the A line
segment and the yellow line is the B line segment in totality.)

Note however, that all the xA1, etc. values have a precision of +/- 2
because of rounding issues so the purpose of the PL_NBCC = 2 fuzz
factor is to make sure that the result are not subject to such
rounding issues, i.e., notcrossed only returns 0 status if the
crossing would occur regardless of shifts of +/- 2 in each of the xA,
yA, xB, and yB coordinates.  And of course, in this case when the
second line segment only has a length of 2, the crossing result is
never going to be definite so you will always get a non-zero return
code from notcrossed.

If that explanation makes sense to you, but you still feel noncrossed
needs a fix, please send that in git format-patch form so I can
conveniently evaluate your proposed logic change.  But I suspect the
noncrossed logic is fine, and the fix for the issue you found needs to
be made in another part of our code to deal correctly with non-zero
return values from notcrossed.

By the way, I hope your presentation went well despite the
distraction introduced by this PLplot bug you discovered at
the last minute.

Alan
__________________________
Alan W. Irwin

Astronomical research affiliation with Department of Physics and Astronomy,
University of Victoria (astrowww.phys.uvic.ca).

Programming affiliations with the FreeEOS equation-of-state
implementation for stellar interiors (freeeos.sf.net); the Time
Ephemerides project (timeephem.sf.net); PLplot scientific plotting
software package (plplot.sf.net); the libLASi project
(unifont.org/lasi); the Loads of Linux Links project (loll.sf.net);
and the Linux Brochure Project (lbproject.sf.net).
__________________________

Linux-powered Science
__________________________

Re: [Plplot-devel] Bug in notcrossed() function of plfill.c

[Maurice L. <mj...@br...>]

On Monday, June 15, 2015 at 11:18:33 (-0700) Alan W. Irwin writes:
 > Hi Phil:
 > 
 > "git blame" is your friend for figuring out who authored what, and it
 > turns out I am virtually (except for a change by Hez) the sole author
 > of notcrossed, but IIRC, that built on top of what Arjen had done before
 > with (embedded logic rather than a function)
 > which built on top of what Maurice had done before....

..and I can't take credit for that either, as the core contourer had already
been written when I got hold of it.  IIRC I fixed a bug or two and added the
function evaluator interface so I could use it from Fortran and later our C++
matrix class.  This is what I started with, summer of 1990:

http://amiga-fish.erkan.se/amiga-fish-disk-340-content-Plplot/

-- 
Maurice LeBrun

Re: [Plplot-devel] Bug in notcrossed() function of plfill.c

[Phil R. <p.d...@gm...>]

I will have to try out git blame then. I imagined that something so well embedded would predate our git usage, but I guess our svn history was brought in too.

I guess you have as little idea as me then about how it is intended to work?

-----Original Message-----
From: "Alan W. Irwin" <ir...@be...>
Sent: ‎15/‎06/‎2015 19:18
To: "Phil Rosenberg" <p.d...@gm...>
Cc: "Arjen Markus" <Arj...@de...>; "plp...@li..." <plp...@li...>
Subject: Re: [Plplot-devel] Bug in notcrossed() function of plfill.c

Hi Phil:

"git blame" is your friend for figuring out who authored what, and it
turns out I am virtually (except for a change by Hez) the sole author
of notcrossed, but IIRC, that built on top of what Arjen had done before
with (embedded logic rather than a function)
which built on top of what Maurice had done before....


On 2015-06-15 11:10+0100 Phil Rosenberg wrote:

> Hi Arjen
>
> I've just copied the code below as I don't just have time at the
> moment to sort a git patch (The plot I was making is for a
> presentation this afternoon!).  The old code has been commented out
> with /* */ and my new code is directly above that from the #ifdef
> onwards.
>
> Basically I get that the variable factor will be zero for parallel
> lines and I get that there is a precision limit on that due to
> floating point rounding. However I don't understand how factor_NBCC
> works as a test.
>
> For the bug in question the inputs were xA1=20994, yA1=12219,
> xA2=4915, yA2=12561 xB1=20979, yB1=12219, xB2=20979, yB2=12221.
> Although perhaps the As and Bs were reversed, but the flagging should
> be identical.

I (and presumably the rest here) were having a hard time figuring out
whether those two lines mathematically intersected or not. So I have
prepared a plot (see attached) that demonstrates that the two lines _do_
mathematically intersect (where the red line is a clipped portion of the A line
segment and the yellow line is the B line segment in totality.)

Note however, that all the xA1, etc. values have a precision of +/- 2
because of rounding issues so the purpose of the PL_NBCC = 2 fuzz
factor is to make sure that the result are not subject to such
rounding issues, i.e., notcrossed only returns 0 status if the
crossing would occur regardless of shifts of +/- 2 in each of the xA,
yA, xB, and yB coordinates.  And of course, in this case when the
second line segment only has a length of 2, the crossing result is
never going to be definite so you will always get a non-zero return
code from notcrossed.

If that explanation makes sense to you, but you still feel noncrossed
needs a fix, please send that in git format-patch form so I can
conveniently evaluate your proposed logic change.  But I suspect the
noncrossed logic is fine, and the fix for the issue you found needs to
be made in another part of our code to deal correctly with non-zero
return values from notcrossed.

By the way, I hope your presentation went well despite the
distraction introduced by this PLplot bug you discovered at
the last minute.

Alan
__________________________
Alan W. Irwin

Astronomical research affiliation with Department of Physics and Astronomy,
University of Victoria (astrowww.phys.uvic.ca).

Programming affiliations with the FreeEOS equation-of-state
implementation for stellar interiors (freeeos.sf.net); the Time
Ephemerides project (timeephem.sf.net); PLplot scientific plotting
software package (plplot.sf.net); the libLASi project
(unifont.org/lasi); the Loads of Linux Links project (loll.sf.net);
and the Linux Brochure Project (lbproject.sf.net).
__________________________

Linux-powered Science
__________________________

Re: [Plplot-devel] Bug in notcrossed() function of plfill.c

[Alan W. I. <ir...@be...>]

On 2015-06-15 21:07+0100 Phil Rosenberg wrote:

> I will have to try out git blame then. I imagined that something so
well embedded would predate our git usage, but I guess our svn history
was brought in too.

Yes, Hazen and I were careful to preserve our history back to the start in
~1992 which in retrospect was really a smart idea because of facilities
like "git blame".

> I guess you have as little idea as me then about how it is intended to work?

Hi Phil:

Actually, if "it" refers to the notcrossed function, I do think I
understand exactly what it is supposed to do, and I tried to explain
it on my previous post which you quoted and which I quote again below.

I suspect you may have just read my first comment below and then quit.  :-)

Alan

>
> -----Original Message-----
> From: "Alan W. Irwin" <ir...@be...>
> Sent: ‎15/‎06/‎2015 19:18
> To: "Phil Rosenberg" <p.d...@gm...>
> Cc: "Arjen Markus" <Arj...@de...>; "plp...@li..." <plp...@li...>
> Subject: Re: [Plplot-devel] Bug in notcrossed() function of plfill.c
>
> Hi Phil:
>
> "git blame" is your friend for figuring out who authored what, and it
> turns out I am virtually (except for a change by Hez) the sole author
> of notcrossed, but IIRC, that built on top of what Arjen had done before
> with (embedded logic rather than a function)
> which built on top of what Maurice had done before....
>
>
> On 2015-06-15 11:10+0100 Phil Rosenberg wrote:
>
>> Hi Arjen
>>
>> I've just copied the code below as I don't just have time at the
>> moment to sort a git patch (The plot I was making is for a
>> presentation this afternoon!).  The old code has been commented out
>> with /* */ and my new code is directly above that from the #ifdef
>> onwards.
>>
>> Basically I get that the variable factor will be zero for parallel
>> lines and I get that there is a precision limit on that due to
>> floating point rounding. However I don't understand how factor_NBCC
>> works as a test.
>>
>> For the bug in question the inputs were xA1=20994, yA1=12219,
>> xA2=4915, yA2=12561 xB1=20979, yB1=12219, xB2=20979, yB2=12221.
>> Although perhaps the As and Bs were reversed, but the flagging should
>> be identical.
>
> I (and presumably the rest here) were having a hard time figuring out
> whether those two lines mathematically intersected or not. So I have
> prepared a plot (see attached) that demonstrates that the two lines _do_
> mathematically intersect (where the red line is a clipped portion of the A line
> segment and the yellow line is the B line segment in totality.)
>
> Note however, that all the xA1, etc. values have a precision of +/- 2
> because of rounding issues so the purpose of the PL_NBCC = 2 fuzz
> factor is to make sure that the result are not subject to such
> rounding issues, i.e., notcrossed only returns 0 status if the
> crossing would occur regardless of shifts of +/- 2 in each of the xA,
> yA, xB, and yB coordinates.  And of course, in this case when the
> second line segment only has a length of 2, the crossing result is
> never going to be definite so you will always get a non-zero return
> code from notcrossed.
>
> If that explanation makes sense to you, but you still feel noncrossed
> needs a fix, please send that in git format-patch form so I can
> conveniently evaluate your proposed logic change.  But I suspect the
> noncrossed logic is fine, and the fix for the issue you found needs to
> be made in another part of our code to deal correctly with non-zero
> return values from notcrossed.
>
> By the way, I hope your presentation went well despite the
> distraction introduced by this PLplot bug you discovered at
> the last minute.
>
> Alan
> __________________________
> Alan W. Irwin
>
> Astronomical research affiliation with Department of Physics and Astronomy,
> University of Victoria (astrowww.phys.uvic.ca).
>
> Programming affiliations with the FreeEOS equation-of-state
> implementation for stellar interiors (freeeos.sf.net); the Time
> Ephemerides project (timeephem.sf.net); PLplot scientific plotting
> software package (plplot.sf.net); the libLASi project
> (unifont.org/lasi); the Loads of Linux Links project (loll.sf.net);
> and the Linux Brochure Project (lbproject.sf.net).
> __________________________
>
> Linux-powered Science
> __________________________

__________________________
Alan W. Irwin

Astronomical research affiliation with Department of Physics and Astronomy,
University of Victoria (astrowww.phys.uvic.ca).

Programming affiliations with the FreeEOS equation-of-state
implementation for stellar interiors (freeeos.sf.net); the Time
Ephemerides project (timeephem.sf.net); PLplot scientific plotting
software package (plplot.sf.net); the libLASi project
(unifont.org/lasi); the Loads of Linux Links project (loll.sf.net);
and the Linux Brochure Project (lbproject.sf.net).
__________________________

Linux-powered Science
__________________________

Re: [Plplot-devel] Bug in notcrossed() function of plfill.c

[Arjen M. <Arj...@de...>]

Hi Phil, Alan, Maurice,



I have had a look at the code (both Phil’s patch and the original). I am a bit uncomfortable here:

-        The original, using factor_NBCC cannot be correct, if only for dimensional reasons. “factor” is clearly a signed surface area, so that its dimension is L^2, whereas “factor_NBCC” has the dimension length (L).

-        Phil’s patch uses FLT_MIN or DBL_MIN as a threshold for indicating nearly parallel lines, but FTL_MIN is 1e-38 and DBL_MIN is even smaller. Given that the incoming arguments are integer, these thresholds will simply never be triggered.



My understanding is that the code tries to determine whether the angle between the two lines is very small by calculating the area spanned by the vectors defining the direction of the lines (this is “factor”) and comparing it to a small value. But that value should be related to the length of both these vectors. I would say something like this ought to work:

factor = … ; /* This is sin(angle) * length vector 1 * length vector 2 – plane geometry */

limit = 0.01 * length vector 1 * length vector 2; /* This means an angle of 0.01 radians or 1 degree */



if ( fabs(factor) < limit ) {

   status = status | NEAR_PARALLEL;

}



Alas, no time right now to elaborate further.



Regards,



Arjen

> -----Original Message-----
> From: Alan W. Irwin [mailto:ir...@be...]
> Sent: Monday, June 15, 2015 11:59 PM
> To: Phil Rosenberg
> Cc: Arjen Markus; plp...@li...
> Subject: RE: [Plplot-devel] Bug in notcrossed() function of plfill.c
>
> On 2015-06-15 21:07+0100 Phil Rosenberg wrote:
>
> > I will have to try out git blame then. I imagined that something so
> well embedded would predate our git usage, but I guess our svn history was brought
> in too.
>
> Yes, Hazen and I were careful to preserve our history back to the start in
> ~1992 which in retrospect was really a smart idea because of facilities like "git
> blame".
>
> > I guess you have as little idea as me then about how it is intended to work?
>
> Hi Phil:
>
> Actually, if "it" refers to the notcrossed function, I do think I understand exactly what
> it is supposed to do, and I tried to explain it on my previous post which you quoted
> and which I quote again below.
>
> I suspect you may have just read my first comment below and then quit.  :-)
>
> Alan
>
> >
> > -----Original Message-----
> > From: "Alan W. Irwin" <ir...@be...>
> > Sent: ‎15/‎06/‎2015 19:18
> > To: "Phil Rosenberg" <p.d...@gm...>
> > Cc: "Arjen Markus" <Arj...@de...>;
> > "plp...@li..."
> > <plp...@li...>
> > Subject: Re: [Plplot-devel] Bug in notcrossed() function of plfill.c
> >
> > Hi Phil:
> >
> > "git blame" is your friend for figuring out who authored what, and it
> > turns out I am virtually (except for a change by Hez) the sole author
> > of notcrossed, but IIRC, that built on top of what Arjen had done
> > before with (embedded logic rather than a function) which built on top
> > of what Maurice had done before....
> >
> >
> > On 2015-06-15 11:10+0100 Phil Rosenberg wrote:
> >
> >> Hi Arjen
> >>
> >> I've just copied the code below as I don't just have time at the
> >> moment to sort a git patch (The plot I was making is for a
> >> presentation this afternoon!).  The old code has been commented out
> >> with /* */ and my new code is directly above that from the #ifdef
> >> onwards.
> >>
> >> Basically I get that the variable factor will be zero for parallel
> >> lines and I get that there is a precision limit on that due to
> >> floating point rounding. However I don't understand how factor_NBCC
> >> works as a test.
> >>
> >> For the bug in question the inputs were xA1=20994, yA1=12219,
> >> xA2=4915, yA2=12561 xB1=20979, yB1=12219, xB2=20979, yB2=12221.
> >> Although perhaps the As and Bs were reversed, but the flagging should
> >> be identical.
> >
> > I (and presumably the rest here) were having a hard time figuring out
> > whether those two lines mathematically intersected or not. So I have
> > prepared a plot (see attached) that demonstrates that the two lines
> > _do_ mathematically intersect (where the red line is a clipped portion
> > of the A line segment and the yellow line is the B line segment in
> > totality.)
> >
> > Note however, that all the xA1, etc. values have a precision of +/- 2
> > because of rounding issues so the purpose of the PL_NBCC = 2 fuzz
> > factor is to make sure that the result are not subject to such
> > rounding issues, i.e., notcrossed only returns 0 status if the
> > crossing would occur regardless of shifts of +/- 2 in each of the xA,
> > yA, xB, and yB coordinates.  And of course, in this case when the
> > second line segment only has a length of 2, the crossing result is
> > never going to be definite so you will always get a non-zero return
> > code from notcrossed.
> >
> > If that explanation makes sense to you, but you still feel noncrossed
> > needs a fix, please send that in git format-patch form so I can
> > conveniently evaluate your proposed logic change.  But I suspect the
> > noncrossed logic is fine, and the fix for the issue you found needs to
> > be made in another part of our code to deal correctly with non-zero
> > return values from notcrossed.
> >
> > By the way, I hope your presentation went well despite the distraction
> > introduced by this PLplot bug you discovered at the last minute.
> >
> > Alan
> > __________________________
> > Alan W. Irwin
> >
> > Astronomical research affiliation with Department of Physics and
> > Astronomy, University of Victoria (astrowww.phys.uvic.ca).
> >
> > Programming affiliations with the FreeEOS equation-of-state
> > implementation for stellar interiors (freeeos.sf.net); the Time
> > Ephemerides project (timeephem.sf.net); PLplot scientific plotting
> > software package (plplot.sf.net); the libLASi project
> > (unifont.org/lasi); the Loads of Linux Links project (loll.sf.net);
> > and the Linux Brochure Project (lbproject.sf.net).
> > __________________________
> >
> > Linux-powered Science
> > __________________________
>
> __________________________
> Alan W. Irwin
>
> Astronomical research affiliation with Department of Physics and Astronomy,
> University of Victoria (astrowww.phys.uvic.ca).
>
> Programming affiliations with the FreeEOS equation-of-state implementation for
> stellar interiors (freeeos.sf.net); the Time Ephemerides project (timeephem.sf.net);
> PLplot scientific plotting software package (plplot.sf.net); the libLASi project
> (unifont.org/lasi); the Loads of Linux Links project (loll.sf.net); and the Linux Brochure
> Project (lbproject.sf.net).
> __________________________
>
> Linux-powered Science
> __________________________

DISCLAIMER: This message is intended exclusively for the addressee(s) and may contain confidential and privileged information. If you are not the intended recipient please notify the sender immediately and destroy this message. Unauthorized use, disclosure or copying of this message is strictly prohibited. The foundation 'Stichting Deltares', which has its seat at Delft, The Netherlands, Commercial Registration Number 41146461, is not liable in any way whatsoever for consequences and/or damages resulting from the improper, incomplete and untimely dispatch, receipt and/or content of this e-mail.

Re: [Plplot-devel] Bug in notcrossed() function of plfill.c

[Phil R. <p.d...@gm...>]

Hi Alan, Maurice and Arjen

Arjen - yes you are correct FLT_MIN was the incorrect number to use. I
should have used  PLFLT_EPSILON*MAX(xA2A1 * yB2B1, yA2A1 * xB2B1 ) for
my test. Here PLFLT_EPSILON is about 1e-16 for a double so we have
something that is much more sensible as a test.

Alan - yes you were correct I missed the second part of your email. If
only you top posted ;-).

So I think I understand the maths now. If each parameter has an
uncertainty of +/- 2 pixels then when factor should be zero, its
maximum value can be
( xA2A1 + 2 ) * ( yB2B1 +2 ) - ( yA2A1 + 2 )* ( xB2B1 + 2 )
which when expanded out gives
xA2A1 * yB2B1 - yA2A1 * xB2B1 + 2( xA2A1 + yB2B1 + yA2A1 + xB2B1 ).
= factor + factor_NBCC

So the uncertainty in factor is factor_NBCC so if abs(factor) is less
than factor_NBCC then it is within the uncertainty of zero. This
explains the dimension inconsistency - actually PL_NBCC has units of
length so that makes it work.

Is this all correct?

So in this case with the numbers I give above the line does indeed
fall within the uncertainty of zero.

However I am going to state that for this problem the initial
definition of uncertainty is incorrect. We are doing a point in
polygon test so we actually don't care at all about the rounding
precision of real numbers to integers. The actual points are exact -
even to within epsilon because all the numbers are integers and a
float can hold all integers exactly. Therefore it would actually be
safe to just test against zero. Despite this it would be worth having
an epsilon test.

In case that isn't clear let me state it like this. The points are not
scientifically exact in that when we go from the data we are plotting
onto out contour plot, we have some rounding uncertainty due to our
grid size. However, at the point of checking whether the corner of a
plot is within one of our fill regions we are no longer interested in
the original data. By this time we begin our fill function we have
divided our plot into a perfectly tessellating pattern of polygons.
And these really are perfectly tessellating. It is these polygons that
we are interested in for our fill algorithm, not the original data.
Therefore as far as the fill algorithm is concerned they are perfect
with zero uncertainty.

Therefore at the most for the fill function we might need an epsilon
test but to assume 2 pixel uncertainty is actually wrong.

Does that make sense?

Phil

On 16 June 2015 at 07:43, Arjen Markus <Arj...@de...> wrote:
> Hi Phil, Alan, Maurice,
>
>
>
> I have had a look at the code (both Phil’s patch and the original). I am a
> bit uncomfortable here:
>
> -        The original, using factor_NBCC cannot be correct, if only for
> dimensional reasons. “factor” is clearly a signed surface area, so that its
> dimension is L^2, whereas “factor_NBCC” has the dimension length (L).
>
> -        Phil’s patch uses FLT_MIN or DBL_MIN as a threshold for indicating
> nearly parallel lines, but FTL_MIN is 1e-38 and DBL_MIN is even smaller.
> Given that the incoming arguments are integer, these thresholds will simply
> never be triggered.
>
>
>
> My understanding is that the code tries to determine whether the angle
> between the two lines is very small by calculating the area spanned by the
> vectors defining the direction of the lines (this is “factor”) and comparing
> it to a small value. But that value should be related to the length of both
> these vectors. I would say something like this ought to work:
>
> factor = … ; /* This is sin(angle) * length vector 1 * length vector 2 –
> plane geometry */
>
> limit = 0.01 * length vector 1 * length vector 2; /* This means an angle of
> 0.01 radians or 1 degree */
>
>
>
> if ( fabs(factor) < limit ) {
>
>    status = status | NEAR_PARALLEL;
>
> }
>
>
>
> Alas, no time right now to elaborate further.
>
>
>
> Regards,
>
>
>
> Arjen
>
>> -----Original Message-----
>> From: Alan W. Irwin [mailto:ir...@be...]
>> Sent: Monday, June 15, 2015 11:59 PM
>> To: Phil Rosenberg
>> Cc: Arjen Markus; plp...@li...
>
>> Subject: RE: [Plplot-devel] Bug in notcrossed() function of plfill.c
>>
>> On 2015-06-15 21:07+0100 Phil Rosenberg wrote:
>>
>> > I will have to try out git blame then. I imagined that something so
>> well embedded would predate our git usage, but I guess our svn history was
>> brought
>> in too.
>>
>> Yes, Hazen and I were careful to preserve our history back to the start in
>> ~1992 which in retrospect was really a smart idea because of facilities
>> like "git
>> blame".
>>
>> > I guess you have as little idea as me then about how it is intended to
>> > work?
>>
>> Hi Phil:
>>
>> Actually, if "it" refers to the notcrossed function, I do think I
>> understand exactly what
>> it is supposed to do, and I tried to explain it on my previous post which
>> you quoted
>> and which I quote again below.
>>
>> I suspect you may have just read my first comment below and then quit.
>> :-)
>>
>> Alan
>>
>> >
>> > -----Original Message-----
>> > From: "Alan W. Irwin" <ir...@be...>
>> > Sent: ‎15/‎06/‎2015 19:18
>> > To: "Phil Rosenberg" <p.d...@gm...>
>> > Cc: "Arjen Markus" <Arj...@de...>;
>> > "plp...@li..."
>> > <plp...@li...>
>> > Subject: Re: [Plplot-devel] Bug in notcrossed() function of plfill.c
>> >
>> > Hi Phil:
>> >
>> > "git blame" is your friend for figuring out who authored what, and it
>> > turns out I am virtually (except for a change by Hez) the sole author
>> > of notcrossed, but IIRC, that built on top of what Arjen had done
>> > before with (embedded logic rather than a function) which built on top
>> > of what Maurice had done before....
>> >
>> >
>> > On 2015-06-15 11:10+0100 Phil Rosenberg wrote:
>> >
>> >> Hi Arjen
>> >>
>> >> I've just copied the code below as I don't just have time at the
>> >> moment to sort a git patch (The plot I was making is for a
>> >> presentation this afternoon!).  The old code has been commented out
>> >> with /* */ and my new code is directly above that from the #ifdef
>> >> onwards.
>> >>
>> >> Basically I get that the variable factor will be zero for parallel
>> >> lines and I get that there is a precision limit on that due to
>> >> floating point rounding. However I don't understand how factor_NBCC
>> >> works as a test.
>> >>
>> >> For the bug in question the inputs were xA1=20994, yA1=12219,
>> >> xA2=4915, yA2=12561 xB1=20979, yB1=12219, xB2=20979, yB2=12221.
>> >> Although perhaps the As and Bs were reversed, but the flagging should
>> >> be identical.
>> >
>> > I (and presumably the rest here) were having a hard time figuring out
>> > whether those two lines mathematically intersected or not. So I have
>> > prepared a plot (see attached) that demonstrates that the two lines
>> > _do_ mathematically intersect (where the red line is a clipped portion
>> > of the A line segment and the yellow line is the B line segment in
>> > totality.)
>> >
>> > Note however, that all the xA1, etc. values have a precision of +/- 2
>> > because of rounding issues so the purpose of the PL_NBCC = 2 fuzz
>> > factor is to make sure that the result are not subject to such
>> > rounding issues, i.e., notcrossed only returns 0 status if the
>> > crossing would occur regardless of shifts of +/- 2 in each of the xA,
>> > yA, xB, and yB coordinates.  And of course, in this case when the
>> > second line segment only has a length of 2, the crossing result is
>> > never going to be definite so you will always get a non-zero return
>> > code from notcrossed.
>> >
>> > If that explanation makes sense to you, but you still feel noncrossed
>> > needs a fix, please send that in git format-patch form so I can
>> > conveniently evaluate your proposed logic change.  But I suspect the
>> > noncrossed logic is fine, and the fix for the issue you found needs to
>> > be made in another part of our code to deal correctly with non-zero
>> > return values from notcrossed.
>> >
>> > By the way, I hope your presentation went well despite the distraction
>> > introduced by this PLplot bug you discovered at the last minute.
>> >
>> > Alan
>> > __________________________
>> > Alan W. Irwin
>> >
>> > Astronomical research affiliation with Department of Physics and
>> > Astronomy, University of Victoria (astrowww.phys.uvic.ca).
>> >
>> > Programming affiliations with the FreeEOS equation-of-state
>> > implementation for stellar interiors (freeeos.sf.net); the Time
>> > Ephemerides project (timeephem.sf.net); PLplot scientific plotting
>> > software package (plplot.sf.net); the libLASi project
>> > (unifont.org/lasi); the Loads of Linux Links project (loll.sf.net);
>> > and the Linux Brochure Project (lbproject.sf.net).
>> > __________________________
>> >
>> > Linux-powered Science
>> > __________________________
>>
>> __________________________
>> Alan W. Irwin
>>
>> Astronomical research affiliation with Department of Physics and
>> Astronomy,
>> University of Victoria (astrowww.phys.uvic.ca).
>>
>> Programming affiliations with the FreeEOS equation-of-state implementation
>> for
>> stellar interiors (freeeos.sf.net); the Time Ephemerides project
>> (timeephem.sf.net);
>> PLplot scientific plotting software package (plplot.sf.net); the libLASi
>> project
>> (unifont.org/lasi); the Loads of Linux Links project (loll.sf.net); and
>> the Linux Brochure
>> Project (lbproject.sf.net).
>> __________________________
>>
>> Linux-powered Science
>> __________________________
>
> DISCLAIMER: This message is intended exclusively for the addressee(s) and
> may contain confidential and privileged information. If you are not the
> intended recipient please notify the sender immediately and destroy this
> message. Unauthorized use, disclosure or copying of this message is strictly
> prohibited. The foundation 'Stichting Deltares', which has its seat at
> Delft, The Netherlands, Commercial Registration Number 41146461, is not
> liable in any way whatsoever for consequences and/or damages resulting from
> the improper, incomplete and untimely dispatch, receipt and/or content of
> this e-mail.

Re: [Plplot-devel] Bug in notcrossed() function of plfill.c

[Phil R. <p.d...@gm...>]

I have just looked and it seems that notcrossed is only used for
point-in-polygon checks. Therefore based on the arguments in my
previous email I would suggest that the following patch should give
the desired results. If anyone has any particular objections to this
please let me know, otherwise I will commit this.

Cheers

Phil

On 16 June 2015 at 09:55, Phil Rosenberg <p.d...@gm...> wrote:
> Hi Alan, Maurice and Arjen
>
> Arjen - yes you are correct FLT_MIN was the incorrect number to use. I
> should have used  PLFLT_EPSILON*MAX(xA2A1 * yB2B1, yA2A1 * xB2B1 ) for
> my test. Here PLFLT_EPSILON is about 1e-16 for a double so we have
> something that is much more sensible as a test.
>
> Alan - yes you were correct I missed the second part of your email. If
> only you top posted ;-).
>
> So I think I understand the maths now. If each parameter has an
> uncertainty of +/- 2 pixels then when factor should be zero, its
> maximum value can be
> ( xA2A1 + 2 ) * ( yB2B1 +2 ) - ( yA2A1 + 2 )* ( xB2B1 + 2 )
> which when expanded out gives
> xA2A1 * yB2B1 - yA2A1 * xB2B1 + 2( xA2A1 + yB2B1 + yA2A1 + xB2B1 ).
> = factor + factor_NBCC
>
> So the uncertainty in factor is factor_NBCC so if abs(factor) is less
> than factor_NBCC then it is within the uncertainty of zero. This
> explains the dimension inconsistency - actually PL_NBCC has units of
> length so that makes it work.
>
> Is this all correct?
>
> So in this case with the numbers I give above the line does indeed
> fall within the uncertainty of zero.
>
> However I am going to state that for this problem the initial
> definition of uncertainty is incorrect. We are doing a point in
> polygon test so we actually don't care at all about the rounding
> precision of real numbers to integers. The actual points are exact -
> even to within epsilon because all the numbers are integers and a
> float can hold all integers exactly. Therefore it would actually be
> safe to just test against zero. Despite this it would be worth having
> an epsilon test.
>
> In case that isn't clear let me state it like this. The points are not
> scientifically exact in that when we go from the data we are plotting
> onto out contour plot, we have some rounding uncertainty due to our
> grid size. However, at the point of checking whether the corner of a
> plot is within one of our fill regions we are no longer interested in
> the original data. By this time we begin our fill function we have
> divided our plot into a perfectly tessellating pattern of polygons.
> And these really are perfectly tessellating. It is these polygons that
> we are interested in for our fill algorithm, not the original data.
> Therefore as far as the fill algorithm is concerned they are perfect
> with zero uncertainty.
>
> Therefore at the most for the fill function we might need an epsilon
> test but to assume 2 pixel uncertainty is actually wrong.
>
> Does that make sense?
>
> Phil
>
> On 16 June 2015 at 07:43, Arjen Markus <Arj...@de...> wrote:
>> Hi Phil, Alan, Maurice,
>>
>>
>>
>> I have had a look at the code (both Phil’s patch and the original). I am a
>> bit uncomfortable here:
>>
>> -        The original, using factor_NBCC cannot be correct, if only for
>> dimensional reasons. “factor” is clearly a signed surface area, so that its
>> dimension is L^2, whereas “factor_NBCC” has the dimension length (L).
>>
>> -        Phil’s patch uses FLT_MIN or DBL_MIN as a threshold for indicating
>> nearly parallel lines, but FTL_MIN is 1e-38 and DBL_MIN is even smaller.
>> Given that the incoming arguments are integer, these thresholds will simply
>> never be triggered.
>>
>>
>>
>> My understanding is that the code tries to determine whether the angle
>> between the two lines is very small by calculating the area spanned by the
>> vectors defining the direction of the lines (this is “factor”) and comparing
>> it to a small value. But that value should be related to the length of both
>> these vectors. I would say something like this ought to work:
>>
>> factor = … ; /* This is sin(angle) * length vector 1 * length vector 2 –
>> plane geometry */
>>
>> limit = 0.01 * length vector 1 * length vector 2; /* This means an angle of
>> 0.01 radians or 1 degree */
>>
>>
>>
>> if ( fabs(factor) < limit ) {
>>
>>    status = status | NEAR_PARALLEL;
>>
>> }
>>
>>
>>
>> Alas, no time right now to elaborate further.
>>
>>
>>
>> Regards,
>>
>>
>>
>> Arjen
>>
>>> -----Original Message-----
>>> From: Alan W. Irwin [mailto:ir...@be...]
>>> Sent: Monday, June 15, 2015 11:59 PM
>>> To: Phil Rosenberg
>>> Cc: Arjen Markus; plp...@li...
>>
>>> Subject: RE: [Plplot-devel] Bug in notcrossed() function of plfill.c
>>>
>>> On 2015-06-15 21:07+0100 Phil Rosenberg wrote:
>>>
>>> > I will have to try out git blame then. I imagined that something so
>>> well embedded would predate our git usage, but I guess our svn history was
>>> brought
>>> in too.
>>>
>>> Yes, Hazen and I were careful to preserve our history back to the start in
>>> ~1992 which in retrospect was really a smart idea because of facilities
>>> like "git
>>> blame".
>>>
>>> > I guess you have as little idea as me then about how it is intended to
>>> > work?
>>>
>>> Hi Phil:
>>>
>>> Actually, if "it" refers to the notcrossed function, I do think I
>>> understand exactly what
>>> it is supposed to do, and I tried to explain it on my previous post which
>>> you quoted
>>> and which I quote again below.
>>>
>>> I suspect you may have just read my first comment below and then quit.
>>> :-)
>>>
>>> Alan
>>>
>>> >
>>> > -----Original Message-----
>>> > From: "Alan W. Irwin" <ir...@be...>
>>> > Sent: ‎15/‎06/‎2015 19:18
>>> > To: "Phil Rosenberg" <p.d...@gm...>
>>> > Cc: "Arjen Markus" <Arj...@de...>;
>>> > "plp...@li..."
>>> > <plp...@li...>
>>> > Subject: Re: [Plplot-devel] Bug in notcrossed() function of plfill.c
>>> >
>>> > Hi Phil:
>>> >
>>> > "git blame" is your friend for figuring out who authored what, and it
>>> > turns out I am virtually (except for a change by Hez) the sole author
>>> > of notcrossed, but IIRC, that built on top of what Arjen had done
>>> > before with (embedded logic rather than a function) which built on top
>>> > of what Maurice had done before....
>>> >
>>> >
>>> > On 2015-06-15 11:10+0100 Phil Rosenberg wrote:
>>> >
>>> >> Hi Arjen
>>> >>
>>> >> I've just copied the code below as I don't just have time at the
>>> >> moment to sort a git patch (The plot I was making is for a
>>> >> presentation this afternoon!).  The old code has been commented out
>>> >> with /* */ and my new code is directly above that from the #ifdef
>>> >> onwards.
>>> >>
>>> >> Basically I get that the variable factor will be zero for parallel
>>> >> lines and I get that there is a precision limit on that due to
>>> >> floating point rounding. However I don't understand how factor_NBCC
>>> >> works as a test.
>>> >>
>>> >> For the bug in question the inputs were xA1=20994, yA1=12219,
>>> >> xA2=4915, yA2=12561 xB1=20979, yB1=12219, xB2=20979, yB2=12221.
>>> >> Although perhaps the As and Bs were reversed, but the flagging should
>>> >> be identical.
>>> >
>>> > I (and presumably the rest here) were having a hard time figuring out
>>> > whether those two lines mathematically intersected or not. So I have
>>> > prepared a plot (see attached) that demonstrates that the two lines
>>> > _do_ mathematically intersect (where the red line is a clipped portion
>>> > of the A line segment and the yellow line is the B line segment in
>>> > totality.)
>>> >
>>> > Note however, that all the xA1, etc. values have a precision of +/- 2
>>> > because of rounding issues so the purpose of the PL_NBCC = 2 fuzz
>>> > factor is to make sure that the result are not subject to such
>>> > rounding issues, i.e., notcrossed only returns 0 status if the
>>> > crossing would occur regardless of shifts of +/- 2 in each of the xA,
>>> > yA, xB, and yB coordinates.  And of course, in this case when the
>>> > second line segment only has a length of 2, the crossing result is
>>> > never going to be definite so you will always get a non-zero return
>>> > code from notcrossed.
>>> >
>>> > If that explanation makes sense to you, but you still feel noncrossed
>>> > needs a fix, please send that in git format-patch form so I can
>>> > conveniently evaluate your proposed logic change.  But I suspect the
>>> > noncrossed logic is fine, and the fix for the issue you found needs to
>>> > be made in another part of our code to deal correctly with non-zero
>>> > return values from notcrossed.
>>> >
>>> > By the way, I hope your presentation went well despite the distraction
>>> > introduced by this PLplot bug you discovered at the last minute.
>>> >
>>> > Alan
>>> > __________________________
>>> > Alan W. Irwin
>>> >
>>> > Astronomical research affiliation with Department of Physics and
>>> > Astronomy, University of Victoria (astrowww.phys.uvic.ca).
>>> >
>>> > Programming affiliations with the FreeEOS equation-of-state
>>> > implementation for stellar interiors (freeeos.sf.net); the Time
>>> > Ephemerides project (timeephem.sf.net); PLplot scientific plotting
>>> > software package (plplot.sf.net); the libLASi project
>>> > (unifont.org/lasi); the Loads of Linux Links project (loll.sf.net);
>>> > and the Linux Brochure Project (lbproject.sf.net).
>>> > __________________________
>>> >
>>> > Linux-powered Science
>>> > __________________________
>>>
>>> __________________________
>>> Alan W. Irwin
>>>
>>> Astronomical research affiliation with Department of Physics and
>>> Astronomy,
>>> University of Victoria (astrowww.phys.uvic.ca).
>>>
>>> Programming affiliations with the FreeEOS equation-of-state implementation
>>> for
>>> stellar interiors (freeeos.sf.net); the Time Ephemerides project
>>> (timeephem.sf.net);
>>> PLplot scientific plotting software package (plplot.sf.net); the libLASi
>>> project
>>> (unifont.org/lasi); the Loads of Linux Links project (loll.sf.net); and
>>> the Linux Brochure
>>> Project (lbproject.sf.net).
>>> __________________________
>>>
>>> Linux-powered Science
>>> __________________________
>>
>> DISCLAIMER: This message is intended exclusively for the addressee(s) and
>> may contain confidential and privileged information. If you are not the
>> intended recipient please notify the sender immediately and destroy this
>> message. Unauthorized use, disclosure or copying of this message is strictly
>> prohibited. The foundation 'Stichting Deltares', which has its seat at
>> Delft, The Netherlands, Commercial Registration Number 41146461, is not
>> liable in any way whatsoever for consequences and/or damages resulting from
>> the improper, incomplete and untimely dispatch, receipt and/or content of
>> this e-mail.

Re: [Plplot-devel] Bug in notcrossed() function of plfill.c

[Alan W. I. <ir...@be...>]

On 2015-06-16 10:30+0100 Phil Rosenberg wrote:

> I have just looked and it seems that notcrossed is only used for
> point-in-polygon checks. Therefore based on the arguments in my
> previous email I would suggest that the following patch should give
> the desired results. If anyone has any particular objections to this
> please let me know, otherwise I will commit this.

Hi Phil:

Please hold off until I have time to consider this.  It has been quite
a while so I don't remember details, but I had what I felt were good
reasons for using the fuzzy logic way back when so let me try to
resurrect those reasons from discussion on the plplot-devel list at
the time and from my commit messages in that era, and then look
carefully at your arguments in light of those reasons. But it is going
to take a while before I can do that because there is a lot of other
PLplot stuff I am involved with at the moment.

Alan
__________________________
Alan W. Irwin

Astronomical research affiliation with Department of Physics and Astronomy,
University of Victoria (astrowww.phys.uvic.ca).

Programming affiliations with the FreeEOS equation-of-state
implementation for stellar interiors (freeeos.sf.net); the Time
Ephemerides project (timeephem.sf.net); PLplot scientific plotting
software package (plplot.sf.net); the libLASi project
(unifont.org/lasi); the Loads of Linux Links project (loll.sf.net);
and the Linux Brochure Project (lbproject.sf.net).
__________________________

Linux-powered Science
__________________________

Re: [Plplot-devel] Bug in notcrossed() function of plfill.c

[Phil R. <p.d...@gm...>]

Okay, no worries

On 16 June 2015 at 11:53, Alan W. Irwin <ir...@be...> wrote:
> On 2015-06-16 10:30+0100 Phil Rosenberg wrote:
>
>> I have just looked and it seems that notcrossed is only used for
>> point-in-polygon checks. Therefore based on the arguments in my
>> previous email I would suggest that the following patch should give
>> the desired results. If anyone has any particular objections to this
>> please let me know, otherwise I will commit this.
>
>
> Hi Phil:
>
> Please hold off until I have time to consider this.  It has been quite
> a while so I don't remember details, but I had what I felt were good
> reasons for using the fuzzy logic way back when so let me try to
> resurrect those reasons from discussion on the plplot-devel list at
> the time and from my commit messages in that era, and then look
> carefully at your arguments in light of those reasons. But it is going
> to take a while before I can do that because there is a lot of other
> PLplot stuff I am involved with at the moment.
>
>
> Alan
> __________________________
> Alan W. Irwin
>
> Astronomical research affiliation with Department of Physics and Astronomy,
> University of Victoria (astrowww.phys.uvic.ca).
>
> Programming affiliations with the FreeEOS equation-of-state
> implementation for stellar interiors (freeeos.sf.net); the Time
> Ephemerides project (timeephem.sf.net); PLplot scientific plotting
> software package (plplot.sf.net); the libLASi project
> (unifont.org/lasi); the Loads of Linux Links project (loll.sf.net);
> and the Linux Brochure Project (lbproject.sf.net).
> __________________________
>
> Linux-powered Science
> __________________________

Re: [Plplot-devel] Bug in notcrossed() function of plfill.c

[Alan W. I. <ir...@be...>]

Hi Phil:

I have been looking carefully at the parts of the fill code that are
affected by notcrossed, and I think we are dealing with a fairly
complex issue here that is larger than just the criterion that is used
to decide on the PL_NEAR_PARALLEL status.  So to make sure that the
final fix really addresses the PLplot failure you discovered that
started this thread, I would greatly appreciate it if you sent me a
test case that replicates that failure for the current master tip
version of PLplot.  Ideally, if your original test case requires
access to data files and/or data processing to determine the data that
are being plotted, it would be good to figure out (say with a debugger
or appropriate print statement) the exact arguments to plfill that
cause the issue, and simply use those exact arguments for a
self-contained test case that triggers the exact same failure
that you originally discovered.

Alan
__________________________
Alan W. Irwin

Astronomical research affiliation with Department of Physics and Astronomy,
University of Victoria (astrowww.phys.uvic.ca).

Programming affiliations with the FreeEOS equation-of-state
implementation for stellar interiors (freeeos.sf.net); the Time
Ephemerides project (timeephem.sf.net); PLplot scientific plotting
software package (plplot.sf.net); the libLASi project
(unifont.org/lasi); the Loads of Linux Links project (loll.sf.net);
and the Linux Brochure Project (lbproject.sf.net).
__________________________

Linux-powered Science
__________________________

Re: [Plplot-devel] Bug in notcrossed() function of plfill.c

[Phil R. <p.d...@gm...>]

Hi Alan
I will try to do this. Unfortunately the fail case of mine was very well wrapped in my own wrapper code so it might be a challenge to generate a simple test.

Phil

-----Original Message-----
From: "Alan W. Irwin" <ir...@be...>
Sent: ‎24/‎06/‎2015 04:03
To: "Phil Rosenberg" <p.d...@gm...>
Cc: "plp...@li..." <plp...@li...>
Subject: Re: [Plplot-devel] Bug in notcrossed() function of plfill.c

Hi Phil:

I have been looking carefully at the parts of the fill code that are
affected by notcrossed, and I think we are dealing with a fairly
complex issue here that is larger than just the criterion that is used
to decide on the PL_NEAR_PARALLEL status.  So to make sure that the
final fix really addresses the PLplot failure you discovered that
started this thread, I would greatly appreciate it if you sent me a
test case that replicates that failure for the current master tip
version of PLplot.  Ideally, if your original test case requires
access to data files and/or data processing to determine the data that
are being plotted, it would be good to figure out (say with a debugger
or appropriate print statement) the exact arguments to plfill that
cause the issue, and simply use those exact arguments for a
self-contained test case that triggers the exact same failure
that you originally discovered.

Alan
__________________________
Alan W. Irwin

Astronomical research affiliation with Department of Physics and Astronomy,
University of Victoria (astrowww.phys.uvic.ca).

Programming affiliations with the FreeEOS equation-of-state
implementation for stellar interiors (freeeos.sf.net); the Time
Ephemerides project (timeephem.sf.net); PLplot scientific plotting
software package (plplot.sf.net); the libLASi project
(unifont.org/lasi); the Loads of Linux Links project (loll.sf.net);
and the Linux Brochure Project (lbproject.sf.net).
__________________________

Linux-powered Science
__________________________

Re: [Plplot-devel] Bug in notcrossed() function of plfill.c

[Alan W. I. <ir...@be...>]

On 2015-06-24 11:10+0100 Phil Rosenberg wrote:

> Hi Alan

> I will try to do this. Unfortunately the fail case of mine was very
well wrapped in my own wrapper code so it might be a challenge to
generate a simple test.

I was afraid of that, but I hope you can overcome that challenge
because a strong test case would be most helpful to make sure I have
fixed all the issues that I have spotted during my review of
the fill code that directly or indirectly uses notcrossed results.

Alan
__________________________
Alan W. Irwin

Astronomical research affiliation with Department of Physics and Astronomy,
University of Victoria (astrowww.phys.uvic.ca).

Programming affiliations with the FreeEOS equation-of-state
implementation for stellar interiors (freeeos.sf.net); the Time
Ephemerides project (timeephem.sf.net); PLplot scientific plotting
software package (plplot.sf.net); the libLASi project
(unifont.org/lasi); the Loads of Linux Links project (loll.sf.net);
and the Linux Brochure Project (lbproject.sf.net).
__________________________

Linux-powered Science
__________________________

Re: [Plplot-devel] Bug in notcrossed() function of plfill.c

[Phil R. <p.d...@gm...>]

Hi
Can we reopen this again please. I have just hit another case where
when plotting a contour plot something goes wrong and the whole plot
gets filled.

Alan, you said you were going to see if you could work out why the
fuzzy logic was needed and I said I would try to generate a test case.
I know I haven't held up my side of the bargain, but I will try to
sort one asap.

Phil

On 24 June 2015 at 19:02, Alan W. Irwin <ir...@be...> wrote:
> On 2015-06-24 11:10+0100 Phil Rosenberg wrote:
>
>> Hi Alan
>
>
>> I will try to do this. Unfortunately the fail case of mine was very
>
> well wrapped in my own wrapper code so it might be a challenge to
> generate a simple test.
>
> I was afraid of that, but I hope you can overcome that challenge
> because a strong test case would be most helpful to make sure I have
> fixed all the issues that I have spotted during my review of
> the fill code that directly or indirectly uses notcrossed results.
>
>
> Alan
> __________________________
> Alan W. Irwin
>
> Astronomical research affiliation with Department of Physics and Astronomy,
> University of Victoria (astrowww.phys.uvic.ca).
>
> Programming affiliations with the FreeEOS equation-of-state
> implementation for stellar interiors (freeeos.sf.net); the Time
> Ephemerides project (timeephem.sf.net); PLplot scientific plotting
> software package (plplot.sf.net); the libLASi project
> (unifont.org/lasi); the Loads of Linux Links project (loll.sf.net);
> and the Linux Brochure Project (lbproject.sf.net).
> __________________________
>
> Linux-powered Science
> __________________________

Re: [Plplot-devel] Bug in notcrossed() function of plfill.c

[Alan W. I. <ir...@be...>]

On 2016-01-18 16:57-0000 Phil Rosenberg wrote:

> Hi
> Can we reopen this again please. I have just hit another case where
> when plotting a contour plot something goes wrong and the whole plot
> gets filled.
>
> Alan, you said you were going to see if you could work out why the
> fuzzy logic was needed and I said I would try to generate a test case.
> I know I haven't held up my side of the bargain, but I will try to
> sort one asap.

Hi Phil:

The status here is I guessed at the cause of the issue you originally
reported and got pretty far with a fix for that on a private topic
branch but did not finish that off because some higher priorities
intervened such as the new Fortran binding.  But if you have found a
complicated case demonstrating an issue with the fill logic on master
branch, that would be like gold because such cases are quite rare.

So your absolutely first priority should be to preserve the exact
complicated conditions where you found the bug.  Then please send me
_that exact case_ to make sure I can replicate it here.  After that,
we can attempt to simplify the issue down to a much more managable
simple test case, fix that simple case, then go back to the
complicated case to make sure that fix works for it as well. Or other
possibilities exist such as fixing some fuzzy issues with the present
logic (for example, how nearly parallel intersections are treated by
the logic) to see if those fixes make any difference to your complex
case.  But essential to all of this bug-fixing process is a case (no
matter how complicated) that can be replicated elsewhere.

Alan
__________________________
Alan W. Irwin

Astronomical research affiliation with Department of Physics and Astronomy,
University of Victoria (astrowww.phys.uvic.ca).

Programming affiliations with the FreeEOS equation-of-state
implementation for stellar interiors (freeeos.sf.net); the Time
Ephemerides project (timeephem.sf.net); PLplot scientific plotting
software package (plplot.sf.net); the libLASi project
(unifont.org/lasi); the Loads of Linux Links project (loll.sf.net);
and the Linux Brochure Project (lbproject.sf.net).
__________________________

Linux-powered Science
__________________________

Re: [Plplot-devel] Bug in notcrossed() function of plfill.c

[Phil R. <p.d...@gm...>]

Hi All
It's been a while. Sorry for my lack of activity over the summer.

I've just picked up some Plplot items again on my to do list, starting
with the fill problem that I reported a rather long time ago.

I have sorted a minimal example to reproduce the bug - see attached.
it turns out that a number of things need to come together to cause
this problem. The example is based on example 12 and draws a very
small trapezium just off the bottom left corner of the plot. however
what happens instead is that the whole plot is filled. The way this
works is that a test point is selected to the right of the fill shape
and Plplot examines if a line between this point and the bottom left
corner intersects the polygon segments to test if the bottom left
corner is in the polygon. When the test is performed segments that are
close to parallel (based on a ~2 pixel fuzziness) are flagged and in
the end treat as a non-intersection. Also if the intersection is close
to the end of a line (again 2 pixels is the limit) then the
intersection is flagged as too close.

In this special case the three short sides are all approximately 2
Plplot internal units long which fools the intersection test into
thinking they are close to parallel to the test line. See
notpointinpolygon() and notcrossed() functions. These three lines are
therefore treated as non-intersectionctions even though the test line
does intersect one of them. Finally the fourth section is just long
enough and the location is just correct that the test line intersects
it more than 2 pixels from each end. The result is that the point in
polygon test sees 1 intersection instead of two and incorrectly
concludes that the bottom left corner is inside the polygon.

The final item that causes the bug to manifest is that the polygon is
entirely outside of the plot area so no segments are drawable. The
test that Plplot performs to see if the whole plot needs filling is
that the bottom left corner is inside the fill polygon and all
segments are outside the plot area. Hence the incorrect full fill.

I'm still of the opinion that the notcrossed function should not use
the 2 pixel fuzziness. At this point in the drawing we are dealing in
integer pixels and we need only an epsilon test I think. I think the
best fix is to change this. There are some sticking plaster solutions
that would hide the problem but not really fix it in my opinion. I
would really like to change the notcrossed function unless anyone has
some really strong objections?

Phil



On 18 January 2016 at 20:08, Alan W. Irwin <ir...@be...> wrote:
> On 2016-01-18 16:57-0000 Phil Rosenberg wrote:
>
>> Hi
>> Can we reopen this again please. I have just hit another case where
>> when plotting a contour plot something goes wrong and the whole plot
>> gets filled.
>>
>> Alan, you said you were going to see if you could work out why the
>> fuzzy logic was needed and I said I would try to generate a test case.
>> I know I haven't held up my side of the bargain, but I will try to
>> sort one asap.
>
>
> Hi Phil:
>
> The status here is I guessed at the cause of the issue you originally
> reported and got pretty far with a fix for that on a private topic
> branch but did not finish that off because some higher priorities
> intervened such as the new Fortran binding.  But if you have found a
> complicated case demonstrating an issue with the fill logic on master
> branch, that would be like gold because such cases are quite rare.
>
> So your absolutely first priority should be to preserve the exact
> complicated conditions where you found the bug.  Then please send me
> _that exact case_ to make sure I can replicate it here.  After that,
> we can attempt to simplify the issue down to a much more managable
> simple test case, fix that simple case, then go back to the
> complicated case to make sure that fix works for it as well. Or other
> possibilities exist such as fixing some fuzzy issues with the present
> logic (for example, how nearly parallel intersections are treated by
> the logic) to see if those fixes make any difference to your complex
> case.  But essential to all of this bug-fixing process is a case (no
> matter how complicated) that can be replicated elsewhere.
>
>
> Alan
> __________________________
> Alan W. Irwin
>
> Astronomical research affiliation with Department of Physics and Astronomy,
> University of Victoria (astrowww.phys.uvic.ca).
>
> Programming affiliations with the FreeEOS equation-of-state
> implementation for stellar interiors (freeeos.sf.net); the Time
> Ephemerides project (timeephem.sf.net); PLplot scientific plotting
> software package (plplot.sf.net); the libLASi project
> (unifont.org/lasi); the Loads of Linux Links project (loll.sf.net);
> and the Linux Brochure Project (lbproject.sf.net).
> __________________________
>
> Linux-powered Science
> __________________________

Re: [Plplot-devel] Bug in notcrossed() function of plfill.c

[Arjen M. <Arj...@de...>]

Hi Phil,



> -----Original Message-----
> From: Phil Rosenberg [mailto:p.d...@gm...]

>
> In this special case the three short sides are all approximately 2 Plplot internal units
> long which fools the intersection test into thinking they are close to parallel to the
> test line. See
> notpointinpolygon() and notcrossed() functions. These three lines are therefore
> treated as non-intersectionctions even though the test line does intersect one of
> them. Finally the fourth section is just long enough and the location is just correct
> that the test line intersects it more than 2 pixels from each end. The result is that
> the point in polygon test sees 1 intersection instead of two and incorrectly
> concludes that the bottom left corner is inside the polygon.
>
> The final item that causes the bug to manifest is that the polygon is entirely outside
> of the plot area so no segments are drawable. The test that Plplot performs to see
> if the whole plot needs filling is that the bottom left corner is inside the fill polygon
> and all segments are outside the plot area. Hence the incorrect full fill.
>
> I'm still of the opinion that the notcrossed function should not use the 2 pixel
> fuzziness. At this point in the drawing we are dealing in integer pixels and we need
> only an epsilon test I think. I think the best fix is to change this. There are some
> sticking plaster solutions that would hide the problem but not really fix it in my
> opinion. I would really like to change the notcrossed function unless anyone has
> some really strong objections?
>
Thanks for constructing that example. This is the sort of things that makes "numerical geometry" an interesting topic ;). I have not studied the example in detail yet, but I am not entirely sure your proposed solution would work in all cases either. I will have a closer look.

Regards,

Arjen



DISCLAIMER: This message is intended exclusively for the addressee(s) and may contain confidential and privileged information. If you are not the intended recipient please notify the sender immediately and destroy this message. Unauthorized use, disclosure or copying of this message is strictly prohibited. The foundation 'Stichting Deltares', which has its seat at Delft, The Netherlands, Commercial Registration Number 41146461, is not liable in any way whatsoever for consequences and/or damages resulting from the improper, incomplete and untimely dispatch, receipt and/or content of this e-mail.

Re: [Plplot-devel] Bug in notcrossed() function of plfill.c

[Alan W. I. <ir...@be...>]

Hi Phil:

It was good to hear from you again.

On 2016-09-12 03:06+0100 Phil Rosenberg wrote:

> Hi All
> It's been a while. Sorry for my lack of activity over the summer.

I took quite a long break from PLplot this summer as well.  So no
worries about that.

>
> I've just picked up some Plplot items again on my to do list, starting
> with the fill problem that I reported a rather long time ago.
>
> I have sorted a minimal example to reproduce the bug - see attached.
> it turns out that a number of things need to come together to cause
> this problem. The example is based on example 12 and draws a very
> small trapezium just off the bottom left corner of the plot. however
> what happens instead is that the whole plot is filled. The way this
> works is that a test point is selected to the right of the fill shape
> and Plplot examines if a line between this point and the bottom left
> corner intersects the polygon segments to test if the bottom left
> corner is in the polygon. When the test is performed segments that are
> close to parallel (based on a ~2 pixel fuzziness) are flagged and in
> the end treat as a non-intersection. Also if the intersection is close
> to the end of a line (again 2 pixels is the limit) then the
> intersection is flagged as too close.
>
> In this special case the three short sides are all approximately 2
> Plplot internal units long which fools the intersection test into
> thinking they are close to parallel to the test line. See
> notpointinpolygon() and notcrossed() functions. These three lines are
> therefore treated as non-intersectionctions even though the test line
> does intersect one of them. Finally the fourth section is just long
> enough and the location is just correct that the test line intersects
> it more than 2 pixels from each end. The result is that the point in
> polygon test sees 1 intersection instead of two and incorrectly
> concludes that the bottom left corner is inside the polygon.
>
> The final item that causes the bug to manifest is that the polygon is
> entirely outside of the plot area so no segments are drawable. The
> test that Plplot performs to see if the whole plot needs filling is
> that the bottom left corner is inside the fill polygon and all
> segments are outside the plot area. Hence the incorrect full fill.

Thanks very much for providing this example and a thorough explanation
of what is going wrong on your particular platform, but I cannot
reproduce the problem here on Linux (gcc version 4.9.2 with
CFLAGS="-O3" which I presume makes some rounding go just the wrong way
so this fill bug is not exposed).  Instead of the coloured fill of the
whole plot you describe, all I get is a labelled blank plot (which is
I believe the result you desired). Assuming you confirm that good
result with gcc and CFLAGS="-O3", can you modify your example so it
triggers the fill bug(s) for all compiler and optimization level
cases?

@Arjen: I am interested whether gcc on Cygwin for this current example
triggers the bug or not.

>
> I'm still of the opinion that the notcrossed function should not use
> the 2 pixel fuzziness. At this point in the drawing we are dealing in
> integer pixels and we need only an epsilon test I think. I think the
> best fix is to change this. There are some sticking plaster solutions
> that would hide the problem but not really fix it in my opinion. I
> would really like to change the notcrossed function unless anyone has
> some really strong objections?

My opinion is this is an extraordinarily tricky topic where all the
currently active fill code (i.e., the part of the code not currently
removed by the C preprocessor) needs to be completely reviewed and
potentially rewritten. Also, I think the fuzziness logic (with all
bugs fixed in that code) should stay just in the interests of
providing some tolerance for numerical rounding errors.  For example,
even the article <https://en.wikipedia.org/wiki/Point_in_polygon>
talks of providing some numerical tolerance.  Note also, such
tolerance is certainly required for the integer case since minute
rounding errors in the floating point calculations that decide, for
example, whether a point is inside or outside a polygon can shift
integer results around by +/- 1.

I have a topic branch where I have already taken some substantial
steps along the above ideas (including at least one bug fix in our
current fuzzy logic in notcrossed). I temporarily halted work on that
topic some time ago, but assuming you can provide a test example that
triggers fill bugs regardless of compiler or optimization level, I
plan to take up that topic again where the first order of business
will be to compare (using imagemagick image differences) updated fill
algorithm results versus 5.11.1 results for all our standard examples
that use fill in some way.  (That test should turn up any unusual fill
artifacts in our examples that are generated by bugs in the original
or revised fill algorithm, and once that test is implemented it should
be done for any fill change from now on.) In addition, of course, I
will look carefully at your example to make sure the revised fill
algorithm produces the correct result for it.

Assuming you are able to provide the requested example which triggers
the fill bug regardless of rounding issues, and the above
plan meets with your approval, I would plan to start working on this
topic again just after the current release is out the door.

Note also there are still a number of relatively small issues I would
like to address for this release, but because of the break I mentioned
above, I made little progress on those this summer so that release
deadline is still indefinite and at least a month or two away.

Alan
__________________________
Alan W. Irwin

Astronomical research affiliation with Department of Physics and Astronomy,
University of Victoria (astrowww.phys.uvic.ca).

Programming affiliations with the FreeEOS equation-of-state
implementation for stellar interiors (freeeos.sf.net); the Time
Ephemerides project (timeephem.sf.net); PLplot scientific plotting
software package (plplot.sf.net); the libLASi project
(unifont.org/lasi); the Loads of Linux Links project (loll.sf.net);
and the Linux Brochure Project (lbproject.sf.net).
__________________________

Linux-powered Science
__________________________

Re: [Plplot-devel] Bug in notcrossed() function of plfill.c

[Arjen M. <Arj...@de...>]

Hi Phil, Alan,



> -----Original Message-----
> From: Alan W. Irwin [mailto:ir...@be...]
>
> @Arjen: I am interested whether gcc on Cygwin for this current example triggers
> the bug or not.
>
I will test it but it may be a one or two days before I get around to it.

Regards,

Arjen

DISCLAIMER: This message is intended exclusively for the addressee(s) and may contain confidential and privileged information. If you are not the intended recipient please notify the sender immediately and destroy this message. Unauthorized use, disclosure or copying of this message is strictly prohibited. The foundation 'Stichting Deltares', which has its seat at Delft, The Netherlands, Commercial Registration Number 41146461, is not liable in any way whatsoever for consequences and/or damages resulting from the improper, incomplete and untimely dispatch, receipt and/or content of this e-mail.

Re: [Plplot-devel] Bug in notcrossed() function of plfill.c

[Phil R. <p.d...@gm...>]

Hi Alan
I just built on Ubuntu (disabling F95 due to the issue I reported a
short while ago). I get the same full fill issue with wxWidgets, but
not with other drivers. I guess each driver may use slightly different
geometry so it ruins the example. Please could you try with wxWidgets
driver or let me know if you have tried that and it still fails.

Phil

On 12 September 2016 at 20:11, Alan W. Irwin <ir...@be...> wrote:
> Hi Phil:
>
> It was good to hear from you again.
>
> On 2016-09-12 03:06+0100 Phil Rosenberg wrote:
>
>> Hi All
>> It's been a while. Sorry for my lack of activity over the summer.
>
>
> I took quite a long break from PLplot this summer as well.  So no
> worries about that.
>
>
>>
>> I've just picked up some Plplot items again on my to do list, starting
>> with the fill problem that I reported a rather long time ago.
>>
>> I have sorted a minimal example to reproduce the bug - see attached.
>> it turns out that a number of things need to come together to cause
>> this problem. The example is based on example 12 and draws a very
>> small trapezium just off the bottom left corner of the plot. however
>> what happens instead is that the whole plot is filled. The way this
>> works is that a test point is selected to the right of the fill shape
>> and Plplot examines if a line between this point and the bottom left
>> corner intersects the polygon segments to test if the bottom left
>> corner is in the polygon. When the test is performed segments that are
>> close to parallel (based on a ~2 pixel fuzziness) are flagged and in
>> the end treat as a non-intersection. Also if the intersection is close
>> to the end of a line (again 2 pixels is the limit) then the
>> intersection is flagged as too close.
>>
>> In this special case the three short sides are all approximately 2
>> Plplot internal units long which fools the intersection test into
>> thinking they are close to parallel to the test line. See
>> notpointinpolygon() and notcrossed() functions. These three lines are
>> therefore treated as non-intersectionctions even though the test line
>> does intersect one of them. Finally the fourth section is just long
>> enough and the location is just correct that the test line intersects
>> it more than 2 pixels from each end. The result is that the point in
>> polygon test sees 1 intersection instead of two and incorrectly
>> concludes that the bottom left corner is inside the polygon.
>>
>> The final item that causes the bug to manifest is that the polygon is
>> entirely outside of the plot area so no segments are drawable. The
>> test that Plplot performs to see if the whole plot needs filling is
>> that the bottom left corner is inside the fill polygon and all
>> segments are outside the plot area. Hence the incorrect full fill.
>
>
> Thanks very much for providing this example and a thorough explanation
> of what is going wrong on your particular platform, but I cannot
> reproduce the problem here on Linux (gcc version 4.9.2 with
> CFLAGS="-O3" which I presume makes some rounding go just the wrong way
> so this fill bug is not exposed).  Instead of the coloured fill of the
> whole plot you describe, all I get is a labelled blank plot (which is
> I believe the result you desired). Assuming you confirm that good
> result with gcc and CFLAGS="-O3", can you modify your example so it
> triggers the fill bug(s) for all compiler and optimization level
> cases?
>
> @Arjen: I am interested whether gcc on Cygwin for this current example
> triggers the bug or not.
>
>>
>> I'm still of the opinion that the notcrossed function should not use
>> the 2 pixel fuzziness. At this point in the drawing we are dealing in
>> integer pixels and we need only an epsilon test I think. I think the
>> best fix is to change this. There are some sticking plaster solutions
>> that would hide the problem but not really fix it in my opinion. I
>> would really like to change the notcrossed function unless anyone has
>> some really strong objections?
>
>
> My opinion is this is an extraordinarily tricky topic where all the
> currently active fill code (i.e., the part of the code not currently
> removed by the C preprocessor) needs to be completely reviewed and
> potentially rewritten. Also, I think the fuzziness logic (with all
> bugs fixed in that code) should stay just in the interests of
> providing some tolerance for numerical rounding errors.  For example,
> even the article <https://en.wikipedia.org/wiki/Point_in_polygon>
> talks of providing some numerical tolerance.  Note also, such
> tolerance is certainly required for the integer case since minute
> rounding errors in the floating point calculations that decide, for
> example, whether a point is inside or outside a polygon can shift
> integer results around by +/- 1.
>
> I have a topic branch where I have already taken some substantial
> steps along the above ideas (including at least one bug fix in our
> current fuzzy logic in notcrossed). I temporarily halted work on that
> topic some time ago, but assuming you can provide a test example that
> triggers fill bugs regardless of compiler or optimization level, I
> plan to take up that topic again where the first order of business
> will be to compare (using imagemagick image differences) updated fill
> algorithm results versus 5.11.1 results for all our standard examples
> that use fill in some way.  (That test should turn up any unusual fill
> artifacts in our examples that are generated by bugs in the original
> or revised fill algorithm, and once that test is implemented it should
> be done for any fill change from now on.) In addition, of course, I
> will look carefully at your example to make sure the revised fill
> algorithm produces the correct result for it.
>
> Assuming you are able to provide the requested example which triggers
> the fill bug regardless of rounding issues, and the above
> plan meets with your approval, I would plan to start working on this
> topic again just after the current release is out the door.
>
> Note also there are still a number of relatively small issues I would
> like to address for this release, but because of the break I mentioned
> above, I made little progress on those this summer so that release
> deadline is still indefinite and at least a month or two away.
>
>
> Alan
> __________________________
> Alan W. Irwin
>
> Astronomical research affiliation with Department of Physics and Astronomy,
> University of Victoria (astrowww.phys.uvic.ca).
>
> Programming affiliations with the FreeEOS equation-of-state
> implementation for stellar interiors (freeeos.sf.net); the Time
> Ephemerides project (timeephem.sf.net); PLplot scientific plotting
> software package (plplot.sf.net); the libLASi project
> (unifont.org/lasi); the Loads of Linux Links project (loll.sf.net);
> and the Linux Brochure Project (lbproject.sf.net).
> __________________________
>
> Linux-powered Science
> __________________________

Re: [Plplot-devel] Bug in notcrossed() function of plfill.c

[Phil R. <p.d...@gm...>]

>>> I'm still of the opinion that the notcrossed function should not use
>>> the 2 pixel fuzziness. At this point in the drawing we are dealing in
>>> integer pixels and we need only an epsilon test I think. I think the
>>> best fix is to change this. There are some sticking plaster solutions
>>> that would hide the problem but not really fix it in my opinion. I
>>> would really like to change the notcrossed function unless anyone has
>>> some really strong objections?
>>
>>
>> My opinion is this is an extraordinarily tricky topic where all the
>> currently active fill code (i.e., the part of the code not currently
>> removed by the C preprocessor) needs to be completely reviewed and
>> potentially rewritten. Also, I think the fuzziness logic (with all
>> bugs fixed in that code) should stay just in the interests of
>> providing some tolerance for numerical rounding errors.  For example,
>> even the article <https://en.wikipedia.org/wiki/Point_in_polygon>
>> talks of providing some numerical tolerance.  Note also, such
>> tolerance is certainly required for the integer case since minute
>> rounding errors in the floating point calculations that decide, for
>> example, whether a point is inside or outside a polygon can shift
>> integer results around by +/- 1.
>>
>> I have a topic branch where I have already taken some substantial
>> steps along the above ideas (including at least one bug fix in our
>> current fuzzy logic in notcrossed). I temporarily halted work on that
>> topic some time ago, but assuming you can provide a test example that
>> triggers fill bugs regardless of compiler or optimization level, I
>> plan to take up that topic again where the first order of business
>> will be to compare (using imagemagick image differences) updated fill
>> algorithm results versus 5.11.1 results for all our standard examples
>> that use fill in some way.  (That test should turn up any unusual fill
>> artifacts in our examples that are generated by bugs in the original
>> or revised fill algorithm, and once that test is implemented it should
>> be done for any fill change from now on.) In addition, of course, I
>> will look carefully at your example to make sure the revised fill
>> algorithm produces the correct result for it.
>>
>> Assuming you are able to provide the requested example which triggers
>> the fill bug regardless of rounding issues, and the above
>> plan meets with your approval, I would plan to start working on this
>> topic again just after the current release is out the door.
>>
>> Note also there are still a number of relatively small issues I would
>> like to address for this release, but because of the break I mentioned
>> above, I made little progress on those this summer so that release
>> deadline is still indefinite and at least a month or two away.
>>
I agree that this is tricky, but feel this is something we can deal
with without being too troublesome. Algorithms and code already exist
to do this consistently - we're not the first to have to deal with it.
In fact here is a 7 line C implementation that deals with the ray
hitting a vertex correctly, but doesn't give any warning about if the
point is close to or on a segment.

I still don't understand why we need two whole plplot units of
fuzziness. I understand that we round and that can give us up to two
pixels of error. But surely we just accept that and work with the
rounded polygons as if they were exact - in fact they are exact
because they use integers.

for example we wish to plot two rectangles which end up with internal
coordinates of the opposite corners of (200,400.2),(600,600.4) and
(200,600.4),(600,800.1). We round these to give (200,400),(600,600)
and (200,600),(600,800). Now there is absolutely no count that the
point (350,600.2) is in the second rectangle. Of course if we were
using the original coordinates this point would have been in the first
rectangle. But we are not plotting the original coordinates, we are
plotting the rounded coordinates and that is what matters - the
coordinates we are plotting.

I would clearly like to get this fixed properly, but in the meantime
would anyone object if I apply a sticking plaster fix for this as it
is something I have hit about half a dozen times over the last six
months - I presume this is because I've been plotting some really high
resolution data. So I do really need to avoid the issue for now.

Phil

Re: [Plplot-devel] Bug in notcrossed() function of plfill.c

[Phil R. <p.d...@gm...>]

sorry meant "no doubt that the point" not "no count that the point"

On 12 September 2016 at 21:39, Phil Rosenberg <p.d...@gm...> wrote:
>>>> I'm still of the opinion that the notcrossed function should not use
>>>> the 2 pixel fuzziness. At this point in the drawing we are dealing in
>>>> integer pixels and we need only an epsilon test I think. I think the
>>>> best fix is to change this. There are some sticking plaster solutions
>>>> that would hide the problem but not really fix it in my opinion. I
>>>> would really like to change the notcrossed function unless anyone has
>>>> some really strong objections?
>>>
>>>
>>> My opinion is this is an extraordinarily tricky topic where all the
>>> currently active fill code (i.e., the part of the code not currently
>>> removed by the C preprocessor) needs to be completely reviewed and
>>> potentially rewritten. Also, I think the fuzziness logic (with all
>>> bugs fixed in that code) should stay just in the interests of
>>> providing some tolerance for numerical rounding errors.  For example,
>>> even the article <https://en.wikipedia.org/wiki/Point_in_polygon>
>>> talks of providing some numerical tolerance.  Note also, such
>>> tolerance is certainly required for the integer case since minute
>>> rounding errors in the floating point calculations that decide, for
>>> example, whether a point is inside or outside a polygon can shift
>>> integer results around by +/- 1.
>>>
>>> I have a topic branch where I have already taken some substantial
>>> steps along the above ideas (including at least one bug fix in our
>>> current fuzzy logic in notcrossed). I temporarily halted work on that
>>> topic some time ago, but assuming you can provide a test example that
>>> triggers fill bugs regardless of compiler or optimization level, I
>>> plan to take up that topic again where the first order of business
>>> will be to compare (using imagemagick image differences) updated fill
>>> algorithm results versus 5.11.1 results for all our standard examples
>>> that use fill in some way.  (That test should turn up any unusual fill
>>> artifacts in our examples that are generated by bugs in the original
>>> or revised fill algorithm, and once that test is implemented it should
>>> be done for any fill change from now on.) In addition, of course, I
>>> will look carefully at your example to make sure the revised fill
>>> algorithm produces the correct result for it.
>>>
>>> Assuming you are able to provide the requested example which triggers
>>> the fill bug regardless of rounding issues, and the above
>>> plan meets with your approval, I would plan to start working on this
>>> topic again just after the current release is out the door.
>>>
>>> Note also there are still a number of relatively small issues I would
>>> like to address for this release, but because of the break I mentioned
>>> above, I made little progress on those this summer so that release
>>> deadline is still indefinite and at least a month or two away.
>>>
> I agree that this is tricky, but feel this is something we can deal
> with without being too troublesome. Algorithms and code already exist
> to do this consistently - we're not the first to have to deal with it.
> In fact here is a 7 line C implementation that deals with the ray
> hitting a vertex correctly, but doesn't give any warning about if the
> point is close to or on a segment.
>
> I still don't understand why we need two whole plplot units of
> fuzziness. I understand that we round and that can give us up to two
> pixels of error. But surely we just accept that and work with the
> rounded polygons as if they were exact - in fact they are exact
> because they use integers.
>
> for example we wish to plot two rectangles which end up with internal
> coordinates of the opposite corners of (200,400.2),(600,600.4) and
> (200,600.4),(600,800.1). We round these to give (200,400),(600,600)
> and (200,600),(600,800). Now there is absolutely no count that the
> point (350,600.2) is in the second rectangle. Of course if we were
> using the original coordinates this point would have been in the first
> rectangle. But we are not plotting the original coordinates, we are
> plotting the rounded coordinates and that is what matters - the
> coordinates we are plotting.
>
> I would clearly like to get this fixed properly, but in the meantime
> would anyone object if I apply a sticking plaster fix for this as it
> is something I have hit about half a dozen times over the last six
> months - I presume this is because I've been plotting some really high
> resolution data. So I do really need to avoid the issue for now.
>
> Phil

Re: [Plplot-devel] Bug in notcrossed() function of plfill.c

[Alan W. I. <ir...@be...>]

On 2016-09-12 21:21+0100 Phil Rosenberg wrote:

> Hi Alan
> I just built on Ubuntu (disabling F95 due to the issue I reported a
> short while ago). I get the same full fill issue with wxWidgets, but
> not with other drivers. I guess each driver may use slightly different
> geometry so it ruins the example. Please could you try with wxWidgets
> driver or let me know if you have tried that and it still fails.

I confirm the full fill issue with -dev wxwidgets.  So it appears we
finally have a reproducible example of a problem, but you should
follow up by figuring out exactly why wxwidgets shows the issue and
our other devices currently do not and ideally you will be able to
follow up even further by adjusting the example slightly so all our
devices show the issue.

Alan
__________________________
Alan W. Irwin

Astronomical research affiliation with Department of Physics and Astronomy,
University of Victoria (astrowww.phys.uvic.ca).

Programming affiliations with the FreeEOS equation-of-state
implementation for stellar interiors (freeeos.sf.net); the Time
Ephemerides project (timeephem.sf.net); PLplot scientific plotting
software package (plplot.sf.net); the libLASi project
(unifont.org/lasi); the Loads of Linux Links project (loll.sf.net);
and the Linux Brochure Project (lbproject.sf.net).
__________________________

Linux-powered Science
__________________________