.NET

Entity Framework Spatial: A Real World Example

Jason Follas — Wed, 27 Jul 2011 17:57:46 GMT

Background

From the Wikipedia article, Leadership in Energy and Environmental Design (LEED) is described as “an internationally recognized green building certification system, providing third-party verification that a building or community was designed and built using strategies intended to improve performance in metrics such as energy savings, water efficiency, CO₂ emissions reduction, improved indoor environmental quality, and stewardship of resources and sensitivity to their impacts.”

In my own words, LEED is a certification system that awards points for following certain environmentally-friendly practices when constructing a building. In the end, a building can be qualify for one of four different levels of certifications, based on the number of points: Certified, Silver, Gold, Platinum. There are often tax benefits associated with having a LEED certification, and many new government buildings (especially Federal) are required to be LEED certified.

Two points in particular (out of of 100, or so) from the LEED checklist are related to geospatial data. One point is awarded if at least 20% of the building materials (by cost) used in construction were manufactured within 500 miles of the job site. A second point is awarded if 10% of the raw materials of those building materials were extracted, harvested, or recovered within 500 miles of the job site.

As a window glass manufacturer, Tempuri Glass is often asked to provide data about its products that are being considered for use in construction. Tempuri Glass may have a certain advantage over its competitors if it can quickly show that its products would count towards these two points for any arbitrary job site.

Data

Tempuri is a simple organization, making only a single type of product (Soda Lime glass) that is then cut into different sizes per order. Therefore, regardless of how many different sized glass panes are produced by a given facility, the ingredients for that glass is the same. The formulas used will be different between facilities, though, since the raw ingredients will be sourced from different locations, and adjustments may need to be made to the ratios due to environmental factors (things like: elevation, temperature, humidity, etc).

So, for our data model, we just need to know where each facility is, and then the formula used to make the glass at that facility (including the ingredients of that formula and the location where they were harvested from).

Within the data store, the [Geocode] columns of the Facility and FormulaComponent tables use the SQL Server geography type. This is useful for the large-scale/real-world distance calculations that Tempuri Glass needs to perform, since the way that you calculate distance on an sphere or ellipsoid (like the Earth) is vastly different than on a flat map.

In the Entity Framework model (using the June 2011 CTP), the SQL Server geography types are mapped as the new System.Data.Spatial.DbGeography type. This makes the geospatial data a first class citizen of our data model, and not just a castable opaque BLOB, as was the case in the past.

Geospatial data can take on many forms, including Points, Line Strings, Polygons, and collections of these shapes. Even though it’s not apparent from the data model, our [Geocode] data will contain only Points (i.e., a single Latitude/Longitude pair). Likewise, a job site will be specified as a single Point, though there is no hard requirement for this because distance can still be calculated between a Polygon and a Point with no coding change required.

Facility Sample Data

FacilityID	FacilityName	City	State	Geocode
1	Greenfield, IA	Greenfield	IA	POINT (-94.4547843933106 41.3151755156904)
2	Spring Green, WI	Spring Green	WI	POINT (-90.053981 43.17431)
3	Tomah, WI	Tomah	WI	POINT (-90.477058 43.989319)
4	Fremont, IN	Fremont	IN	POINT (-84.9314403533936 41.7186070559443)
5	Fargo, ND	Fargo	ND	POINT (-96.8667125701904 46.8985894795683)
6	Waxahachie, TX	Waxahachie	TX	POINT (-96.8427014350891 32.4424403136322)
7	Hood River, OR	Hood River	OR	POINT (-121.51526927948 45.630620334868)
8	Vinton, VA	Vinton	VA	POINT (-79.863876 37.263329)
9	Casa Grande, AZ	Casa Grande	AZ	POINT (-111.78155422210693 32.882073958767954)
10	Mountain Top, PA	Mountain Top	PA	POINT (-75.896477 41.141327)
11	Winlock, WA	Winlock	WA	POINT (-122.926218509674 46.5449155194259)
12	Durant, OK	Durant	OK	POINT (-96.4133548736572 34.0001619910696)
13	Mooresville, NC	Mooresville	NC	POINT (-80.7865476608277 35.6316281732984)

FormulaComponent Sample Data

FormulaComponentID	Name	Percentage	SourceLocation	Geocode
14	Limestone	13	Genola, UT	POINT (-111.808204650879 40.0098667779887)
1	Silica Sand	75	Houck, AZ	POINT (-109.241695404053 35.2062151838369)
27	Soda Ash	12	Trona, CA	POINT (-117.311668395996 35.6955040738332)
15	Limestone	13	Genola, UT	POINT (-111.808204650879 40.0098667779887)
2	Silica Sand	75	Houck, AZ	POINT (-109.241695404053 35.2062151838369)
28	Soda Ash	12	Trona, CA	POINT (-117.311668395996 35.6955040738332)
16	Limestone	13	Chicago, IL	POINT (-87.6176834106445 41.5738476278005)
3	Silica Sand	75	Overton, NV	POINT (-114.4313621521 36.5146030619859)
29	Soda Ash	12	Green River, WY	POINT (-109.448783397675 41.5090754257687)

Spatial Querying Algorithm

Input: Job Site Latitude/Longitude

Steps:

A. Query for closest facility to Job Site within 500 miles:

Calculate the distance between the job site and each facility.
Filter the list of facilities to just those where distance < 500 miles.
Order the list of facilities by distance in ascending order.
The first element (if any) will be the closest facility, and also signifies that the product qualifies as being manufactured within 500 miles

B. If there is a facility within 500 miles, then sum the percentage of formula components that were sourced from within 500 miles of the Job Site:

Calculate the distance between the job site and each of the facility’s formula components
Filter the list of formula components to just those where distance < 500 miles
Sum the Percentages

Output: Boolean of whether the product qualifies; Percentage of the product’s ingredients that qualifies.

Implementation

Before we can calculate distance using an instance method of the DbGeography type, we need to actually create an instance to represent the Job Site. DbGeography is immutable and does not have a constructor, so instead, a static method must be called to create a new object. There are a number of these factory methods available to create specific kinds of shapes (Point, Line String, Polygon, etc) given different kinds of input (text, byte arrays).

For simplicity, let’s use the .Parse() method, which accepts Well-Known Text (WKT) as input, and assumes a Spatial Reference ID of 4326 (the same coordinate system that GPS and internet mapping sites use).

Note: WKT uses a (Longitude, Latitude) ordering for points, which adheres to the same concept as (X, Y) ordering for Cartesian coordinates.

private static DbGeography CreatePoint(double latitude, double longitude)
{
   return DbGeography.Parse(String.Format("POINT({1} {0})", latitude, longitude));
}

The first spatial query, written as a LINQ expression, finds the closest qualifying facility. Since SRID 4326 uses meters as the unit of measure, we need to convert 500 miles into meters within the predicate:

private Facility GetNearestFacilityToJobsite(DbGeography jobsite)
{
   var q1 = from f in context.Facilities
            let distance = f.Geocode.Distance(jobsite)
            where distance < 500 * 1609.344
            orderby distance
            select f;

   return q1.FirstOrDefault();
}

Assuming that a facility was returned, a second LINQ expression can be used to find the sum of Percentage from qualifying Formula Components:

private decimal SumQualifyingPercentages(Facility nearestFacility, DbGeography jobsite)
{
   var q2 = from fc in nearestFacility.Formula.FormulaComponents
            where fc.Geocode.Distance(jobsite) < 500 * 1609.344
            select fc;

   return q2.Sum(c => c.Percentage.GetValueOrDefault(0));
}

Finally, putting all of the parts together (using a Tuple<> for the output):

private Tuple GetResults(double latitude, double longitude)
{
   DbGeography jobsite = CreatePoint(latitude, longitude);
   Facility nearestFacility = GetNearestFacilityToJobsite(jobsite);

   if (nearestFacility != null)
   {
      return new Tuple(true, SumQualifyingPercentages(nearestFacility, jobsite));
   }

   return new Tuple(false, 0);
}

private void PerformQuery()
{
   double latitude = 47.63752;
   double longitude = -122.13343;

   var results = GetResults(latitude, longitude);
}

Windows Azure platform AppFabric Access Control: Using the Token

Jason Follas — Sat, 27 Mar 2010 19:46:01 GMT

In previous articles (Part 1, Part 2, Part 3), ACS was configured to process token requests from different Issuers, and a Customer application obtained a SWT token from ACS using an intermediate service (that represented its particular Issuer).

Now that the application has a token, ACS is not needed again until that token expires. This article will show how to use that token in order for the Customer application to call the Bartender web service.

Note: OAuth WRAP defines terminology for parts of the system as follows:

The Customer application is known as the Client.
The Bouncer (ACS) is known as the Authorization Server.
The Bartender web service is known as the Protected Resource.

Passing a Token from Client to Protected Resource

We had to conform to OAuth WRAP specifications while acquiring a token from ACS, but there’s no actual requirement for how a Client must pass that token to the Protected Resource. An Architect or Developer could come up with any contract that they would like to use. However, a best practice would be to continue using the OAuth WRAP specification as guidance.

WRAP defines three different ways that a Protected Resource can accept a token:

In the HTTP header
In the Query String
In the Form contents

OAuth WRAP suggests that a Protected Resource at least support the HTTP header method, but makes no mandates. If a Protected Resource is able to implement all three, then it would be in the position to support the widest variety of Clients. However, if the Protected Resource is unable to use HTTP headers but could use a value passed in the Query String, then there would be nothing in the WRAP specification to prevent only that implementation.

Regardless of the method used, an unauthorized request (perhaps due to a bad or missing token) will result in a HTTP status of 401 Unauthorized, and a header in the response containing: WWW-Authenticate: WRAP

Tokens passed in the HTTP header are expected to use the “Authorization” header, with this header’s value containing the text: WRAP access_token="tokenstring". Note that tokenstring is a placeholder for the actual SWT token obtained from ACS and does not need to be URL Encoded.

Example (using a System.Net.WebClient class):

  string headerValue = string.Format("WRAP access_token=\"{0}\"", HttpUtility.UrlDecode(token)); 
  var client = new WebClient();            
  client.Headers.Add("Authorization", headerValue);

Tokens passed in either the Query String or in Form Contents are expected to use the name/value pair of: wrap_access_token=tokenstring. Again, tokenstring is a placeholder for the actual SWT token obtained from ACS, and should be URL Encoded as needed in order to properly construct the HTTP Request (this may be done automatically by the framework that is used).

Example (using a System.Net.WebClient class):

  var values = new NameValueCollection();
  values.Add("wrap_access_token", token);
  var client = new WebClient();
  client.UploadValues("BartenderWebservice", "POST", values));

Accepting and Validating a Token

SWT tokens are opaque to the Client. That is, since the Client cannot modify the token, they shouldn’t really care what’s in it or how it’s structured. The Protected Resource, however, must deconstruct, validate, and then use the claims that are contained within the tokens. If anything is invalid or malformed, then the Protected Resource should deny access by returning a 401 Unauthorized status in the response.

The Windows Azure platform AppFabric SDK V1.0 contains plenty of boilerplate code in the samples demonstrating how to parse and validate a SWT token (so I won’t be repeating that code here). In essence, all of the following needs to pass validation before the Client is authorized to access the Protected Resource:

HMACSHA256 signature is valid
Token has not yet expired
The Issuer is trusted (i.e., contains the URL of the ACS server)
The Audience is trusted (i.e., contains the URL of the Protected Resource)
Additional required claims are present

For the nightclub example, the Customer’s Birthdate will be presented as a claim (#5 in the list above). So, in addition to checking the technical aspects of the token, a business rule must also ensure that the Customer is of legal age to order a drink from the Bartender (in the United States, this means at least 21 years old).

Conclusion

I wrote this series of blog posts because I myself was having a hard time grasping the Hows and Whys of using Windows Azure platform AppFabric Access Control to secure a Protected Resource. What I discovered was that by using claims based identity in conjunction with a federated identity model, you can incorporate a very scalable authorization scheme into your system without requiring complex code and/or special prerequisite software. Technically, an organization could build this same functionality into a system without using Azure AppFabric. However, Windows AppFabric Access Control offers the benefit of already being internet-facing and hosted in a high availability environment, and already includes a rich implementation of OAuth WRAP that supports many different kinds of Issuers.

Windows Azure platform AppFabric Access Control: Introduction

Jason Follas — Tue, 09 Mar 2010 04:37:43 GMT

The Windows Azure platform AppFabric Access Control service was one aspect of the Windows Azure platform that I found a bit challenging to understand, primarily because identity is not a domain that I regularly work with. This post, the first in a planned series of articles, will explore what the Access Control service is and why it is useful.

Three Geeks Walk Into a Bar…

Let’s examine a common real-world scenario: Ordering a drink from a bartender at a nightclub.

Before the nightclub opens, the bouncers inform the bartenders about the token that customers will bear on that night to indicate that they are of legal age. This could be a stamp on the back of the hand, a colored wristband, etc.

At the door, a customer will present their identification to the bouncer that shows, among other things, their date of birth. This ID could be a state-issued driver's license, a passport, or even a school identification card. The point is that the nightclub didn’t issue that ID, but they recognize the authority that did issue it, and will accept the claim (the birth date) that is displayed on that ID.

If the bouncer determines that the ID is authentic and hasn’t been tampered with, then he will give the customer the token of the night (stamped hand or colored wristband), and the customer is free to enter the bar.

Once inside, the customer only needs to show the token to the bartender in order to buy drinks. They do not need to show their ID.

The next night, the token will change, so a customer cannot use a token obtained the night before.

Federated Access Control

Now let’s look at a similar scenario: Calling a web service from an application. Only, in this case, the web service should not fulfill requests from unauthorized clients. Furthermore, it’s not the web service’s responsibility to authenticate the client; it is simply expecting the client to bear some verifiable proof that it is already authorized to use the service.

Before calling the Web Service, the Service Consumer (application) must first obtain a token that is issued by an Access Control Service (ACS). This is done by sending a number of claims to the ACS, with one of these claims being secrets belonging to an Issuer that the application is associated with.

If the Issuer is recognized and trusted by the ACS, then a token will be created. This token (which is a collection of name/value pairs) will contain claims, an expiration date, and a signature that can be used to ensure that the token was not modified after it was created.

Once the Service Consumer has a valid token, it can then call the Web Service and provide that token in a location where the service expects to find it, such as in a HTTP header. The Web Service validates that the token is well-formed, has not expired, and has not been modified since it was created. If anything fails validation, then the processing aborts. Otherwise, the web service returns data to the Service Consumer, possibly using claims contained in the token as input in the process.

This scenario is considered to be Federated because the ACS doesn’t actually maintain a list of usernames and passwords. Instead, it maintains a list of trusted Issuers with the expectation is that the Issuer is responsible for authenticating its own users.

Correlation

In these examples, the Web Service is analogous to the nightclub’s Bartender: it has something to provide to the Service Consumer (Customer), but the Service Consumer must present an appropriate token that is generated by the Access Control Service (Bouncer).

The web service example above is intentionally vague in the part where a token is obtained. There are a few different ways that an Issuer can be identified in a token request, and while passing the Issuer’s secret in plain text is one of those ways, it certainly shouldn’t be taken lightly. Whoever has the Issuer’s key can spoof any of the claims, and that might prove to be a challenge for the service. In the example where we need a Date of Birth claim to be presented, it would probably be a bad idea to allow the customer themselves to say “I’m from Ohio, here’s a blank driver's license that meets all of the standards of a proper ID, and, oh yeah… I’m writing on here that I am 21 years old.”

Instead, claims should originate from the Issuer in some way that cannot be tampered with by the application (using the assumption that the application itself should not be trusted). With the plain text method, this might require having a separate service that runs within the Issuer’s domain and is aware of its users and also ACS. This service would broker the ACS token request for the application, automatically providing any claim data that might be needed (like the Date of Birth) from the Issuer’s own user database. The application would be provided with the same token, but would never have the Issuer’s secret that is required to obtain the token directly from ACS.

(Continued in Part 2)

You Need that Using Statement for Extension Methods!

Jason Follas — Thu, 25 Feb 2010 19:11:38 GMT

I was working through some Windows Azure example code today, and came across a situation where IntelliSense did not show a method that the sample code used (CreateCloudBlobClient(), in this case):

var storageAccount = Microsoft.WindowsAzure.CloudStorageAccount.FromConfigurationSetting("DataConnectionString");
var blobStorage = storageAccount.CreateCloudBlobClient();

A lot of times, when I'm exploring an API, I will type out the fully qualified class name in code so that I can use IntelliSense to see what the other members exist in the same namespace. And, while I'm exploring, I usually don't bother to include a using statement at the top of my code because it's so easy to just use the "Remove Type Qualifier" refactoring available in CodeRush to clean up the code when I'm ready to move on.

Well, something that I guess I didn't remember soon enough was that using statements are required in order to enable Extension Methods belonging to that namespace. In this case, CreateClousBlobClient() was not a method of CloudStorageAccount, but rather an Extension Method (and this fact is not something that is very apparent when typing in sample code that you find in a document).

IntelliSense showed that method (and more!) after adding the following line of code to the top of my file:

using Microsoft.WindowsAzure.StorageClient;

Microsoft Solver Foundation

Jason Follas — Sat, 04 Apr 2009 11:53:21 GMT

Warning: Only 3 people who read this may actually understand it.

This morning, after actually considering what the effort might be to port lp_solve from C over to .NET, I stumbled upon this:

http://code.msdn.microsoft.com/solverfoundation

About 4-5 years ago, I worked on a project that used a Frankenstein'ed "lp_solve 2.0-ported-to-Java-then-ported-to-C#" solver, which was great because it was free and it was a completely managed solution (no native components). What I was doing wasn't particularly that heavy of a problem, but still required a solver to quickly and reliably minimize a cost given a bunch of user-provided constraints.

Solver Foundation appears to satisfy both of these "requirements" (i.e., being Free and being completely managed).

Now, if I can build a Silverlight 2.0+ app that is able to use MSF, then I essentially get infinite scaleout of my optimizer without requiring infinite server infrastructure.

Enterprise ASP.NET Application Performance Tip

Jason Follas — Mon, 23 Feb 2009 19:15:00 GMT

Microsoft Regional Director (and friend) Steven Smith has a great talk about ASP.NET performance tips - I've seen the presentation probably a handful of times already, and always seem to walk away with something new to try that I didn't quite "grok" previously.

But, here's one additional tip that I can offer that is easily overlooked, yet very important for enterprise development.

Enterprise web applications (at least in my world) tend to use Integrated Security in order to provide Single Sign-On capability (i.e., automatically authenticating the user according to their Active Directory credentials). As such, Anonymous access to the web application is usually disabled directly in the metabase using the IIS MMC. But, with sites that use a lot of small images, there's a serious performance hit that you take when Anonymous access is disabled!

A web browser will always try to submit a request anonymously. In the case that I described where Anonymous access is disabled, the web server will generate a 403 response (and include a list of possible ways that the client can authenticate itself). The web browser will then either prompt the user for credentials, or in the case of using Internet Explorer in the Intranet Zone with an application protected by Integrated Security, will automatically provide a response to the NTLM challenge. The point being that it takes two separate requests for each resource (not to mention a higher computational cost, since there's a challenge/response included). Multiply this by however many little images your page might have, and your load time increases significantly.

Just today, I was asked to diagnose a load-time issue for a 3rd party web application that my client uses. The site looks nice because it uses little images all over the place - to the effect of hundreds per page! But, the price of these aesthetics was really aweful load times, especially over a VPN connection.

For images and other resources that do not necessarily need authentication, you can get an immediate performance improvement by enabling Anonymous access to the resource directories/files themselves (leaving Anonymous access disabled for the rest of the application).

Using SQL Server Spatial Objects as ADO.NET Parameter Values

Jason Follas — Thu, 11 Dec 2008 19:04:12 GMT

I've previously mentioned that the SQL Server 2008 Spatial data types are freely available for use in your .NET applications, regardless of whether you have SQL Server 2008 or not. This allows you to incorporate some powerful spatial capabilities right into your application.

(Look for "Microsoft SQL Server System CLR Types" on this page: http://www.microsoft.com/downloads/details.aspx?FamilyID=228DE03F-3B5A-428A-923F-58A033D316E1&displaylang=en )

However, in most usage scenarios, there will come a time when you have an instance of a SQL Server spatial object in your .NET application, and need to commit it to your SQL Server 2008 database. How would you do this, without losing fidelity or resorting to serialization of the object to WKT first?

The solutions is to create a Parameter object of type System.Data.SqlDbType.Udt. Then set the UdtTypeName parameter to the SQL Server-recognized type name (i.e., for SqlGeometry, you would simply use Geometry).

The following code demonstrates executing an UPDATE statement that sets the value of a Spatial field to a newly constructed object.

using (SqlConnection conn = new SqlConnection("Server=.;Integrated Security=true;Initial Catalog=scratch"))
{
   using (SqlCommand cmd = new SqlCommand("UPDATE fe_2007_us_zcta500 SET Boundary=@boundary WHERE id=@id", conn))
   {
      SqlParameter id = cmd.Parameters.Add("@id", System.Data.SqlDbType.Int);
      SqlParameter boundary = cmd.Parameters.Add("@boundary", System.Data.SqlDbType.Udt);
      boundary.UdtTypeName = "geometry";
      SqlGeometry geom = SqlGeometry.Parse("POLYGON((0 0, 0 1, 1 1, 1 0, 0 0))");
      boundary.Value = geom;
      id.Value = 123;
      conn.Open();
      cmd.ExecuteNonQuery();
      conn.Close();
   }
}

SqlGeography: Ring Orientation of Polygon Interior Rings (Holes)

Jason Follas — Tue, 25 Nov 2008 14:14:18 GMT

I have mentioned before how the Ring Orientation for the exterior ring of a Polygon is significant when instantiating a SqlGeography object. In this case, a Counter-Clockwise orientation is required so that as an observer walks along the path, the interior of the Polygon is always to their left.

But, what I have never really seen documented (or paid attention to, at least) is the fact that the interior rings, or holes, of a Polygon also have specific Ring Orientation requirements.

In keeping with the "Left-handed" rule, interior rings must be defined in a Clockwise manner - the opposite orientation of the shape's exterior ring. This is because holes within a Polygon are considered to be part of the exterior of the shape, so the observer walking in a Clockwise direction is still keeping the Polygon's interior to their left.

(I should note here that the Ring Orientation for SqlGeography is the exact opposite of ESRI's ShapeFile format, which is why Ring Orientation has been on my mind for the past few days).

Spatial: Determining Ring Orientation

Jason Follas — Mon, 24 Nov 2008 18:00:46 GMT

A Ring is a list of points such that the starting point and ending point are the same (forming a closed shape). The order the you define the points that make up a Ring - known as Ring Orientation - is significant, for various data formats (including SQL Server's Geography type) imply special meaning for rings that are defined in a clockwise manner as opposed to a counter-clockwise manner.

Given a list of points with no additional context, it can be difficult to determine the Ring Orientation being used.

For example, suppose that you have a generic list of points that represent the boundary of a postal code, and that you wish to use these points in order to construct a Polygon instance using the SqlGeography type. SqlGeography happens to use "Left-handed" ordering, so that as an observer walks along the set of points in the order defined, the "inside" of the polygon is always to their left. This also implies that the exterior ring of a Polygon is defined in a counter-clockwise manner.

If you try to define a polygon with an area greater than a single hemisphere (this is a nice way to say "if you screw up and use the wrong orientation"), then the SqlGeography type will throw an exception. So, aside from using Try-Catch, what can you do?

While researching solutions to this problem, I stumbled upon a paper entitled "A Winding Number and Point-in-Polygon Algorithm" from the Colorado State University. It turns out that a simple algorithm with O(n) complexity can be used to determine if a point is within a Polygon, and a side effect also provides the Ring Orientation. The key to this algorithm is determining the trend of the ring at each crossing of an axis.

Since I was only interested in Ring Orientation (and not point enclosure detection), I didn't need to use this particular algorithm. Instead, I took inspiration from the winding concept, and created a simpler derivative algorithm:

Iterate the point collection and determine the extreme "left" and "right" points
Normalize the line segments connected to these points so that they each have the same "X" dimension length
Compare the "Y" values of the normalized segments to establish the trend through that extreme point (i.e., is the "previous" segment above or below the "next" segment)
In the spirit of the Winding algorithm, use opposite orientations for the left and right points so that the results coincide with one another
A negative result (negative indicates Clockwise orientation, positive result indicates Counter-Clockwise orientation, and a result of zero would be undefined

I've actually written (and posted) several versions of this algorithm, each time discovering some edge case exception that would cause me to take down the post and rewrite the algorithm. I believe the code below works for all simple polygons on a Cartesian coordinate system (read: I have more testing to see if this will work with an ellipsoidal model, like SqlGeography).

Note: The following code is generic in nature, and as such, I've defined my own Point structure instead of using a SqlGeometry or SqlGeography, etc.

struct Point
{
    public double X { get; set; }
    public double Y { get; set; }
}
enum RingOrientation : int
{
    Unknown = 0,
    Clockwise = -1,
    CounterClockwise = 1
};
RingOrientation Orientation(Point[] points)
{
    // Inspired by http://www.engr.colostate.edu/~dga/dga/papers/point_in_polygon.pdf
    // This algorithm is to simply determine the Ring Orientation, so to do so, find the
    // extreme left and right points, and then check orientation
    if (points.Length < 4)
    {
        throw new ArgumentException("A polygon requires at least 4 points.");
    }
    if (points[0].X != points[points.Length - 1].X || points[0].Y != points[points.Length - 1].Y)
    {
        throw new ArgumentException("The array of points is not a polygon.  The first and last point must be identical.");
    }
    int rightmostIndex = 0;
    int leftmostIndex = 0;
    for (int i = 1; i < points.Length; i++)
    {
        if (points[i].X < points[leftmostIndex].X)
        {
            leftmostIndex = i;
        }
        if (points[i].X > points[rightmostIndex].X)
        {
            rightmostIndex = i;
        }
    }
    Point p0; // Point before the extreme
    Point p1; // The extreme point
    Point p2; // Point after the extreme
    double m; // Holds line slope
    double lenP2x;  // Length of the P1-P2 line segment's delta X
    double newP0y;  // The Y value of the P1-P0 line segment adjusted for X=lenP2x
    RingOrientation left_orientation;
    RingOrientation right_orientation;
    // Determine the orientation at the Left Point
    if (leftmostIndex == 0)
        p0 = points[points.Length - 2];
    else
        p0 = points[leftmostIndex - 1];
    p1 = points[leftmostIndex];
    if (leftmostIndex == points.Length - 1)
        p2 = points[1];
    else
        p2 = points[leftmostIndex + 1];
    m = (p1.Y - p0.Y) / (p1.X - p0.X);
    if (double.IsInfinity(m))
    {
        // This is a vertical line segment, so just calculate the dY to
        // determine orientation
        left_orientation = (RingOrientation)Math.Sign(p0.Y - p1.Y);
    }
    else
    {
        lenP2x = p2.X - p1.X;
        newP0y = p1.Y + (m * lenP2x);
        left_orientation = (RingOrientation)Math.Sign(newP0y - p2.Y);
    }
    // Determine the orientation at the Right Point
    if (rightmostIndex == 0)
        p0 = points[points.Length - 2];
    else
        p0 = points[rightmostIndex - 1];
    p1 = points[rightmostIndex];
    if (rightmostIndex == points.Length - 1)
        p2 = points[1];
    else
        p2 = points[rightmostIndex + 1];
    m = (p1.Y - p0.Y) / (p1.X - p0.X);
    if (double.IsInfinity(m))
    {
        // This is a vertical line segment, so just calculate the dY to
        // determine orientation
        right_orientation = (RingOrientation)Math.Sign(p1.Y - p0.Y);
    }
    else
    {
        lenP2x = p2.X - p1.X;
        newP0y = p1.Y + (m * lenP2x);
        right_orientation = (RingOrientation)Math.Sign(p2.Y - newP0y);
    }
    if (left_orientation == RingOrientation.Unknown)
    {
        return right_orientation;
    }
    else
    {
        return left_orientation;
    }
}
void Test()
{
    // Simple triangle - left extreme point is vertically "in between" line segments
    Point[] points = new Point[]
    {
        new Point(5,-1),
        new Point(0,0),
        new Point(5,1),
        new Point(5,-1)
    };
    System.Diagnostics.Debug.Assert(Orientation(points) == RingOrientation.Clockwise);
    Array.Reverse(points);
    System.Diagnostics.Debug.Assert(Orientation(points) == RingOrientation.CounterClockwise);
    // Case where both line segments are above the left extreme point
    points = new Point[]
    {
        new Point(2,1),
        new Point(0,0),
        new Point(1,1),
        new Point(2,1)
    };
    System.Diagnostics.Debug.Assert(Orientation(points) == RingOrientation.Clockwise);
    Array.Reverse(points);
    System.Diagnostics.Debug.Assert(Orientation(points) == RingOrientation.CounterClockwise);
    // Case where both line segments are below the left extreme point
    points = new Point[]
    {
        new Point(2,-1),
        new Point(0,0),
        new Point(1,-1),
        new Point(2,-1)
    };
    System.Diagnostics.Debug.Assert(Orientation(points) == RingOrientation.CounterClockwise);
    Array.Reverse(points);
    System.Diagnostics.Debug.Assert(Orientation(points) == RingOrientation.Clockwise);
    // Case where line segment is vertical (slope cannot be determined)
    points = new Point[]
    {
        new Point(0,0),
        new Point(0,1),
        new Point(1,1),
        new Point(1,0),
        new Point(0,0)
    };
    System.Diagnostics.Debug.Assert(Orientation(points) == RingOrientation.Clockwise);
    Array.Reverse(points);
    System.Diagnostics.Debug.Assert(Orientation(points) == RingOrientation.CounterClockwise);
    // Case where angle thru left extreme point is a right angle
    points = new Point[]
    {
        new Point(0,0),
        new Point(1,1),
        new Point(1,-1),
        new Point(0,0)
    };
    System.Diagnostics.Debug.Assert(Orientation(points) == RingOrientation.Clockwise);
    Array.Reverse(points);
    System.Diagnostics.Debug.Assert(Orientation(points) == RingOrientation.CounterClockwise);
    // Real-world case from a SHP file
    points = new Point[]
    {
        new Point(-156.92467299999998,20.738695999999997),
        new Point(-156.924636,20.738822),
        new Point(-156.924608,20.73894),
        new Point(-156.92458,20.739082),
        new Point(-156.92460599999998,20.739234),
        new Point(-156.924551,20.739326),
        new Point(-156.924507,20.739241999999997),
        new Point(-156.924482,20.739082),
        new Point(-156.924466,20.738854999999997),
        new Point(-156.924387,20.738602999999998),
        new Point(-156.924308,20.738325),
        new Point(-156.924239,20.738063999999998),
        new Point(-156.92424,20.737887999999998),
        new Point(-156.924285,20.737811999999998),
        new Point(-156.924475,20.73762),
        new Point(-156.92458299999998,20.737603999999997),
        new Point(-156.924754,20.737579),
        new Point(-156.924851,20.737731),
        new Point(-156.924956,20.738101),
        new Point(-156.924909,20.738343999999998),
        new Point(-156.924818,20.738487),
        new Point(-156.92467299999998,20.738695999999997)
    };
    System.Diagnostics.Debug.Assert(Orientation(points) == RingOrientation.Clockwise);
    Array.Reverse(points);
    System.Diagnostics.Debug.Assert(Orientation(points) == RingOrientation.CounterClockwise);
}

Upcoming Events

Jason Follas — Thu, 25 Sep 2008 16:50:25 GMT

There are a few events taking place in October that I would like to promote:

Day of .NET in Ann Arbor
Saturday, October 18, 2008

The fourth Day of .NET in Ann Arbor event will take place on the campus of Washenaw Community College in Ann Arbor (or is it actually Ypsilanti? I can never tell). The original conference was a collaboration between GANG, AADND, and NWNUG. This year, we have officially added GLUG.net and West Michigan to the list of groups who are assisting in the organization and promotion. So, for those of you following along at home, this event is the product of FIVE regional user groups, and like its predecessors, should be a great day of learning and networking.

The session list has been posted, and there should be something on the schedule for everyone. Registration is free, and all that we ask is that if you do sign up, then please show up. There's nothing worse than wasting sponsorship dollars by ordering too much food or too many T-Shirts (though, this year, we're going to try to get Pizza back on the menu, so food waste should hopefully be minimized).

http://www.dayofdotnet.org/AnnArbor/Fall2008/Sessions.aspx

Wally McClure appearing at Northwest Ohio .NET User Group
Monday, October 20, 2008

"Hello. I'm Wally McClure. You might remember me from my many books published by Wrox Press with my picture on them. Or, the ASP.NET Podcast, where on the website, you'll find pictures of my books with my pictures on them. Or, the very popular T-Shirt with my picture on the back...."

I met Wally this summer at TechEd Developer in Orlando, where one of the first experiences was being crammed into the back seat of a car between him and Keith Elder. He seemed to take a liking to me, and let's just say that my phone now receives more random text messages than ever before. :-)

In all seriousness, Wally was supposed to have appeared at NWNUG in June, just after TechEd, but had to back out due to work commitments (Steve Smith ended up filling in for him). We're thrilled that he was still interested in coming to Toledo, and we were able to arrange an October 20th date (note that this is a Monday, not the regular Tuesday meeting night).

Watch the NWNUG website for further details about the meeting topic.