Archive

Archive for June, 2007

PolygonF and Polygon code posted.

June 26, 2007 Comments off

I have just posted the PolygonF code I discussed in Testing to see if a Point is within a Polygon. The file includes both PolygonF and Polygon classes. Visit the Free Code page or download it from the PolygonF home page.

Categories: .NET 2.0, C# 2.0

Testing to see if a Point is within a Polygon

June 7, 2007 8 comments

I’m on a brief respite from my Compact Framework woes: I am instead in the process of rewriting a very old Java Sketching program. Our legacy application stores text-based vectors for drawing 2D sketches of the external footprint of structures. Until I wrote this Java program in 2001, our sketches were always rendered in Text. Yes, I said TEXT. Dashes, underlines, plus signs, forward slashes and backward slashes – well you get the idea. We began displaying some of this information on the Internet and needed something a little more modern. This program in particular reads through our entire database and creates all the Sketches as JPGs, storing them locally on the C drive. There is a companion program that creates and displays in a GUI a single sketch requested by the user (via a function key in our iSeries RPG program).

In fact, one interesting note about it: this was the first PC based program I ever wrote. Since I was in the throes of learning Java anyway (my first PC or Web related language), I took on the task of making something out of nothing. Of course, I had no idea what I was getting in to, but I ended up with a crash course in Object Oriented design, JDBC and disconnected databases, Swing (shoot me if I ever go down THAT path again!), and of course 2D graphics. For someone who did not know the first thing about GUI development, this project was way too much for a first try. But 5-6 months of reading, studying, trial and error, and labor and I ended up with a workable program.

Don’t get me wrong: it is an abhorrent behometh, chock full of bad techniques and poor implementations. Worst of all, it is a Java program, and on more than one occasion has broken due to updates in the JRE. Couple that with the fact that it is slow as death (again, certainly my own fault) and almost NEVER deploys properly thanks to myriad Classpath woes and divergent operating system. After my last machine bit the dust, I never even bothered to recreate my Java environment (as I had completely moved on to VS2003 by then). As a result, legitimate complaints by users have gone unaddressed, largely because of my own unwillingness to return to Java.

Fast forward to today: now experienced in Java, PHP, Perl, and of course my favorite, C#, and having done quite a bit of GUI and OO development in the intervening years, I finally decided to tackle the rewrite of my old behometh. I rewrote the engine Wednesday afternoon, and by the end of the day had rudimentary sketching working. 5 Hours to do what originally took 5 months. I spent part of yesterday working on the Text labelling, which is quite a bit more difficult than the actual drawing. I’ll probably spend another few days hashing all that out.

During my labors, though, I discovered a shocking omission in the C# language: there is no Polygon Class. Drawing the Polygons is easy enough using the Graphics DrawPolygon member, but as I am inserting labels, I need to check and see if the proposed position is within the Bounds of the Polygon, and I would like to center some labels, so I need to know what the center point is, etc., etc. So, I quickly whipped up my own Polygon class. The class manages a read-only Array of PointF objects, so right now it is immutable. I may change that if the need arises, but for now I need to work with the complete closed Polygon.

It is not overly complex or anything like that, but here are some of the key features

  • Bounds of the Polygon
  • CenterPoint of those Bounds
  • Minimum and Maximum X and Y
  • Number of Points
  • Determine if a PointF is in the Bounds
  • Calculate Area of the Polygon
  • Determine if the Polygon Contains a PointF (different than above)

That last one was a real challenge. A PointF could easily be in the Rectangular Bounds of a Polygon but not inside the Polygon itself, so the Contains check determines whether or not the PointF is actually inside the boundaries of the Polygon. This required more math than I was able to come up with, so I turned to my trusty friend Google and found this link. At this site, you can find the formula originally written in Fortran and converted to C. Naturally, I converted it on to C#, and I am now sharing that code with you.

public bool Contains(PointF pt)
{
    bool isIn = false;
    if (IsInBounds(pt))
    {
        int i, j = 0;
        for (i = 0, j = NumberOfPoints - 1; i < NumberOfPoints; j = i++)
        {
            if (
                (
                 ((_pts[i].Y <= pt.Y) && (pt.Y < _pts[j].Y)) || ((_pts[j].Y <= pt.Y) && (pt.Y < _pts[i].Y))
                ) &&
                (pt.X < (_pts[j].X - _pts[i].X) * (pt.Y - _pts[i].Y) / (_pts[j].Y - _pts[i].Y) + _pts[i].X)
               )
            {
                isIn = !isIn;
            }
        }
    }
    return isIn;
}

You can see that I bypass any points that are outside the rectangular bounds altogether since there is no point in running the rest of the checks at that point, but that is really the only fundamental change I made. Of course, I return an actual Boolean but the orginial C returned an int.

When I complete the rest of the Polygon code, I’ll post it in the Free Code section. This one is actually PolygonF for using floats, but it could easily be modified to use Integers instead.

UPDATE:

Download PolygonF.

Categories: .NET 2.0, C# 2.0
Follow

Get every new post delivered to your Inbox.