Venn diagram generation software from RCC(8) speci

问题:

Please note: While the bounty is no longer available, I'm still keen for anyone with an answer to this question to contribute; I'm still watching it, and I'm waiting to see if there is a better answer. Thanks, and please read on...

---

I am looking for a way to convert an arbitrary set of RCC-like spatial relations (or similar) describing a constraint network into Venn-diagram-like images. For example, the constraint network as expressed in RCC8:

W {EC} Y, X {TPP} Y, Z {NTPP} Y, Z {PO} X.

..could be represented by the following diagram with circular or square regions:

..alternatively:  

Is anyone aware of software that can at least generate such diagrams programmatically (via an API) from a specification of RCC-like constraints?

I am aware that such a constraint network could be underspecified, precluding a match to any single such diagram (many solutions may exist). Ideally, I would like to deal with this by being able to generate possible alternatives, but can resort to none (and raising an error) for now.

Just to be clear, in this question I am specifically asking for software which can calculate a diagram layout based on RCC-like constraints in a declarative manner. I am not concerned with tools to turn a DSL for RCC into some other syntax, nor am I interested in particular image serialization formats or methods. I am hoping to find an algorithm to do this for dealing with an arbitrary number of constraints for up to six unique sets.

Notes: Graphviz (as @vickirk mentioned below) is an example of a diagram layout software package, which is akin to what I'm after. Unfortunately, it seems that Graphviz itself cannot help with this problem (but I'd be very happy to be proven wrong!). It seems this is a very hard problem.

回答1:

Who need's a backend? Here's a working prototype using HTML/CSS/JS:

http://jsfiddle.net/RuvE6/6/

Just enter the RCC8 code syntax in the field and hit the button!

Some current limitations:

• Doesn't handle ambiguity
• There's no error handling if syntax is off
• Probably breaks in some valid cases (I haven't tested very much)
• Didn't implement any inverse cases (yet?)

Edit: How it works

Basically, there are two families of relationships shown with these diagrams:

• A contains B
• A is adjacent to B.

There are then sub-types or variations, like:

• A contains B and B is tangential to A
• A is adjacent to B and A overlaps with to B

Both of the basic concepts are kind of baked into the HTML rendering world:

• containment --> nested HTML elements: <div class="region"><div class="region"></div></div>
• adjacency --> sibling HTML elements: <div class="region"></div><div class="region"></div>

I handle the variations with special classes that (rather crudely) wiggle margins around to accomplish the desired layout:

• containment, with tangent: <div class="region"><div class="region touches-parent"></div></div> (child has negative top margin to touch parent)
• adjacency, with overlap: <div class="ven"><div class="region"></div><div class="region touches-parent"></div></div> (a wrapper is added to trigger CSS on the children - the second element has negative left margin to overlap the first.)

There is some static markup commented out in the jsfiddle showing the structure I started with.

To complete the functional loop, there is a bit of code that parses the RCC8 statement into A {XX} B parts, and attempts to render the necessary markup for each part. It checks as it goes to not duplicate regions. I also go through afterwards and set the heights of all sibling the same, which ensures they will overlap and/or abut properly.

This code is really just a start, and it has it's conceits. It's basically a linear diagram, which means it doesn't, for instance, handle cases where there are complicated adjacencies, like this:

A {EC} B, C {EC} B, D {EC} B

These might be handled be smarted JS parsing and more complicated CSS, but probably quickly venture into the realm of more force-directed layouts (a smarter bubble chart, for instance).

回答2:

I don't know of any software that can generate such diagrams. However, If I had to tackle your problem I would probably explore the possibility of using Scalable Vector Graphics (SVG). I think you can translate your DSL for RCC into SVG XML, and then you can render it (maybe in a Web browser). You can easily find examples on the Web by searching for "svg venn diagram". A nice one is here: here's a diagram that I generate from that website

and here's the corresponding SVG code (also from the website):

<?xml version="1.0" encoding="UTF-8" standalone="yes"?>
<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.0//EN" "http://www.w3.org/TR/2001/REC-SVG-20010904/DTD/svg10.dtd">
<svg 
    height="150" 
    width="200" 
    xmlns="http://www.w3.org/2000/svg" 
    xmlns:svg="http://www.w3.org/2000/svg" 
    xmlns:xlink="http://www.w3.org/1999/xlink">    
<title >WIBR Venn diagram</title>
    <ellipse 
        cx="141.795128105731" 
        cy="75" 
        id="circle2" 
        rx="58.2048718942687" 
        ry="58.2048718942687" 
        style="fill: gray; fill-opacity: 0.5; stroke: black; stroke-width: 1; stroke-opacity: 1" />
    <ellipse 
        cx="67.2091969126074" 
        cy="75" id="circle1" 
        rx="67.2091969126074" ry="67.2091969126074" 
        style="fill: darkgray; fill-opacity: 0.5; stroke: black; stroke-width: 1; stroke-opacity: 1"/>
</svg>

There's also an Apache toolkit for SVG called Batik, which should support display, generation or manipulation of SVGs.

Another option is to use TikZ & PGF with LaTeX: there you have powerful macros that let you programmatically place shapes, and the rendering is done by LaTeX. Here's an example:

\documentclass[a4paper,10pt]{article}

\usepackage{tikz}
\usetikzlibrary{shapes,calc}

\begin{document}

\pagestyle{empty}

\begin{tikzpicture}

    \node (TPP) {X TPP Y};

    \node
        [ circle,
            draw,
            minimum width=2cm,
            label={[label distance=-0.7cm]145:X},
        ] (X) [right of=TPP,xshift=1cm] {};

    \node
        [ circle,
            draw,
            minimum width=1cm,
            anchor=south east,
        ] (Y) at (X.south east) {Y}; 

\end{tikzpicture}

\end{document}

which produces the following (i.e. the RCC8 TPP relation):

You can see from the LaTeX code that you can draw the Y circle at south west of X (X.south west) saying that Y's anchor is also at south west (anchor=south west). You can find a more complex example here, and some additional discussion here.

Although this is not yet a layout algorithm that draws RCC8 relation for you, I think you can define LaTeX macro that translate RCC8 relations into PGF/TikZ macros. The drawback is that you must then compile the LaTeX code.

I hope this helps and good luck!

回答3:

Have you evaluated antlr, You could define an EBNF grammar for RCC8. Use antlr to generate an item list. This item list can be used as an input to software like VennMaster for drawing diagrams.

Other options are Goolge Charts ,

http://bioinfogp.cnb.csic.es/tools/venny/index.html