C/C++ Goes-to Operator ??

Have you ever heard about the "Goes-to" operator (-->) in C and C++ ?
No? So, check out the following code:

#include <stdio.h>
int main()
{
    int x = 5;
    while (x --> 0) // X goes to 0
    {
        printf("%d ", x);
    }
}

The previous code compiles. Actually, there is no operator in C and C++ called "Goes-to". It's two separate operators; decrementing x and return its original value (-- operator), and then compare it if greater than zero (> operator).

To better understand, the while statement could be written as follows:
while ( (x--) > 0 ) .

A New Variant of Douglas–Peucker Algorithm (2/4) [Original Algo. MATLAB Implementation]

Previous Posts  

A New Variant of Douglas–Peucker Algorithm (1/4)

Original Douglas-Peucker Algorithm

The following algorithm description is taken from Wikipdeia [1] and CodeProject article by Elmar de Koning [2]. The Ramer–Douglas–Peucker algorithm (RDP) is an algorithm for reducing the number of points in a curve that is approximated by a series of points. This algorithm is also known under the names Douglas–Peucker algorithm, iterative end-point fit algorithm and split-and-merge algorithm.

The Douglas-Peucker algorithm uses a point-to-edge distance tolerance. The algorithm starts with a crude simplification that is the single edge joining the first and last vertices of the original polyline. It then computes the distance of all intermediate vertices to that edge. The vertex that is furthest away from that edge, and that has a computed distance that is larger than a specified tolerance, will be marked as a key and added to the simplification. This process will recurse for each edge in the current simplification, until all vertices of the original polyline are within tolerance of the simplification results. This process is illustrated below:

Initially, the simplification consists of a single edge. During the first step, the fourth vertex is marked as a key and the simplification is adjusted accordingly. During the second step, the first edge of the current simplification is processed. The maximum vertex distance to that edge falls below the tolerance threshold, and no new key is added. During the third step, a key is found for the second edge of the current simplification. This edge is split at the key and the simplification is updated. This process continues until no more keys can be found. Note that at each step, only one edge of the current simplification is processed.
This algorithm has a worst case running time of O(nm), and O(n log m) on average, where m is the size of the simplified polyline. As such, this is an output dependent algorithm, and will be very fast when m is small. To make it even faster, the Distance between points routine is applied as a pre-processing step.

MATLAB Implementation

function out_points = points_simplify_2d(points, epsilon)

  id_end = size(points,1);

  id_start = 1;

  % Indeces of points are not removed by Douglas-Peucker algorithm

  remaining_ids = true(id_end,1);

  % Call douglas_peucker_iteration (recursive function)

  [points remaining_ids] = douglas_peucker_iteration( ...
     points,epsilon,id_start,id_end, remaining_ids);

  out_points = points(remaining_ids,:);

end

function [points remaining_ids]  = douglas_peucker_iteration(points, epsilon, id_start, id_end, remaining_ids)

  % For the points (start + 1) to (end) -> next_points_relative is

  % relative coordinates from start point

  next_points_relative = bsxfun(@minus, points(id_start+1:id_end,:), 

     points(id_start,:));

  end_point_relative = next_points_relative(end,:)';

  % Efficient Method to get distances_from_start_end_line

  beta = (end_point_relative' *

     next_points_relative')./(end_point_relative'*end_point_relative);

  b = next_points_relative-bsxfun(@times,beta,end_point_relative)';

  distances_from_start_end_line = hypot(b(:,1),b(:,2));

  % Identify maximum distance and get its index

  [dmax dmax_id] = max(distances_from_start_end_line);

  dmax_id  = id_start + dmax_id; %ID of the edge point

  if dmax <= epsilon;
    remaining_ids(id_start+1:id_end-1) = false; 
  else  

    [points remaining_ids] = douglas_peucker_iteration( ...
       points,epsilon,id_start,dmax_id, remaining_ids);

    [points remaining_ids] = douglas_peucker_iteration( ...

       points,epsilon,dmax_id,id_end, remaining_ids);

  end

end

______________________________________________________________________
References:
[1] http://en.wikipedia.org/wiki/Ramer-Douglas-Peucker_algorithm
[2] Polyline Simplification

A New Variant of Douglas–Peucker Algorithm (1/4) [Introduction]

The Ramer-Douglas-Peucker is a polyline simplification algorithm that uses a point-to-edge (point-to-line) distance tolerance “Epsilon”. The algorithm starts with a crude simplification that is the single edge (line) joining the first and last vertices (points) of the original polyline (polyline needed to be simplified). There is a variant of this algorithm already that allows it to produce a polyline with a fixed number of vertices “N”.

From software points of view, sometimes it’s preferred to have a fixed-size array to store a polyline vertices. Thus, the variant version of the Douglas-Peucker algorithm, that produces a fixed number of vertices “N”, is more convenient. However, from applications point of view, it doesn’t make sense to describe a simple polyline (rectangular area for example) with the same number of vertices that describe a complex-shaped one. This is why I’ve introduced my own version of the Douglas-Peucker algorithm, which I call a “Regularized” version.

My modified algorithm takes two pieces of data as inputs. The first is a predefined maximum number of vertices "N". The second is a tolerance "Epsilon". The algorithm returns n ≤ N vertices; it excludes the vertices that over-fit according to the predefined tolerance "Epsilon”. Those are the vertices that would have not been selected using the original Douglas-Peucker algorithm if it runs using the given "epsilon". A sample results of my variant of the Douglas–Peucker algorithm are shown in the coming table.

(A) N=50 , Epsilon=1.5 :	(B) N=50 , Epsilon=1.0 :
(C) N=100 , Epsilon=1.5 :	(D) N=10 , Epsilon=1.5 :

In the previous table, polyline (B) contains more vertices than polyline (A), because decreasing Epsilon allows more vertices to produce max edge distances higher than Epsilon, while these points still produce a polyline with number of vertices less than N. The resulted polyline in (C) is the same as (A), because increasing N, while having the same Epsilon will not produce new vertices that fits that Epsilon. Polyline in (D) contains fewer vertices than the polyline in (A), because the number of vertices in polyline (A) is greater than the N in (D).

In a coming posts, I will post the algorithms and MATLAB implementations for the three configurations:
- Original Douglas-Peucker algorithm.
- Variant of Douglas-Peucker algorithm (fixed number of simplified vertices "N").
- My Variant of Douglas-Peucker algorithm (with "N" and a tolerance "Epsilon").