I was setting up a Ext JS grid and the rendering was wrong :
It was a CSS conflict between default ASP.NET CSS and Ext JS CSS. After commenting out all table related styles from Site.css the grid pager is displaying correctly:
I needed to update a SharePoint list item directly on client side in a classic SharePoint list form. I found this blog who explains very well how to do it by using Prototype but I was already using jQuery and didn’t want to add another javascript framework to my solution. Sure this is very easily portable to jQuery but I wanted a cleaner solution.
I found this: jQuery SOAP Client, a jQuery plug-in (it’s really an add-on because it doesn’t use jQuery extension mechanism) who was looking very promising. So I started to code…
I was going to call the UpdateListItems of the list web service (http://server/_vti_bin/lists.asmx). This method requires two arguments: listName and updates. Updates are the CAML commands describing the changes to the list and looks like this:
<Batch OnError="Continue">
<Method ID="1" Cmd="Update">
<Field Name="ID">1</Field>
<Field Name="Title">updated title</Field>
</Method>
</Batch>
I think that’s pretty readable: we want to change the Title of the element with the ID=1 to “updated title”.
Next: the javascript code using jQuery SOAP Client:
var wsMethod = "UpdateListItems";
var soapNs = "http://schemas.microsoft.com/sharepoint/soap/";
var soapBody = new SOAPObject(wsMethod);
soapBody.ns = soapNs;
soapBody.appendChild(new SOAPObject("listName")).val("list1");
soapBody.appendChild(new SOAPObject("updates")).val(batch);
var sr = new SOAPRequest(soapNs + wsMethod, soapBody);
SOAPClient.Proxy = "http://server/_vti_bin/lists.asmx";
SOAPClient.SendRequest(sr, processResponse);
For this to work it needs to be executed from an already authenticated SharePoint web page. Internet Explorer automatically passes the credentials with the XHR call. You could pass the credentials in the jQuery call but I wouldn’t do that if I where you.
Well, this didn’t work… I was getting some generic SharePoint error page, not very useful for debugging so I fired up Fiddler2.
I found out that the response was a HTTP error code 415 - Unsupported Media Type. I noticed some differences between the SOAP request created by jQuery SOAP Client and the SOAP code expected by the service and modified the plug-in accordingly. But I was still getting the same error.
And then I saw it: the Content-Type sent was application/x-www-form-urlencoded, text/xml; charset= "utf-8"; Thing is when you make an AJAX call with jQuery it automatically ads application/x-www-form-urlencoded content-type if no content-type is specified. But jQuery SOAP Client added the content-type not by using jQuery but directly into the XmlHttpRequest object:
$.ajax({
type: "POST",
url: SOAPClient.Proxy,
dataType: "xml",
processData: false,
data: content,
complete: getResponse,
beforeSend: function(req) {
req.setRequestHeader("Method", "POST");
req.setRequestHeader("Content-Length", SOAPClient.ContentLength);
req.setRequestHeader("Content-Type", SOAPClient.ContentType + "; charset=\"" + SOAPClient.CharSet + "\"");
req.setRequestHeader("SOAPServer", SOAPClient.SOAPServer);
req.setRequestHeader("SOAPAction", soapReq.Action);
}
});
Fixing that was simple and… it worked!!!
$.ajax({
type: "POST",
url: SOAPClient.Proxy,
dataType: "xml",
processData: false,
data: content,
contentType : SOAPClient.ContentType + "; charset=\"" + SOAPClient.CharSet + "\"",
complete: getResponse,
beforeSend: function(req) {
req.setRequestHeader("Method", "POST");
req.setRequestHeader("Content-Length", SOAPClient.ContentLength);
req.setRequestHeader("SOAPServer", SOAPClient.SOAPServer);
req.setRequestHeader("SOAPAction", soapReq.Action);
}
});
You can download the source code here
This blog publishes each week a programming challenge they think would appropriate for a programming job interview. In my opinion most of them aren’t very well suited for a job interview but this isn’t the subject of my post. The aim of my post is to solve this week challenge.
This week question is:
Your input:
- List of points in a 2D space. If you draw lines between one point to the next one, a closed polygon is created (can be either concave or convex).
- A single point in a 2D space.
You need to determine whether the given point is inside or outside the given polygon.
[...]
Provide the most efficient and simple algorithm.
The simplest algorithm I have in mind would be:
Problem solved is a few lines of code :D. But what happens if coordinates aren’t integers or are really big (> 10000) ? This algorithm is not very accurate, we’d run out of memory and filling up a big polygon would take lots of time.
Lets draw a ray starting at our point in a random direction to the infinity. This ray intersects our polygon zero or more times.
Zero times would mean the point is outside the polygon. One time means the point is inside, two times outside and so on… Even number of intersections means the point is outside, odd number means the point is inside. How do I prove that ?
I don’t have a mathematical proof, rather an intuitive one… Lets choose an imaginary point on the ray at infinity. Could this point be inside the polygon ? No, it can’t: because the polygon is closed and finite a point at infinity can’t be inside it. Lets walk backwards from the point to infinity to our reference point. Each time the ray intersects the polygon we switch from inside to outside and vice versa. Even number of switches (intersections) -> the point is outside; odd number of switches -> the point is inside. The algorithm is pretty simple and is O(n) complexity:
How can we implement that ?! The mathematical representation of a ray is:
Ray(t) = Po + t*Pd with t>=0
Where Po is the origin point and Pd is a point somewhere on the ray witch gives the ray direction.
The mathematical representation of a segment is:
Segment(u) = P1 + u * (P2-P1) with 0<=u<=1
Where P1 and P2 are the head points of the segment. If we replace (P2-P1) by D (as in Delta) we get the same formula as the ray. Only the limits for the argument are different.
To find out if the ray intersects the segment we have to solve the equation
Ray(t) = Segment(u)
and check if t>=0 and 0<=u<=1. But I won’t steal you the pleasure of solving it 
First let me warn you that for the sake of simplicity I eliminated input validation code: polygon should have at least three points, segment and ray validation (origin and direction points should be different).
The language used is C# 3.0.
Lets start with some simple geometric classes:
public class Point
{
public Point(float x, float y)
{
X = x;
Y = y;
}
public float X { get; private set; }
public float Y { get; private set; }
}
public class Ray
{
public Ray(Point p1, Point p2)
{
Origin = p1;
Direction = p2;
}
public Point Origin { get; private set; }
public Point Direction { get; private set; }
}
public class Segment
{
public Segment(Point p1, Point p2)
{
Origin = p1;
Delta = new Point(p2.X - p1.X, p2.Y - p1.Y);
}
public Point Origin { get; private set; }
public Point Delta { get; private set; }
}
Now the method witch finds out if a ray and an segment intersect:
/// <summary>
/// Solves the equation Ray(t) = Segment(u) where
/// Ray(t) = Po + t*Pd with t>=0
/// Segment(u) = P1 + u * (P2-P1) with 0<=u<=1
/// </summary>
/// <param name="ray">the ray</param>
/// <param name="seg">the segment</param>
/// <returns>true if ray and segment intersect</returns>
private static bool Intersecting(Ray ray, Segment seg)
{
var a =
seg.Delta.X * ray.Direction.Y -
seg.Delta.Y * ray.Direction.X;
// if ray and segment are parallel they don't intersect
if (0 == a) return false;
var b =
(ray.Origin.X - seg.Origin.X) * ray.Direction.Y -
(ray.Origin.Y - seg.Origin.Y) * ray.Direction.X;
var u = b / a;
b =
(ray.Origin.X - seg.Origin.X) * seg.Delta.Y -
(ray.Origin.Y - seg.Origin.Y) * seg.Delta.X;
var t = b / a;
return 0 <= t && 0 <= u && 1 > u;
}
}
Did you notice that something changed ? The constraints on u changed from 0<=u<=1 to 0<=u<1. What happens if the ray contains one of the polygon points ? The intersection would be counted twice ! Hence the change.
To define the polygon the input is a list of points but our algorithm needs segments so we transform the input:
/// <summary>
/// Transforms a list of polygon points in a list of polygon segments
/// </summary>
/// <param name="polyPoints">list of polygon points</param>
/// <returns>list of polygon segments</returns>
private static IList<Segment> GetPolySegments(IList<Point> polyPoints)
{
IList<Segment> segments = new List<Segment>();
for (var i = 0; i < polyPoints.Count - 1; i++)
{
segments.Add(new Segment(polyPoints[i], polyPoints[i + 1]));
}
segments.Add(new Segment(polyPoints[polyPoints.Count - 1], polyPoints[0]));
return segments;
}
To define the ray we need an origin point (the input point) and a direction point. For fun I choosed the direction point to be the center of the polygon.
/// <summary>
/// Calculates the center of a polygon. (the averege of coordinates)
/// </summary>
/// <param name="polyPoints">collection of polygon</param>
/// <returns>Center Point</returns>
private static Point GetPolyCenter(ICollection<Point> polyPoints)
{
return new Point(
polyPoints.Sum(p => p.X) / polyPoints.Count,
polyPoints.Sum(p => p.Y) / polyPoints.Count);
}
Any random direction point would work as long as it is different form the input point.
And now the main algorithm:
/// <summary>
/// Finds if a point is inside a closed polygon
/// </summary>
/// <param name="p">point</param>
/// <param name="polyPoints">list of points definig the polygon</param>
/// <returns>true if point p is inside the polygon</returns>
public static bool IsPointInsidePoly(Point p, IList<Point> polyPoints)
{
// define ray
var rayToPolyCenter = new Ray(p, GetPolyCenter(polyPoints));
// count intersections
var intersections = GetPolySegments(polyPoints).Count(
s => Intersecting(rayToPolyCenter, s));
// Odd number of intersections means inside
return 1 == intersections % 2;
}
So that’s it. There are some ways of improving the code (input validation, test it with very close points, etc.) but I’ll stop here.