Translator: Ziming
Author: labuladong
Many readers in the previous article expressed interest in the Union-Find algorithm, so in this article, I will take a few LeetCode problems to talk about the ingenious use of this algorithm.
First, let’s recall that the Union-Find algorithm solves the problem of dynamic connectivity of the graph, but the algorithm itself is not difficult. Your ability which is to abstract the original problem into a question about graph theory to abstract the problem determines whether you can solve it.
First let us review the algorithm code written in the previous article and answer a few questions:
class UF {
// Record the number of connected components
private int count;
// Store several trees
private int[] parent;
// Record the "weight" of the tree
private int[] size;
public UF(int n) {
this.count = n;
parent = new int[n];
size = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
size[i] = 1;
}
}
/* Connect p and q */
public void union(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ)
return;
// The small tree is more balanced under the big tree
if (size[rootP] > size[rootQ]) {
parent[rootQ] = rootP;
size[rootP] += size[rootQ];
} else {
parent[rootP] = rootQ;
size[rootQ] += size[rootP];
}
count--;
}
/* Determine whether p and q are connected to each other */
public boolean connected(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
// Nodes on the same tree are interconnected
return rootP == rootQ;
}
/* Returns the root node of node x */
private int find(int x) {
while (parent[x] != x) {
// Path compression
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
public int count() {
return count;
}
}
The algorithm has three key points:
Use the parent
array to record the parent node of each node, which is equivalent to a pointer to the parent node, so theparent
array actually stores a forest (several multi-trees).
Use the size
array to record the weight of each tree. The purpose is to keep theunion
tree still balanced without degrading it into a linked list, which affects the operation efficiency.
Path compression is performed in the find
function to ensure that the height of any tree is kept constant, so that the time complexity of theunion
and connected
API is O (1).
Some readers may ask, Since the path compression, does the weight balance of the size
array still need? This problem is very interesting, because path compression guarantees that the tree height is constant (not more than 3), even if the tree is unbalanced, the height is also constant, which basically has little effect.
In my opinion, when it comes to time complexity, indeed, it is also O (1) without the need for weight balance. However, if the size array is added, the efficiency is still slightly higher, such as the following:
If weight balance optimization is carried out, case 1 will surely be obtained, without weight optimization, case 2 may occur. The while
loop of path compression is triggered only when the height is 3, so case 1 will not trigger path compression at all, while case 2 will perform path compression many times to compress the nodes in the third layer to the second layer.
In other words, removing the weight balance, although the time complexity is still O (1) for a single find
function call, the efficiency of the API call will decrease to some extent. Of course, the advantage is that it reduces some space, but for Big O notation, the space-time complexity has not changed.
Let’s get down to business and see what practical applications this algorithm has.
Many problems solved by the DFS depth-first algorithm can also be solved by the Union-Find algorithm.
For instance, Surrounded Regions of question 130: Given a 2D board containing X
and O
(the letter O), capture all regions surrounded by X
.
void solve(char[][] board);
Note that O
must be surrounded by four sides in order to be replaced with X
, that is, O
on the corner must not be enclosed, and further, O
connected to O
on the corner Will not be surrounded by X
and will not be replaced.
PS: This reminds me of the chess game “Othello” when I was a kid. As long as you use two pieces to sandwich each other’s pieces, the opponent’s pieces will be replaced with yours. Similarly, the pieces occupying the four corners are invincible, and the side pieces connected to it are also invincible (cannot be clipped).
The traditional method of solving this problem is not difficult. First use the for loop to traverse the four sides of the chessboard, and use the DFS algorithm to replace those O
connected to the border with a special character, such as #
; Second, traverse the entire chessboard, replace the remaining O
Into X
and restore #
to O
. This can complete the requirements of the problem, time complexity O (MN).
This problem can also be solved with the Union-Find algorithm. Although the implementation is more complicated and even less efficient, this is a general idea using the Union-Find algorithm and it is worth learning.
Those O
which do not need to be replaced have a common ancestor calleddummy
. These O
anddummy
are connected to each other,however, those O
that need to be replaced are not connected todummy
.
This is the core idea of Union-Find and it is easy to understand the code if you understand this diagram.
Firstly, according to our implementation, the bottom layer of Union-Find is a one-dimensional array. The constructor needs to pass in the size of the array, and the title is a two-dimensional chessboard.
Which is simple, that the two-dimensional coordinates (x, y)
can be converted to the number x * n + y
This is a common technique for mapping two-dimensional coordinates to one dimension.
Secondly, the “patriarch” we described earlier is fictitious and we need to leave a place for his elderly. The index [0 .. m * n-1]
is a one-dimensional mapping of the coordinates in the chessboard, so let this dummy dummy
node occupy the indexm * n
.
void solve(char[][] board) {
if (board.length == 0) return;
int m = board.length;
int n = board[0].length;
// Leave an extra room for dummy
UF uf = new UF(m * n + 1);
int dummy = m * n;
// Connect the first and last columns of O and dummy
for (int i = 0; i < m; i++) {
if (board[i][0] == 'O')
uf.union(i * n, dummy);
if (board[i][n - 1] == 'O')
uf.union(i * n + n - 1, dummy);
}
// Connect O and dummy in the first and last rows
for (int j = 0; j < n; j++) {
if (board[0][j] == 'O')
uf.union(j, dummy);
if (board[m - 1][j] == 'O')
uf.union(n * (m - 1) + j, dummy);
}
// Direction array d is a common method for searching up, down, left and right
int[][] d = new int[][]{{1,0}, {0,1}, {0,-1}, {-1,0}};
for (int i = 1; i < m - 1; i++)
for (int j = 1; j < n - 1; j++)
if (board[i][j] == 'O')
// Connect this O with up, down, left and right O
for (int k = 0; k < 4; k++) {
int x = i + d[k][0];
int y = j + d[k][1];
if (board[x][y] == 'O')
uf.union(x * n + y, i * n + j);
}
// All O not connected to dummy shall be replaced
for (int i = 1; i < m - 1; i++)
for (int j = 1; j < n - 1; j++)
if (!uf.connected(dummy, i * n + j))
board[i][j] = 'X';
}
This code is very long. In fact, it is just the realization of the previous idea. Only the O
connected to the boundary O
have the connectivity with dummy
and they will not be replaced.
To be honest, the Union-Find algorithm solves this simple problem. It can be a bit of a killer. It can solve more complex and more technical problems. The main idea is to add virtual nodes in a timely manner. Dynamic connectivity.
This problem can be solved using the Union-Find algorithm, that is:
Given an array equations of strings that represent relationships between variables, each string equations[i]
has length 4
and takes one of two different forms: "a==b"
or "a!=b"
. Here, a
and b
are lowercase letters (not necessarily different) that represent one-letter variable names.
Return true if and only if it is possible to assign integers to variable names so as to satisfy all the given equations.
The core idea of solving the problem is that divide the expressions in equations
into two parts according to ==
and !=
, First process the expressions of ==
, so that they are connected. !=
Expression to check if the inequality relationship breaks the connectivity of the equality relationship.
boolean equationsPossible(String[] equations) {
// 26 letters
UF uf = new UF(26);
// Let equal letters form connected components first
for (String eq : equations) {
if (eq.charAt(1) == '=') {
char x = eq.charAt(0);
char y = eq.charAt(3);
uf.union(x - 'a', y - 'a');
}
}
// Check if inequality relationship breaks connectivity of equal relationship
for (String eq : equations) {
if (eq.charAt(1) == '!') {
char x = eq.charAt(0);
char y = eq.charAt(3);
// If the equality relationship holds, it is a logical conflict
if (uf.connected(x - 'a', y - 'a'))
return false;
}
}
return true;
}
At this point, the problem of judging the validity of the expression is solved. Is it easy to use the Union-Find algorithm?
The Union-Find algorithm is a dynamic connectivity problem, that is, how to transform the original problem into a graph. For the legitimacy of the formula, the equivalent relationship can be directly used, and for the checkerboard envelopment problem, a virtual node is used to create the dynamic connectivity.
In addition, you can use the directional array d
to map a two-dimensional array to a one-dimensional array to simplify the amount of code.
Many more complex DFS algorithm problems can be solved using the Union-Find algorithm. There are more than 20 Union-Find related questions on LeetCode, and you can go and try!


We’re launching our brand new website for friends and alumni of The Brown Daily Herald, Since 1891(www.heraldalumni.org). At Since 1891, anyone can learn more about Herald projects, and Herald alums can access a private network, post on communal message boards, and register for an alumni e-newsletter and Herald updates. Since 1891 is designed to provide you with networking opportunities and ways to get involved with The Herald again. For example, several alums are mentoring Herald staffers. Some have made generous donations to our new digitization and financial aid initiatives. We are also planning an exciting Herald reunion event for this year's Commencement Weekend. We have ambitious goals planned for The Herald in which we hope all alumni will play a vital role. To that end, one of our major goals is to establish a working alumni network — because once you've worked for The Herald, you're always a part of The Herald.
It is my great pleasure to introduce you to The Herald's newest set of leaders. At our annual banquet on December 4th, we welcomed the 120th Editorial Board and the newest business, editorial and post- magazine leadership. In 2009, The Herald has doubled the size of its digital archive and made tremendous strides towards ensuring that Brown's best and brightest can work on the The Herald, regardless of their financial circumstances. We are making steady progress towards our goal for the first-ever Brown Daily Herald Annual Appeal: $10,000 by New Year's. I am thrilled to report that we are only $2,500 away! I hope that you will help make the inaugural Annual Appeal a success.


Class iGivefirst
Main interface for the iGivefirst Donation API
Located at iGivefirst.php
public
|
#
__construct( string $apikey, string $apisecret, boolean $sandbox = true )
Construct the interface class |
public
|
public
mixed
|
$donor |
|
|
public
mixed
|
$account |
|
|
public
mixed
|
$donation |
|
|
public
mixed
|
$client |
|


Home
Need help?
(current)
Hardware
Software
Internet access
Make a request
Offer Help
Requests gallery
Post your help
Offer
Gallery
Are you in need of something? Be confident to contact some of the people that have offered their help.
Search
Hardware
Software
Internet Access


SCORE
PC
0
-
0
YOU
Rocks
Papyrus
Scissor
vs PC
Reset
Required Victories
2
3
4
5
Cartoon Vectors from Vecteezy
All other stuff by me


---
layout: post
status: publish
published: true
title: Custom XML Serialization for the .NET Compact Framework
author:
display_name: Geoff Lane
login: admin
email<EMAIL_ADDRESS>url: http://www.zorched.net
author_login: admin
author_email<EMAIL_ADDRESS>author_url: http://www.zorched.net
date: '2007-02-28 11:25:15 -0500'
date_gmt: '2007-02-28 17:25:15 -0500'
categories:
- Code
- ".NET"
tags:
- compact framework
- xml
- windows-mobile
---
.NET provides a whole slew of utilities for serializing objects into an XML form. But as I wrote in my previous post, .NET Compact Framework has serious problems with this serialization. The good news is that you can leverage all of the existing Attributes and tricks that you think should work (if it weren't so buggy) and use them in your own serialization scheme.
Get Started
For example I want to know if I should skip a given member? There are a number of different things I can check. Is a Reference type null? Is there and XmlIgnore attribute? Is there a PropertyNameSpecified value set to false? All of those questions can easily be answered using reflection.
{% highlight csharp %}
///
/// Should the current property be skipped based on rules
/// such as the existence of a propertySpecified value set to false?
///
/// The MemberInfo to check
/// The object that contained this member
/// true if this member should be skipped
public bool SkipMember(MemberInfo member, object o)
{
object val = null;
if (member.MemberType == MemberTypes.Field)
{
val = ((FieldInfo)member).GetValue(o);
}
else if (member.MemberType == MemberTypes.Property)
{
val = ((PropertyInfo)member).GetValue(o, null);
}
if (null == val)
return true;
string propertyToTest = member.Name + "Specified";
PropertyInfo specifiedProperty = o.GetType().GetProperty(propertyToTest);
if ((null != specifiedProperty && !(bool)specifiedProperty.GetValue(o, null)))
return true;
FieldInfo specifiedField = o.GetType().GetField(propertyToTest, FIELD_BINDING_FLAGS);
if ((null != specifiedField && !(bool)specifiedField.GetValue(o)))
return true;
return member.IsDefined(typeof(XmlIgnoreAttribute), false);
}
{% endhighlight %}
I can use a similar "fall-through" strategy to determine the name of the element to write using the XmlElement attribute for example. Now that I know I can answer some basic questions about an Object using the built-in mechanisms that .NET uses for serialization I can get down to serious serialization.
We're all Object-Oriented programmers these days right? Right!? So to start I decided that the best way to handle this problem was to decompose it into a bunch of simpler problems.
ITagWriter
There are two things that we can write in XML. Either an XML Element or an XML Attribute. So, I created an interface ITagWriter
with two concrete implementations to correspond to these two XML types: AttributeTagWriter
and ElementTagWriter
. These classes allow me to write the structure of the XML Document.
{% highlight csharp %}
///
/// Interface to implement to write different Xml tags
/// Either Elements or Attributes.
///
internal interface ITagWriter
{
///
/// Write the opening Xml tag with the given name
///
/// The XML Document to write the tage to.
/// The name of the tag
void WriteStart(XmlWriter doc, string tagName);
///
/// Write the appropriate end tag
///
/// The XML Document to write the tage to.
void WriteEnd(XmlWriter doc);
}
{% endhighlight %}
IValueWriter
With the ability to write the structure, I then need to be able to write out the values of the various objects and their properties. Just like with the ITagWriter
interface, I decided to create an IValueWriter
for the various kinds of values that I would need to write. The types I came up with were ObjectWriter
, CollectionValueWriter
, EnumValueWriter
, SimpleValueWriter
, and XmlElementValueWriter
.
{% highlight csharp %}
///
/// Interface to implement to write different kinds of values.
///
internal interface IValueWriter
{
///
/// Write the Entry value to the XmlDocument
///
/// The XML Document to write the tage to.
/// The meta-information and value to write.
void Write(XmlWriter doc, CustomSerializationEntry entry);
}
{% endhighlight %}
You'll notice the CustomSerializationEntry
class
is the parameter for the IValueWriter.Write()
method. This class contains all of the metadata and the
value about the various properties of an Object. This alows us an easy way
to ask questions about a given property. Is it a Collection? Is it an Enum?
Is there a sort order? Basically the idea is to encapsulate all of the
things that are interesting from a serialization point of view.
To help manage the interaction I also created a basic TypeLookup
class. The job of this class is to
determine what type of ITagWriter
and IValueWriter
to use for a
given CustomSerializationEntry
instance. This allows us to centralize that decision making in a
single class. The centralized knowledge keeps the individual writer
implementations much simpler. They just need to ask for the correct
writer and then call the methods defined in the interface. They don't
need to care what type they are writing. All hail power of
encapsulation and abstraction!
Start Serializing
I bootstrap the serialization by creating an ObjectWriter to handle the
outermost object. From there, the ObjectWriter takes over, constructing
CustomSerializationEntry objects for each of the serialized object's
properties. The type of the property determines the type of IValueWriter that
is used to write the property value.
{% highlight csharp %}
///
/// Serialize an object using the given
/// xmlRoot as the root element name.
///
///
///
///
public string Serialize(object o, string xmlRoot)
{
StringBuilder sb = new StringBuilder();
using (XmlTextWriter writer = new XmlTextWriter(new StringWriter(sb)))
{
writer.Formatting = Formatting.Indented;
XmlWriter xmlDoc = XmlWriter.Create(writer);
WriteRootElement(xmlDoc, o, xmlRoot);
}
return sb.ToString();
}
private static void WriteRootElement(XmlWriter doc, object o, string rootElement)
{
doc.WriteStartDocument();
ObjectWriter writer = new ObjectWriter(new TypeLookup());
writer.Write(doc, o, rootElement);
doc.WriteEndDocument();
}
{% endhighlight %}
The ObjectWriter itself creates a CustomSerializationEntry for all the
properties that should be written. It then loops over the properties. Notice
how it uses the TypeLookup (lookup) to ask for the proper value writer for
each of the properties.
{% highlight csharp %}
// ...
public void Write(XmlWriter doc, object o, string elementName)
{
doc.WriteStartElement(elementName);
IEnumerable entries = GetMemberInfo(o);
foreach (CustomSerializationEntry currentEntry in entries)
{
lookup.GetValueWriter(currentEntry).Write(doc, currentEntry);
}
doc.WriteEndElement();
}
// ...
{% endhighlight %}
Conclusion
OK, so I left out a lot of details! But If I gave you all of the answers it
wouldn't be any fun now would it. I hope you can see how decomposing the
problem of serialization turns it a series of relatively simple problems that
you can answer. So, if I can do this in about 500 lines of code, how come
Microsoft can't implement a decent XML Serializer for the .NET Compact
Framework.


Access Denied
You don't have permission to access "http://www.army.mil/privacy" on this server.
Reference #18.b2fd4317.1480855753.180ce55


There were 100 unique nationalities and multi-nationalities identified on the Titanic. So for this representation we combined all multi-nationalities into one group called "Multi-Nationality", which leaves 44 unique nationalities. The only Naionality with more Saved than Lost was American. While the English were the most onboard, only 28% were Saved. In fact, due to the large number of English aboard, quite a few nationality's numbers are unviewable in this chart. If you have question or want me to work on a different representation, report an issue on GitHub which can be found by clicking my name at the bottom of this page. Also, don't forget about Miss Marison Wright who was a 26 years old English woman. Remember this as you continue to explore the other demographics.


|
Little Heroes
|
Delegate callback that Unity can serialize and set via Inspector. More...
Classes | |
| class | Parameter |
| Delegates can have parameters, and this class makes it possible to save references to properties that can then be passed as function arguments, such as transform.position or widget.color. More... | |
Public Member Functions | |
| delegate void | Callback () |
| EventDelegate () | |
| EventDelegate (Callback call) | |
| EventDelegate (MonoBehaviour target, string methodName) | |
| override bool | Equals (object obj) |
| Equality operator. More... | |
| override int | GetHashCode () |
| Used in equality operators. More... | |
| void | Set (MonoBehaviour target, string methodName) |
| Set the delegate callback using the target and method names. More... | |
| bool | Execute () |
| Execute the delegate, if possible. More... | |
| void | Clear () |
| Clear the event delegate. More... | |
| override string | ToString () |
| Convert the delegate to its string representation. More... | |
Static Public Member Functions | |
| static void | Execute (List< EventDelegate > list) |
| Execute an entire list of delegates. More... | |
| static bool | IsValid (List< EventDelegate > list) |
| Convenience function to check if the specified list of delegates can be executed. More... | |
| static EventDelegate | Set (List< EventDelegate > list, Callback callback) |
| Assign a new event delegate. More... | |
| static void | Set (List< EventDelegate > list, EventDelegate del) |
| Assign a new event delegate. More... | |
| static EventDelegate | Add (List< EventDelegate > list, Callback callback) |
| Append a new event delegate to the list. More... | |
| static EventDelegate | Add (List< EventDelegate > list, Callback callback, bool oneShot) |
| Append a new event delegate to the list. More... | |
| static void | Add (List< EventDelegate > list, EventDelegate ev) |
| Append a new event delegate to the list. More... | |
| static void | Add (List< EventDelegate > list, EventDelegate ev, bool oneShot) |
| Append a new event delegate to the list. More... | |
| static bool | Remove (List< EventDelegate > list, Callback callback) |
| Remove an existing event delegate from the list. More... | |
| static bool | Remove (List< EventDelegate > list, EventDelegate ev) |
| Remove an existing event delegate from the list. More... | |
Public Attributes | |
| bool | oneShot = false |
| Whether the event delegate will be removed after execution. More... | |
Properties | |
| MonoBehaviour | target [get, set] |
| Event delegate's target object. More... | |
| string | methodName [get, set] |
| Event delegate's method name. More... | |
| Parameter[] | parameters [get] |
| Optional parameters if the method requires them. More... | |
| bool | isValid [get] |
| Whether this delegate's values have been set. More... | |
| bool | isEnabled [get] |
| Whether the target script is actually enabled. More... | |
Delegate callback that Unity can serialize and set via Inspector.
| EventDelegate.EventDelegate | ( | ) |
| EventDelegate.EventDelegate | ( | Callback | call | ) |
| EventDelegate.EventDelegate | ( | MonoBehaviour | target, |
| string | methodName | ||
| ) |
|
static |
Append a new event delegate to the list.
|
static |
Append a new event delegate to the list.
|
static |
Append a new event delegate to the list.
|
static |
Append a new event delegate to the list.
| delegate void EventDelegate.Callback | ( | ) |
| void EventDelegate.Clear | ( | ) |
Clear the event delegate.
| override bool EventDelegate.Equals | ( | object | obj | ) |
Equality operator.
| bool EventDelegate.Execute | ( | ) |
Execute the delegate, if possible.
This will only be used when the application is playing in order to prevent unintentional state changes.
|
static |
Execute an entire list of delegates.
| override int EventDelegate.GetHashCode | ( | ) |
Used in equality operators.
|
static |
Convenience function to check if the specified list of delegates can be executed.
|
static |
Remove an existing event delegate from the list.
|
static |
Remove an existing event delegate from the list.
| void EventDelegate.Set | ( | MonoBehaviour | target, |
| string | methodName | ||
| ) |
Set the delegate callback using the target and method names.
|
static |
Assign a new event delegate.
|
static |
Assign a new event delegate.
| override string EventDelegate.ToString | ( | ) |
Convert the delegate to its string representation.
| bool EventDelegate.oneShot = false |
Whether the event delegate will be removed after execution.
|
get |
Whether the target script is actually enabled.
|
get |
Whether this delegate's values have been set.
|
getset |
Event delegate's method name.
|
get |
Optional parameters if the method requires them.
|
getset |
Event delegate's target object.


Across: 1. Tiny time-piece? (6) 4. A couple of hundred employed in the dock (7) 9. Rodeo star upset bullfighters (9) 10. Avoid duel arranged by egg-head (5) 11. Revulsion about Bob's urgency! (5) 12. A purse one opens for continentals (9) 13. Acts superficially with French star in part of Yorkshire (7) 15. Twitch after car crash in frozen north (6) 17. Make hungry deserters return by 8/5/45 (6) 19. Tramps found on the border (7) 22. Claimant entered PR set-up (9) 24. Surrounded by a thousand using force (5) 26,8dn. Scottish side of a short river (5 6) 27. Wet spell, possibly, to end dry spell? (4 5) 28. Log gets cut up for pegs (7) 29. Father inspects Turks Head (6) Down: 1. Found suitable rug with Edward after church (7) 2. Standards produced by wisdom? (5) 3. Gypsy salesman? (9) 4. Country song about Union Street (7) 5. Move quietly about and look back (5) 6. Easily shocked at his masque (9) 7. Stylish boat in Ryde spectacular (6) 8. See 26 14. Annoying alternative held by Mr Crosby (9) 16. Carried on mixing herb (9) 18. Dee runs about to find bears (7) 19. Horrible doctor dissected bird! (6) 20. Propose dismantling g-gusset (7) 21. Character one carried by return journeys (6) 23. The Spanish surround the girl (5) 25. Big cat in zoo unceremoniously shot! (5)


Imagr is an application designed to be run from a NetInstall environment created with AutoNBI. It is able replace tools such as DeployStudio for many organisations without the requirement of needing to be run on OS X servers.
Features Include
- Restore ASR Images (such as those created with AutoDMG)
- Install packages during Imagr run and at first boot
- Run scripts during Imagr run and at first boot
- Include other workflows in your workflow, specified statically or using a script
- Erase and partition disks
- Rename the machine
- Protect your users from accidentally wiping their devices by specifying a password for Imagr
For more information on Imagr, check out Imagr on github.


“ I’ve been interested in coding for a while but never taken the jump, until now. I couldn’t recommend this course enough. I’m now in the job of my dreams and so excited about the future. ”
“ I’ve been interested in coding for a while but never taken the jump, until now. I couldn’t recommend this course enough. I’m now in the job of my dreams and so excited about the future. ”


{% extends 'layout_home.html'%}
{% block title %} Home {% endblock %}
{% block body %}
Welcome to Sketch Map Analyzer (SMA)
The SMA is a tool that analysis the accuracy and completeness of the drawn
spatial information in the input Sketch Map
with respect to spatial information in the Geo-referenced Map
The accuracy of input map is measured based on the preserved Qualitative Spatial Configurations:
Topological relations between polygonal features: i.e. Connected, Disconnected,
Overlaps, etc.
Topological relations between linear features: i.e. Connected, Disconnected, crosses,
etc.
LeftRight relations between polygonal and linear features: i.e. Left_of, Right_of,
Crosses, etc.
Linear ordering relations between polygonal along a route: i.e. Before, After,
Overlaps, etc.
Topological relations between polygonal and linear features: i.e. Connected, Disconnected, crosses,
etc.
Relative orientation relations between linear features: i.e. Left_of, Right_of; Front_of, Half_left, etc.