Dr JTS
My previous blog post reviewed the concept of the Hausdorff distance (which more descriptively could be called farthest distance.) Despite its usefulness in matching geometric data, there are surprisingly few open-source implementations, and seemingly no efficient ones for linear and polygonal...
Dr JTS
The Hausdorff Distance is a useful spatial function which can appear slightly mysterious. Partly this is due to the name. It honours Felix Hausdorff, one of the founding fathers of topology, and a polymath who was creative in music and literature as well as mathematics. Felix Hausdorff ...
Dr JTS
Some spatial use cases require identifying "narrow" or "skinny" polygons. A classic example is the process of cleaning polygonal coverages. Coverages (even clean ones) may contain narrow gaps between polygons which are unwanted. But they may also contain larger gaps which are valid. A geometric...
Dr JTS
The JTS Topology Suite has been rolling out the capability to manage polygonal coverages. It supports modelling polygonal coverages as arrays of discrete polygonal geometries. This is simple to work with and allows using all of the wide variety of JTS algorithms. Coverage topology allows...
Allen Sallinger
What is a Binary Tree A binary tree is a data structure that consists of nodes in a tree. Each node has three attributes: a value and a left and right child node. As simple binary tree would look like the following: 1 / \ 3 2 / \ 4 5 What is a Binary Search...
Dr JTS
A previous post introduced a new algorithm in the JTS Topology Suite called RelateNG. It computes topological relationships between geometries using the Dimensionally-Extended 9 Intersection Model (DE-9IM) model. This algorithm is fundamental to a large proportion of spatial queries executed in...
Dr JTS
The most fundamental and widely-used operations in the JTS Topology Suite are the ones that evaluate topological relationships between geometries. JTS implements the Dimensionally-Extended 9 Intersection Model (DE-9IM), as defined in the OGC Simple Features specification, in the RelateOp...
Dr JTS
A new capability for the JTS Topology Suite is operations to process Simple Polygonal Coverages. A Simple Polygon Coverage is a set of edge-matched, non-overlapping polygonal geometries (which may be non-contiguous, and have holes). Typically this is used to model an area in which every point...
Dr JTS
The next operation delivered in the build-out of Simple Polygonal Coverages in the JTS Topology Suite is Coverage Union. This is simply the topological union of a set of polygons in a polygonal coverage, producing one or more polygons as the result. (This is sometimes called "dissolve" in the...
Dr JTS
Recently JTS gained the ability to compute Concave Hulls of point sets. The algorithm used is based the Chi-shapes approach described by Duckham et al. It works by eroding border triangles from the Delaunay Triangulation of the input points, in order of longest triangle edge length, down to a...
Dr JTS
The previous post discussed polygonal coverages and outlined the plan to support them in the JTS Topology Suite. This post presents the first step of the plan: algorithms to validate polygonal coverages. This capability is essential, since coverage algorithms rely on valid input to provide...
Dr JTS
An important concept in spatial data modelling is that of a coverage. A coverage models a two-dimensional region in which every point has a value out of a range (which may be defined over one or a set of attributes). Coverages can be represented in both of the main physical spatial data models:...
Dr JTS
The previous post introduced the new ConcaveHullOfPolygons class in the JTS Topology Suite. This allows computing a concave hull which is constrained by a set of polygonal geometries. This supports use cases including:generalization of groups of polygonjoining polygonsfilling gaps between...
Dr JTS
A common spatial need is to compute a polygon which contains another set of polygons. There are numerous use cases for this; for example:Generalizing groups of building outlines (questions: 1, 2) Creating "district" polygons around block polygons (questions: 1)Removing gaps between sets of...
Dr JTS
The electrons were hardly dry on the JTS Outer and Inner Polygon Hull post when another interesting use case popped up on GIS StackExchange. The question was how to remove aliasing artifacts (AKA "jaggies") from polygons created by vectorizing raster data, with the condition that the result...
Dr JTS
The JTS Topology Suite recently gained the ability to compute concave hulls. The Concave Hull algorithm computes a polygon enclosing a set of points using a parameter to determine the "tightness". However, for polygonal inputs the computed concave hull is built only using the polygon vertices,...
teymour
Note: you can find the question paper on the BIO website Part A This problem can be solved using a recursive algorithm: function is_pat(string: String) -> bool if string.len() == 1 then return True else is_pat = False for i=0 to string.len() - 2 do...
Dr JTS
As the title of this blog indicates, I'm a fan of linearity. But sometimes a little non-linearity makes things more interesting. A convenient way to generate non-linear curved lines is to use Bezier Curves. Bezier Curves are curves defined by polynomials. Bezier curves can be defined for...
Dr JTS
A common spatial need is to find a polygon that accurately represents a set of points. The convex hull of the points often does not provide this, since it can enclose large areas which contain no points. What is required is a non-convex hull, often termed the concave hull. The Convex Hull and a...
Dr JTS
Offset curves (also known as parallel curves) are an oft-requested feature in JTS. They are a natural extension to the concept of buffering, and are useful for things like placing labels along rivers. As far as I know there is no hard-and-fast definition for how an offset curve should be...
Dr JTS
A (long) while ago I posted about "soon-to-be-released" JTS code for polygon triangulation using Ear Clipping. It turned out it was actually in the category of "never-to-be-released". However, later I worked with a student, Dan Tong, on a coding exercise sponsored by Facebook. We decided to...
Dr JTS
Recently a GEOS patch was contributed to change the KdTree query implementation to use an explicit stack rather than recursion. This has been ported to JTS as PR #779 (along with some refactoring).The change was motivated by a QGIS issue in which a union of some large polygons caused a stack...
DK
Today I launched a new novelty Mac app, Retro Dither. Retro Dither gives any photo a cool retro look using just black and white pixels. You may want this for artistic effect, or you may want to export your photo to MacPaint for display on a retro Mac. Retro Dither launched on the Mac App Store...
Dr JTS
In a previous post I described how the JTS Topology Suite operation IsSimpleOp has been completely rewritten to reduce code dependencies, improve performance, and provide a simpler, more understandable implementation. The post points out that the IsValidOp implementation would benefit from the...
Adrian Mejia Blog
A priority queue is a versatile data structure that is good to have under your algorithmic toolbelt. In this post, we discuss, what it is, real-world applications, and we explore two different implementations, the latter one being more robust. What’s a Priority Queue (PQ)?A priority queue is a...
Dr JTS
Hard to believe that the JTS Topology Suite is almost 20 years old. That's 140 in dog years! Despite what they say about old dogs, one of the benefits of longevity is that you have the opportunity to learn a trick or two along the way. One of the key lessons learned after the initial release of...
Adrian Mejia Blog
Finding out the time complexity of your code can help you develop better programs that run faster. Some functions are easy to analyze, but when you have loops, and recursion might get a little trickier when you have recursion. After reading this post, you are able to derive the time complexity of...
Adrian Mejia Blog
Graphs are one of my favorite data structures because you can model many real-life situations with them. Such problems involve finding the shortest paths between 2 or more locations, scheduling courses, finding relationships in family trees, solving mazes, and many more! As a result, it’s...
Adrian Mejia Blog
Binary Search Trees (BST) is used for many things that we might not be aware of. For instance: in compilers to generate syntax trees, cryptography and in compressions algorithms used in JPG and MP3. However, search trees need to be balanced to be fast. So, we are going to discuss how to keep the...
Adrian Mejia Blog
Tree data structures have many uses, and it’s good to have a basic understanding of how they work. Trees are the basis for other very used data structures like Maps and Sets. Also, they are used on databases to perform quick searches. The HTML DOM uses a tree data structure to represents the...
Adrian Mejia Blog
In this post, we are going to explore non-linear data structures like graphs. Also, we’ll cover the central concepts and typical applications. You are probably using programs with graphs and trees. For instance, let’s say that you want to know the shortest path between your workplace and home. You...
Adrian Mejia Blog
When we are developing software, we have to store data in memory. However, many types of data structures, such as arrays, maps, sets, lists, trees, graphs, etc., and choosing the right one for the task can be tricky. This series of posts will help you know the trade-offs so that you can use the...
Adrian Mejia Blog
Analyzing the running time of non-recursive algorithms is pretty straightforward. You count the lines of code, and if there are any loops, you multiply by the length. However, recursive algorithms are not that intuitive. They divide the input into one or more subproblems. On this post, we are...
.jpg)
Adrian Mejia Blog
SummaryLearn how to compare algorithms and develop code that scales! In this post, we cover 8 Big-O notations and provide an example or 2 for each. We are going to learn the top algorithm’s running time that every developer should be familiar with. Knowing these time complexities will help you to...
Adrian Mejia Blog
As a developer, you have the power to change the world! You can write programs that enable new technologies. For instance, develop software to find an earlier diagnosis of diseases. But that’s not the only way. You might do it indirectly by creating projects that make people more productive and...
Aram’s Lair of Mad Science
I built a reference cookbook of algorithms and data structures for contest problem solvers. It’s written in the Rust programming language, as I believe it’s ideally suited to the task. For more info, please check out the repository at github.com/EbTech/rust-algorithms. While I believe Rust is...
Jeffrey Wang
Last time, I wrote about a clever algorithm for approximating the histogram for a stream using bounded memory. The post was motivated by this paper, which is an extension of that algorithm to a problem that seems unrelated at first glance, which is matrix sketching. The matrix sketching problem is...
Jeffrey Wang
It's been a while, but I finally motivated myself to write another blog post! Today's topic is approximating the frequency of items in a stream. With all the data that is generated today, streaming algorithms have become very popular as one of the efficient ways to process datasets that are far...