Announcement

Collapse
No announcement yet.

Learning GRAPHICS

Collapse
X
 
  • Filter
  • Time
  • Show
Clear All
new posts

  • Learning GRAPHICS

    I've never used the GRAPHICS commands before, and this week while down with a bad cold, I started to learn some of them. One of the things I started with was:

    Code:
       GRAPHIC ATTACH hTriangle, 0
       GRAPHIC POLYGON PlotPoints, %BLUE
       GRAPHIC PAINT (x, y) , %BLUE
    but I was having trouble getting the triangle to paint, and not the space around it...

    My estimates for x and y were often incorrect. I needed to find a way to be absolutely sure of a point inside the shape.

    I did a LOT of research, reading, and test coding, and tried at least three methods. I settled on one that's straightforward and easily handles anything I could throw at it.


    I'm posting it here as my way of saying thank you to all who have helped me in the past, in the hope that it might be of some small help.

    After I do some more cleanup, I'll post the entire test program. It does have some pretty cool routines...

    -John




    Here's the change:
    Code:
       GRAPHIC ATTACH hTriangle, 0
       GRAPHIC POLYGON PlotPoints, %BLUE
       lRet = FindPointInTriangle (PlotPoints, StartPoint)
       GRAPHIC PAINT (StartPoint.x, StartPoint.y) , %BLUE
    And here's the function; works like a champ with triangles of ANY shape:

    Code:
    FUNCTION FindPointInTriangle (BYREF PointsList AS PolyArray, BYREF RetVal AS PolyPoint) AS LONG
       'A known point inside a triangle is it's "centroid", where the medians of the angles intersect
       RetVal.x = (PointsList.xy(1).x + PointsList.xy(2).x + PointsList.xy(3).x) / 3
       RetVal.y = (PointsList.xy(1).y + PointsList.xy(2).y + PointsList.xy(3).y) / 3
       FUNCTION = %TRUE
    END FUNCTION


    Supporting TYPES:

    Code:
    TYPE PolyPoint
      x AS SINGLE
      y AS SINGLE
    END TYPE
    
    TYPE StraightLine
       p1 AS PolyPoint      'some point that is on the line
       p2 AS PolyPoint      'some other point that is on the line
       SegLen AS SINGLE     'optional
       Rise   AS SINGLE     'optional
       Run    AS SINGLE     'optional
       Slope  AS SINGLE     'optional
    END TYPE
    
    TYPE PolyArray
      COUNT AS LONG
      xy(1 TO 100) AS PolyPoint    'Can't redim dynamically, but extras aren't harmful
    END TYPE
    
    TYPE Triangle
       Points AS PolyArray  ' TriangleName.Points.xy(1).x
       S12 AS StraightLine  'Side                
       S23 AS StraightLine  'Side
       S13 AS StraightLine  'Side
       A12 AS SINGLE        'Angle
       A23 AS SINGLE        'Angle
       A13 AS SINGLE        'Angle
       Centroid AS PolyPoint'intersection of medians
       TriangleClassA AS STRING *  7  'Classifcation based on Angles  (eg, right, obtuse, acute)
       TriangleClassS AS STRING * 11  'Classifcation based on Sides   (equilateral, scalene, isoceles)
                                      ' lengths accomodate full text descriptors
                  ' (if we stored only the first char, we'd need programatic interpretations later)
    END TYPE

  • #2
    John,

    The method you posted will probably work well enough for most applications, but you may experience trouble when your point is nearly on a triangle edge or very close to one of the verticies. If your triangles are close to being degenerate, you also may have trouble determining if the point is inside or outside. As a test try locating a point on a triangle edge or on one of the triangle verticies and see what happens.

    The best method I have found to determine if a point is inside or outside of a triangle is through the use of barycentric coordinates.
    Later...

    JR

    "When governments fear the people there is liberty. When people fear the government there is tyranny." - Thomas Jefferson

    Comment


    • #3
      Degenerate triangles? (Sounds like something from a bad novel... Or, are they areas of the ocean off the coast of Florida where degenrates disappear?) (Hey, can you tell I'm happy to not be running a fever today?)

      Actually had to look it up, I'd never come across the term.
      Mathwords.com gives the following definitions:
      "A degenerate triangle is the "triangle" formed by three collinear points. It doesn’t look like a triangle, it looks like a line segment."
      "Collinear" is defined as: "Lying on the same line."
      and "line" is defined as: "The geometric figure formed by two points. A line is the straight path connecting two points and extending beyond the points in both directions."

      Therefore, a "Degenerate triangle" is one whose three vertices all fall on the same line. Translation: a line (two points) having a third identified point.

      OK, I understand it. However, I'm not concerned about it.

      The function finds the "centroid" point. I've done some testing, and have obtained what appears to be a valid result for an isoceles triangles with equal sides in excess of 100,000 pixels and an opposite side of only 1 pixel. Also, if it's of any value, PB does PAINT the area properly with the given point... (I have to add more than 1.1 pixels to the y-coordinate in order to get PB to paint outside the shape...makes sense: line width plus a bit)

      Note that the function does not test a given point. Rather, given the triangle's three point coordinates, the function simply returns the centroid point.

      I suppose if one wanted to, they could screen the function's input parameters to ensure they aren't too small. But otherwise, the function is perfect for my needs at this time.

      I read about the barycentric method but I don't have working PB code for it yet. I did find a C version, but my C skills are minimal. It will take me awhile to translate... FYI I also tried the "shoot a ray and see if there's an intercept" method. Much more complex, for no perceptible gain (under these circumstances).

      Thanks for your comments and for stirring up the pot; I appreciate the opportunity to explore new "angles" of this problem area...

      Now, stay tuned until I get to the larger "point-in-polygon" problem...

      -John
      Last edited by John Montenigro; 10 Nov 2008, 02:36 PM. Reason: clarify two sentences

      Comment


      • #4
        John,

        Thanks.

        Somehow I got the idea from your first post that the eventual functionality of your routines was to determine if a point is inside or outside of a triangle. But that is not what you wrote, so my apologies.

        You are correct about the definition of degenerate triangles. The thing you need to consider is the possibility of triangles that are almost degenerate, where the geometry is related to your mathematical precision. Again, if you won't be creating "bad" triangle geometry then it won't be much of a problem. But just in case you want to use this routine for something else, then degenerate triangles should be a design consideration.

        I read about the barycentric method but I don't have working PB code for it yet.
        Barycentric coordinates allow you to determine whether a point is inside/outside a triangle without using the intrinsic trig functions to handle angles. It is very fast.

        FYI I also tried the "shoot a ray and see if there's an intercept" method. Much more complex, for no perceptible gain (under these circumstances).
        Yes, for a triangle this is a bit of overkill. This method is used to determine whether a point is inside/outside a complex polygon. For example, a complex polygon shaped like a "C". Depending on the point you wish to check it may be possible to cross the boundary of the "C" by your ray more than once. The conventional wisdom is if your ray crosses the boundary an odd number of times the point is inside, even crossings, point is outside.

        A good book on graphics programming is "Visual Basic Graphics Programming" by Rod Stephens. Has lots of source code examples for VB but are easily converted to PB.
        Later...

        JR

        "When governments fear the people there is liberty. When people fear the government there is tyranny." - Thomas Jefferson

        Comment


        • #5
          Thanks, John, good info.

          "Barycentric coordinates allow you to determine whether a point is inside/outside a triangle without using the intrinsic trig functions to handle angles. It is very fast."

          I'm looking forward to sinking my teeth into this!

          -JohnM

          Comment


          • #6
            John,

            There is a 3D graphics engine on the "Source Code" forums called "PBDEX3D", or something similar, that has some good stuff that may interest you too. Patrice Terrier posted this 3D engine.
            Later...

            JR

            "When governments fear the people there is liberty. When people fear the government there is tyranny." - Thomas Jefferson

            Comment


            • #7
              The latest PBDEX3D engine is there:
              http://www.jose.it-berater.org/smffo...p?topic=1139.0
              Patrice Terrier
              www.zapsolution.com
              www.objreader.com
              Addons: GDImage.DLL 32/64-bit (Graphic library), WinLIFT.DLL 32/64-bit (Skin Engine).

              Comment


              • #8
                Thanks JR and Patrice!

                PBDEX is so far beyond my abilities, it'll take till next week for me to get grounded again! But I have been studying it, and will be playing with it over the next few months.

                Meanwhile, I figured I'd post the code that I've been developing. This is scruffy, rough-edged code that I have been using to experiment with and tweak and make mistakes with, so it's not elegant. However, it is well commented, so you can tell what I was doing...

                I think that some of the stuff in the program will be of interest to many and of use to some. Please take a look at:
                http://www.powerbasic.com/support/pb...132#post302132 and let me know what you think.

                In particular, check out:
                - the "Set_(shape)_Properties" routines,
                - the "FindPointIn_(shape)_" routines,
                but especially:
                - the "AngleOppSideC" function!
                (Given only the three coordinate points for the vertices of a triangle, it solves all the other properties. I'm kinda pleased with this!)


                Thanks to all who provided feedback and guidance! Much appreciated!

                -John

                Comment


                • #9
                  John,

                  In your studies you may want to become familiar with vectors and their relationship with angles. Check out any Calculus book or books on analytical geometry as there will be a discussion on vectors and their application in solving geometric problems. If you find the above types of books too dry then try to find some books on game programming. One of the advantages of the game programming books is the authors try to optimize various graphics algorithms which can be of use to you.

                  One example of the value of using vectors is that you can shorten the "AngleOppSideC" function considerably while expanding your function to handle any type of triangle.

                  You may also find that your line slope may fail if you try to determine the slope of a vertical line. Using vectors can help you here too.

                  Good job, keep plugging away.
                  Later...

                  JR

                  "When governments fear the people there is liberty. When people fear the government there is tyranny." - Thomas Jefferson

                  Comment


                  • #10
                    Thanks JR, I appreciate the feedback and further guidance. I'm going to have to expand my To-Do list! Vectors, eh? You realize what kind of trouble I'm going to create when I get into that!?!

                    -John

                    Comment


                    • #11
                      Originally posted by John Montenigro View Post
                      Thanks JR, I appreciate the feedback and further guidance. I'm going to have to expand my To-Do list! Vectors, eh? You realize what kind of trouble I'm going to create when I get into that!?!

                      -John
                      Dunno anything about vectors except one thing. It's what AutoCad uses to scale its drawings. (and drawing don't get much more accurate than AutoCad). I recall one really impressive early demo (circa version II). The drawing was of the universe showing all the planets and galaxies.

                      One could drill down (magnify) repeatedly until the Earth and Moon showed up. Then even further on the Moon until it showed the Lunar Lander and a "First Step For Mankind" plaque.

                      When you get Vectors figured out, John, be sure to pass it along (in DDT terms, only please {grin})

                      ==========================================================
                      Every war when it comes, or before it comes,
                      is represented not as a war but as an act of self-defense
                      against a homicidal maniac.
                      George Orwell
                      ==========================================================
                      It's a pretty day. I hope you enjoy it.

                      Gösta

                      JWAM: (Quit Smoking): http://www.SwedesDock.com/smoking
                      LDN - A Miracle Drug: http://www.SwedesDock.com/LDN/

                      Comment


                      • #12
                        John,

                        Vectors, eh? You realize what kind of trouble I'm going to create when I get into that!?!
                        Now now John, don't despair, once you understand the concept of vectors, especially when you can calculate the COS of an angle between two vectors, for example, you will be off and running. Trust me on this, the vector light bulb will come on and you will wonder how you ever got along without them.
                        Later...

                        JR

                        "When governments fear the people there is liberty. When people fear the government there is tyranny." - Thomas Jefferson

                        Comment


                        • #13
                          "When the vector light bulb comes on..." I wouldn't be holding my breath waiting on that event!!!

                          Realisticly, I won't be able to start researching and reading about vectors until the Christmas/New Year's timeframe.

                          But I do appreciate your encouragement, and I promise I will look into it.

                          -John

                          Comment


                          • #14
                            John,

                            I just thought when (not if) your vector light bulb came on you will experience a thrill by discovering vector properties by yourself. Vectors have so many uses in graphics and computational geometry they are well worth understanding.

                            I will help anyway I can.

                            Be of good cheer, have lots of fun!
                            Later...

                            JR

                            "When governments fear the people there is liberty. When people fear the government there is tyranny." - Thomas Jefferson

                            Comment


                            • #15
                              Not to be a noodge John but I just dl'ed you code (.zip) and tried running it. Got a "Duplicate Name" error in Function intersect(ByVal x1 As Double, _ (inside the Include).

                              The code is way too over my head for me to run it down and it's unlikely I would have any use/need for it anyway, but I thought you'd like to know.

                              =======================================
                              Enjoy things which are pleasant;
                              that is not the evil:
                              Evil is the reducing of our moral self
                              to slavery by them that is.
                              Thomas Carlyle
                              =======================================
                              It's a pretty day. I hope you enjoy it.

                              Gösta

                              JWAM: (Quit Smoking): http://www.SwedesDock.com/smoking
                              LDN - A Miracle Drug: http://www.SwedesDock.com/LDN/

                              Comment


                              • #16
                                Gosta,

                                I just d/l'd the zip, extracted it, opened and compiled and ran with no errors.

                                I'm using PBCC5.0. If you're using an earlier compiler, you may want to edit INTERSECT1.inc and un-comment the DECLARE FUNCTION.

                                That's the only problem I can imagine would cause your difficulty?????

                                -John

                                Comment


                                • #17
                                  Am using PB9, so I imagine that's a good starting point for differences. I never noticed the PBCC5 comment in the code. Not to worry about, John. Or spend any effort remedying. As I said I was only trying it out for curiousity's sake. It's not something I think I would ever have a need for myself. Flunked trigonometry over 50 years ago. Not much hope of doing any better today {sigh}.

                                  ====================================
                                  "Only two things are infinite,
                                  the universe and human stupidity,
                                  and I'm not sure about the former."
                                  Albert Einstein (1879-1955)
                                  ====================================
                                  It's a pretty day. I hope you enjoy it.

                                  Gösta

                                  JWAM: (Quit Smoking): http://www.SwedesDock.com/smoking
                                  LDN - A Miracle Drug: http://www.SwedesDock.com/LDN/

                                  Comment


                                  • #18
                                    Originally posted by Gösta H. Lovgren-2 View Post
                                    Am using PB9, so I imagine that's a good starting point for differences. I never noticed the PBCC5 comment in the code. Not to worry about, John. Or spend any effort remedying.
                                    No worry! But if you take the time to download and try it, I want you to be successful running it, and I'm willing to help to whatever extent I can.

                                    I was only trying it out for curiousity's sake. It's not something I think I would ever have a need for myself. Flunked trigonometry over 50 years ago. Not much hope of doing any better today {sigh}.
                                    Funny - that's kinda why I got into this in the first place: I have no real need for GRAPHICS and never use trig, but I wanted to explore something that I was not comfortable with. -- Each month I try to give myself a "learning problem" to solve, something to make me expand my knowledge and/or skill. I may only be a hobbyist programmer, but I am determined to keep on learning.

                                    I was miserable in trig, too (only 40 years ago). But now I have some exposure to PB graphics, some exposure to higher math functions, and I've learned a whole lot about solving point-in-polygon problems (well for now, mostly triangles).

                                    If you take the time to walk through the code using the debugger, maybe you'll pick up something useful. At least, that's my reason for posting it. I try to leave a lot of comments so that if others want to modify it, they can readily see what to keep and where they can go in another direction.

                                    And yes, I know that at some point I'm going to have to improve my coding style... just after I learn COM and Objects (and pointers and ...)!

                                    Comment


                                    • #19
                                      Thanks the offer John. I'll probably take you up on it one day. (Us Jersey guys gotta stick together in this unforgiving world. {grin})

                                      BTW I was thinking a little more on those AutoCad vectors and remember looking into the .dat files for the "Universe" drawing. IIRC (long while ago) there were only a half dozen or so numbers in each data line. And not a whole lot of lines at that for such a complex drawing. I was amazed a how much use could be made from such little data using vectors.
                                      It's a pretty day. I hope you enjoy it.

                                      Gösta

                                      JWAM: (Quit Smoking): http://www.SwedesDock.com/smoking
                                      LDN - A Miracle Drug: http://www.SwedesDock.com/LDN/

                                      Comment


                                      • #20
                                        Gösta,

                                        A single 3D vector can describe direction and magnitude (length). So it is possible, in combination with a 3D point, to define another point in space. Or one can size the vector (change its length) and locate another point in space along the line of the vector. Just one of the vector's many uses.

                                        The fact that AutoCAD's drawing file is vector based makes it ideal for use in modeling real world applications such as buildings, machinery, highways, etc. I don't know what the specific AutoCAD application of the .DAT file is, but the actual drawing information is stored in the .DWG file and I'm sure contains a lot more geometry data than what you found in the .DAT file.
                                        Later...

                                        JR

                                        "When governments fear the people there is liberty. When people fear the government there is tyranny." - Thomas Jefferson

                                        Comment

                                        Working...
                                        X