From: Phil R. <p.d...@gm...> - 2015-06-16 09:30:20
|
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. |