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.rosenb...@gmail.com> 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 <arjen.mar...@deltares.nl> 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...@beluga.phys.uvic.ca]
>>> Sent: Monday, June 15, 2015 11:59 PM
>>> To: Phil Rosenberg
>>> Cc: Arjen Markus; plplot-devel@lists.sourceforge.net
>>
>>> 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...@beluga.phys.uvic.ca>
>>> > Sent: ‎15/‎06/‎2015 19:18
>>> > To: "Phil Rosenberg" <p.d.rosenb...@gmail.com>
>>> > Cc: "Arjen Markus" <arjen.mar...@deltares.nl>;
>>> > "plplot-devel@lists.sourceforge.net"
>>> > <plplot-devel@lists.sourceforge.net>
>>> > 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.

Attachment: intersect.patch
Description: Binary data

------------------------------------------------------------------------------
_______________________________________________
Plplot-devel mailing list
Plplot-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/plplot-devel

Reply via email to