db4o-sp / Blog: Recent posts

I was published link to full paper (czech language) about this work and shortened English version of this paper.

Please, see download section (https://sourceforge.net/projects/db4o-sp/files/Technical%20report/)

For some question, please send mail to polach.ondrej@email.cz

Compact jar file with source codes and javadoc was added to downloads section (Home/Compact repository/db4o-sp.jar).

Technical report will be available for download as soon as possible.

There are some observations from development which can be useful for other developers who want to implements its own spatial extension.

1) When you choose database for spatial extension, you need to determine the most useful information about it. Focusing mainly on the extension points, such as integration of its own indexing strategy, etc.... read more

There is a list with dependencies for this spatial extension of db4o:

• Apache Commons Math 2.2 or higher here
• db4o 8.1 or higher here
• JInterval here
• JScience here

I am finishing my work.

SVN repository contains implementation of building geometry graph with doubly connected edge list, which is convenient for operations relate and overlay.

Relate is implemented but have to be more tested...

For overlay, graph to geometry conversion must be implemented (class Graph2GeometryTransformer).
Face labels should be used for this.

Operations as distance, buffer, convex hull, area, perimeter and some other less significant operations are not implemented.... read more

I implemented persistence for geometries. These can be store in db4o. Querying was described before this.

Each geometry has its own object's graph. During each update, this graph is updated. So some objects are created, updated or deleted.
For example, if user remove point from line string, object of this point is removed from database during update process and so on. Of course, transparently for users. User uses only store or delete on its geometries.... read more

Spatial objects will be query as other objects. So, using native query or SODA, (and may be using QBE). Well, but what about performance. SODA uses B-Trees index structure. Spatial objects needs other index structure, for example R-Tree. SODA should be extended for new index structures. But, for now, there is no direct API hook to implement own indexing strategy (for more information see http://community.versant.com/Forums/tabid/98/aft/11961/Default.aspx).

To repository added large majority of API implementation.
Some methods have not been implemented yet, but object structure of API was implemented.
Some specification was customized for Java (generic types). Designed and implemented way of changes of geometries. Because of this, some methods were added, witch is not in standard. For example, in ST_LineString are methods addAllPoints, AddPoint and RemovePoint witch should be used for change of line. Method getPoints return only unmodifiable list of points. Each geometry can contains parent which is notified about change to check feasibility of change (validity).... read more

I created factory for geometry graphs (GeometryGraphFactory), witch will be used for relate and overlay operations.

At this time, factory can creates ST_Point and ST_LineString instances.

I wanted to you use plane sweep algorithm (originally from Bentley and Ottmann), but there is one reason why I can not.
This algorithm need exact computation. I have exact computation for sign of determinant, but only for double input and I would need exact (rational) input. Why? Because of on every event point I need update status and for this I need orientation test. It is not problem, if this point is end point of edge(s) - is represented in double. But problem occurs, if point is intersection (computed) point. This point can be approximation of real point. Because line intersection can robustly decide intersection but construction of this point is only approximation - using homogenous coordinates. Then orientation test for this intersection point can failed and order of edges in status is bad! I try modification (current implementation of plane sweep in repository), but I finished with same conclusion, need orientation test for exact input. I can change kernel to handle exact input.
At this time, I implemented edge intersector naively, compare each edge with each other in O(n^2), but robustly (lineIntersector do robust decisions).
And I implemented simple snap rounder using Hobby's hot points where each graph's edge is compared witch each hot point's boundary edges in O(n^2).
These two components are contained in noder, witch do noding of graph. In this case slowly, but robustly.

Created higher layer of Overlay and Relate operations.
Overlay operations = intersection, union, difference, symmetric difference.
Relate operations - relations predicates (use DE-9IM).
Will be based on topology graph operations - edges intersection, snap rounding (noding), labeling...

I created factories for geometry and coordinates.
All geometries should be created using geometry factory.
Coordinates factory is used for coordinates creation - for example in HomogeneousCoordinateLine

I decided that extension will be support only 2D in first release.
However, I use strategy design pattern for simplify of next extension to 3D and so on.

Added line intersector for 2D.
Predicate is computed robustly, based on orientation test. Support COLLINEAR cases too.
For more information about intersection predicate computation see to code please (getCollinearCode mainly).

Computation of intersection point is based on homogeneous coordinates, so approximately, but robustly - use BigDecimal witch round off to double on finish of computation.

TODO: snap rounding.

Robust kernel based only on robust computation of sign of determinant.
This computation is based on Exact Computation Geometry with dynamic filter.
Dynamic filter based on interval arithmetic (JInterval). Algorithm source - http://hal.inria.fr/docs/00/34/42/81/PDF/interval_journal-1.pdf (Chapter 4.1).
Exact computation based on BigFraction number type from Apache Commons Math.
Determinant is computed by LU Decomposition from Apache Commons Math.... read more

Replaced by technical report

You can see the final version of theoretic preparation (but only in Czech). See section Files.

However, something is redesigned or more developed - see post of this blog for incremental informations.