In one of my next postings I will show a algorithm, that calculates line segment intersections. As a prerequisite we need an algorithm, which calculates the intersection of two lines. In this post I will consider the following intersection of two lines in the euclidean plan:
We can write this as an equation system with two variables and two equations:
Ax + r (Bx – Ax) = Cx + s (Dx – Cx)
Ay + r (By – Ay) = Cy + s (Dy – Cy)
After solving this system we can calculate the intersection:
Px = Ax + r (Bx – Ax)
Py = Ay + r (By – Ay)
Putting this all together we can derive the following F#-code:
let calcIntersection (A:Location, B:Location, C:Location, D:Location) =
let (Ax,Ay,Bx,By,Cx,Cy,Dx,Dy) =
(A.XPos, A.YPos, B.XPos, B.YPos, C.XPos, C.YPos, D.XPos, D.YPos)
let d = (Bx-Ax)*(Dy-Cy)-(By-Ay)*(Dx-Cx)
if d = 0 then
// parallel lines ==> no intersection in euclidean plane
None
else let q = (Ay-Cy)*(Dx-Cx)-(Ax-Cx)*(Dy-Cy)
let r = q / d
let p = (Ay-Cy)*(Bx-Ax)-(Ax-Cx)*(By-Ay)
let s = p / d
if r < 0. or r > 1. or s < 0. or s > 1. then
None // intersection is not within the line segments
else
Some(
(Ax+r*(Bx-Ax)), // Px
(Ay+r*(By-Ay))) // Py
Remarks:
If one given line degenerates into a point, then the algorithm gives no intersection.
If the given lines are parallel, then the algorithm gives no intersection, even if the lines have an overlap.
Last time I showed how the immutable set implementation in F# can be used to get a immutable sorted list. As a result of using sets, the shown version doesn’t support repeated items. This lack can be wiped out by using an additional dictionary (immutable "Map" in F#) which stores the count of each item.
At first I define two basic helper functions for the dictionary:
module MapHelper =
let addToMap map idx =
let value = Map.tryfind idx map
match value with
| Some(x) -> Map.add idx (x+1) map
| None -> Map.add idx 1 map
let removeFromMap map idx =
let value = Map.tryfind idx map
match value with
| Some(x) ->
if x > 1 then
Map.add idx (x-1) map
else
Map.remove idx map
| None -> map
open MapHelper
Now I can adjust my sorted list implementation:
// a immutable sorted list - based on F# set
type 'a SortedFList =
{items: Tagged.Set<'a,Collections.Generic.IComparer<'a>>;
numbers: Map<'a,int>;
count: int}
member x.Min = x.items.MinimumElement
member x.Items =
seq {
for item in x.items do
for number in [1..x.GetCount item] do
yield item}member x.Length = x.count
member x.IsEmpty = x.items.IsEmpty
member x.GetCount item =
match Map.tryfind item x.numbers with
| None -> 0
| Some(y) -> y
static member FromList(list, sortFunction) =
let comparer = FComparer<'a>.Create(sortFunction)
let m = list |> List.fold_left addToMap Map.empty
{new 'a SortedFList with
items = Tagged.Set<'a>.Create(comparer,list) and
numbers = m and
count = list.Length}
static member FromListWithDefaultComparer(list) =
SortedFList<'a>.FromList(list,compare)
static member Empty(sortFunction) =
SortedFList<'a>.FromList([],sortFunction)
static member EmptyWithDefaultComparer() =
SortedFList<'a>.Empty(compare)
member x.Add(y) =
{x with
items = x.items.Add(y);
numbers = addToMap x.numbers y;
count = x.count + 1}
member x.Remove(y) =
if x.GetCount y > 0 then
{x with
items = x.items.Remove(y);
numbers = removeFromMap x.numbers y;
count = x.count - 1}
else
x
F# supports a powerful implementation of immutable lists (see Dustin’s introduction). But for my current work I needed a sorted list and of course I wanted it the F#-way, which means immutable. I didn’t want to reinvent the wheel so I asked my question in the hubFS forum.
It turned out (thanks to Robert) that F# uses red-black trees to give a fast implementation for the immutable set. This means that a set in F# stores all elements in a balanced binary tree and searching for an element costs only O(log n). As a side effect all elements can be visited in the underlying order, which means the set implementation gives a possibility for implementing a sorted list. The only limitation is that a set usually don’t store objects more than once.
The next problem I got, was that my sorted list needs a specific ordering function. The standard F# set implementation uses structural comparison to give an order, which is not the order I need. But Laurent mentioned the Set.Make function in the F# PowerPack. This function creates a new set type for the given ordering function. The only problem with Set.Make is that it was only designed for OCaml compatibility. But with this hint I was able to put all information together and got a nice immutable sorted list implementation for F#:
// wrap orderingFunction as Collections.Generic.IComparer
type 'a FComparer =
{compareF: 'a -> 'a -> int}
static member Create(compareF) =
{new 'a FComparer with compareF = compareF}
interface Collections.Generic.IComparer<'a> with
member x.Compare(a, b) = x.compareF a b
// a immutable sorted list - based on F# set
type 'a SortedFList =
{items: Tagged.Set<'a,Collections.Generic.IComparer<'a>> }
member x.Min = x.items.MinimumElement
member x.Items = seq {for item in x.items do yield item}
member x.Length = x.items.Count
member x.IsEmpty = x.items.IsEmpty
static member FromList(list, sortFunction) =
let comparer = FComparer<'a>.Create(sortFunction)
{new 'a SortedFList with
items = Tagged.Set<'a>.Create(comparer,list)}
static member FromListWithDefaultComparer(list) =
SortedFList<'a>.FromList(list,compare)
static member Empty(sortFunction) =
SortedFList<'a>.FromList([],sortFunction)
static member EmptyWithDefaultComparer() =
SortedFList<'a>.Empty(compare)
member x.Add(y) =
{x with items = x.items.Add(y)}
member x.Remove(y) =
{x with items = x.items.Remove(y)}
Please note that this implementation stores every item only once. Next time I will show a version which allows to store repeated items.
Last time I showed how it is possible to use parallel map and fold functions to compute the sum of all factorials between 1 and 3000. The result was a nearly perfect load balancing for this task on a two processor machine. This time I will derive a generic function that computes partial results in parallel and folds them to a final result.
Let’s consider our F# example:
let add a b = a + b
letfac (x:bigint) =
[1I..x] |> List.fold_left (*) 1I
let sequential() =
[1I..3000I]
|> List.map fac
|> List.fold_left add 0I
This is the same as:
let calcFactorialSum min max =
[min..max]
|> List.map fac
|> List.fold_left add 0I
let f1() = calcFactorialSum 1I 2000I
let f2() = calcFactorialSum 2001I 2200I
let f3() = calcFactorialSum 2201I 2400I
let f4() = calcFactorialSum 2401I 2600I
let f5() = calcFactorialSum 2601I 2800I
let f6() = calcFactorialSum 2801I 3000I
let sequential2() =
f1() + f2() + f3() + f4() + f5() + f6()
We spitted the summation into 6 independent tasks and computed the sum of the partial results. This has nearly no bearing on the runtime.
But with the help of PLINQ we can compute each task in parallel:
let asParallel (list: 'a list) =
list.AsParallel<'a>()
let runParallel functions =
ParallelEnumerable.Select(
asParallel functions, (fun f -> f() ) )
let pFold foldF seed (data:IParallelEnumerable<'a>)=
ParallelEnumerable.Aggregate<'a,'b>(
data, seed, new Func<'b,'a,'b>(foldF))
let calcFactorialsParallel() =
[f1; f2; f3; f4; f5; f6]
|> runParallel
|> pFold add 0I
This time we build a list of functions (f1, f2, f3, f4, f5, f6) and run them in parallel. "runParallel” gives us back a list of the partial results, which we can fold with the function “add” to get the final result.
On my Core 2 Duo E6550 with 2.33 GHz and 3.5 GB RAM I get the following results:
Time Normal: 26.576s
Time Sequential2: 26.205s (Ratio: 0.99)
Time “Parallel Functions”: 18.426s (Ratio: 0.69)
We can see that the parallel computation of the functions f1 – f6 is much faster than the sequential.
But why is the PLINQ-version (see last post) still faster? We can easily see that each partial function needs a different runtime (e.g. it’s much harder to calculate the factorials between 2800 and 3000 than between 2000 and 2200). On my machine I get:
Time F1: 8.738s
Time F2: 2.663s
Time F3: 3.119s
Time F4: 3.492s
Time F5: 3.889s
Time F6: 4.442s
The problem is that the Parallel Framework can only guess each runtime amount in advance. So the load balancing for 2 processors will not be optimal in every case. In the original PLINQ-version there are only small tasks, and the difference between each runtime is smaller. So it is easier to compute the load balancing.
But of course we can do better if we split f1 into two functions f7 and f8:
let f7() = calcFactorialSum 1I 1500I
let f8() = calcFactorialSum 1501I 2000I
So we can get a better load balancing:
Time F1: 8.721s
Time F7: 4.753s
Time F8: 4.829s
Time Normal: 26.137s
Time “Parallel Functions”: 16.138s (Ratio: 0.62)
I have just released my newest version of Counterize II (2.05). I did a lot of refactoring and cleaned up a lot of things. Here is the ChangeLog:
All TableNames replaced with function calls
LocalizationFramework used (Translation in German)
DayOfWeek-Bug fixed
Display only external referers (Thanks to eric)
Extremly speed up sql queries
All stats moved back to Manage-Page (only for admins visible)
Colors in all stats
Separate statistics page for blog entries
Microsoft URL Control-bot excluded
Performance
The biggest changes concern the analysis sql-statements. As I told before, IÂ have completely rewritten the analysis queries and therefore made some dramatic perfomance gains: I have 100.000+ log entries in my blog database. In version 2.04 it take 25 seconds to compute the complete statistics – in version 2.05 I need only 3 sec.
External stats page
Version 2.05 supports external statistic pages – view my stats page to see this in action. If you want to give your visitors such an overview just write <!-- counterize_stats --> into one of your blog posts or pages.
Localization
Counterize II Version 2.05 is the first Counterize version which uses the WordPress Localization Framework. I translated the plugin into german. If you are interested in translating Counterize II into other languages just write a comment. Don’t be shy: It is very easy and I will provide technical assistance.
The next version of Counterize II (2.05) will be released during the next week. For now I am searching some Beta-Testers and translators for several languages (incl. German).
I have made a lot of small Bugfixes (like the famous DayOfWeek-Bugfix) and started to use the WordPress-LocalizationFramework.
The biggest changes concern the analysis sql-statements. I have completly rewritten the whole stuff and made some dramatic perfomance gains: I have 100.000 log entries in my blog database. In version 2.04 it take 25 seconds to compute the complete statistics – in version 2.05 I need only 3 sec.
Version 2.05 supports external statistic pages – view my stats page.
If you want to test the new version 2.05 just write a comment and I will send you an email.
My new WordPress-Plugin “WP-ReferencesMap” will be released within the next weeks – but i’m searching some beta testers. WP-ReferencesMap allows you to geocode references and show them on a GoogleMaps-Control. Warning: Creating default object from empty value in /www/htdocs/w007928a/blog/wp-content/plugins/wp-referencesmap/GoogleMapsWrapper.php on line 55
Warning: Creating default object from empty value in /www/htdocs/w007928a/blog/wp-content/plugins/wp-referencesmap/GoogleMapsWrapper.php on line 55
Today I want to describe a way to integrate Oracle into Navision. We use this way to migrate selected Tables and Views (rawdata) completely automatic into Dynamics Nav. This means we generate the Table-Structure (as a copy of the Oracle data dictionary) and import the data on the fly.
“This form lists the granules and their associated objects for MBS-Navision 3.60, 3.70 & 4.00. Now you can determine which Granules you need to buy in order to gain access to a certain Object or feature.”
