CloudRunner

Algorithm: Topological Sweep of a Line Arrangement

Description:
Performs a topological sweep of a two-dimensional line arrangement in quadratic time. The sweep can be used for MMOSPA estimation for two targets.
Paper: Herbert Edelsbrunner, Leonidas J. Guibas, Topologically sweeping an arrangement, Journal of Computer and System Sciences, Volume 38, Issue 1, February 1989, Pages 165-194, ISSN 0022-0000

Marcus Baum, Peter Willett, Uwe D. Hanebeck, Calculating Some Exact MMOSPA Estimates for Particle Distributions, Proceedings of the 15th International Conference on Information Fusion (Fusion 2012), July 2012, Singapore

Tags: MMOSPA topological sweep line arrangement
Usage: Algorithm is public.
Viewed 3372 times, called 47 times
Upload:
Empty star Empty star Empty star Empty star Empty star
0 votes
Marcus Baum
11/04/2013 11:15 p.m. (version #1)

Run Algorithm

:
nx2 array consisting of n lines, where line E(i,:) is specified by slope E(i,1) and intercept E(i,2).
:
:
Allow cached result?
Close

Please Wait

Computation is running...

Plots

showing plot # of

Result Value(s)


		

Resource Usage

Execution of the algorithm took seconds.
Peak memory usage for running the algorithm was kilobytes (total usage: kilobytes).

Run ID / Link

ID of this run:
Link:

Result from Cache

Result has been delivered from cache and computed on (UTC).

Matlab log

(show)

		

Error

Using this algorithm in your local MATLAB environment is easy: Click here for instructions!

Usage Instructions for CloudRunner Client

  1. Download the CloudRunner Client by clicking here and place the downloaded file in your MATLAB working directory.

  2. Inside MATLAB, initialize the CloudRunner Client by calling CloudRunner:
    >> CloudRunner

    A login dialog will prompt for your CloudRunner mail address and password. For a start, you can leave the dialog empty and just click "Connect".

    Alternatively, you can provide the login credentials (or empty strings to skip login) as a parameter and hence skip the login dialog. This is useful when using CloudRunner in non-interactive scripts.
    >> CloudRunner('mail@example.com', 'password')

  3. Select this algorithm by its URL. Selecting an algorithm creates the lambda function that proxies calls to the algorithm to the server for execution:
    >> CloudRunnerSelect('http://www.cloudrunner.eu/algorithm/147/topological-sweep-of-a-line-arrangement/version/1/')

    For the sake of convenience, you can also use the algorithm ID instead of its URL for public algorithms.

  4. Call functions from the algorithm like any regular local function.

Note: You can find further information on the help page.

Source Code

File:

  1 function [sortedpermu,cellChanges] = topologicalSweep(E,plotSweep)
  2 % Performs a topological sweep of the two-dimensional line arrangement E as described in
  3 % 
  4 % Herbert Edelsbrunner, Leonidas J. Guibas, Topologically sweeping an arrangement, 
  5 % Journal of Computer and System Sciences, Volume 38, Issue 1, February 1989, Pages 165-194, ISSN 0022-0000
  6 %
  7 % This function is used for the purpose of calculating MMOSPA estimates, see
  8 % 
  9 % Marcus Baum, Peter Willett, Uwe D. Hanebeck, Calculating Some Exact MMOSPA Estimates for Particle Distributions,
 10 % Proceedings of the 15th International Conference on Information Fusion (Fusion 2012), July 2012, Singapore 
 11 % 
 12 % Input:
 13 % * E is an nx2 array consisting of n lines, where line E(i,:) is specified
 14 %   by slope E(i,1) and intercept E(i,2).
 15 % * plotSweep specifies if the sweep is plotted, i.e., 0 for no plotting, 1 for plotting the extracted vertices, 
 16 %   and 2 for plotting the entire sweep.
 17 %         
 18 % Output:
 19 % * sortedpermu returns the lines E sorted according to their slope.
 20 % * cellChanges is an array encoding the elementary steps performed during
 21 %   the sweep.
 22 % The sweep can be reconstructed from this information.
 23 %
 24 % Remarks: 
 25 % * No degeneracy check and handling is performed.
 26 % * Code is not optimized for speed.
 27 %
 28 % Date: 1 October 2013
 29 % Author: Marcus Baum (baum@engineer.uconn.edu)
 30 
 31 global LEFTINF RIGHTINF bounds;
 32 
 33 LEFTINF = -100000;
 34 RIGHTINF = 100000;
 35 
 36 if nargin ==0
 37     % example line arrangement
 38     E(1,:)= [0.5 0];
 39     E(2,:)= [1 5];
 40     E(3,:)= [-1 4];
 41     E(4,:)= [-5 8];
 42 end
 43 if nargin <2
 44     plotSweep= 2;
 45 end
 46 
 47 % sort lines according to slope
 48 [~, sortedpermu] =sort(E(:,1),'descend');
 49 E = E(sortedpermu,:);
 50 % add pseudo lines at beginning and end
 51 E = [0 0; E; 0 0];
 52 n =  size(E,1);
 53 
 54 % Initialization of data structures
 55 
 56 % HTU(i,j,k): segment on line i delimited by j and k
 57 % M(i): Line indices of current cut, from top to bottom
 58 % N(i,:): Left and right line indices that delimit the cut on line i
 59 % I: Stack of integers, where lines M(I(i)) and M(I(i)+1) have a common endpoint
 60 % cellChanges: Cell changes performed, only required for return parameter
 61 
 62 cellChanges = [];
 63 HTU = init_htu(E,n);
 64 HTL = init_htl(E,n);
 65 [N M I] = init_NMI(HTL,HTU,E,n);
 66 
 67 
 68 if plotSweep
 69     inter = calcIntersections(E,n);
 70     bounds.bounds_x = [min(inter(:,1 ))-1, max(inter(:,1 ))+1 ];
 71     bounds.bounds_y = [min(inter(:,2 ))-1, max(inter(:,2 ))+1];
 72     figure
 73     plotlines(E,n)
 74     hold on
 75     plot(inter(:,1),inter(:,2),'o')
 76 end
 77 
 78 
 79 % Main loop
 80 
 81 while ~isempty(I)
 82     
 83     % plotting  
 84     if plotSweep ==2
 85     h = plotCut(N,M,I,E,n);
 86     pause
 87     delete(h);
 88     h = plotHTU(HTU,E);
 89     pause
 90     delete(h)
 91     h = plotHTL(HTL,E);
 92     pause
 93     delete(h);
 94     end
 95     if plotSweep
 96       nexti = intersectLines(E(M(I(1)),:), E(M(I(1)+1),:));
 97       plot(nexti(:,1),nexti(:,2),'x','MarkerSize',10,'Color','r')
 98     end
 99     
100     cellChanges= [cellChanges; I(1)];  
101     
102     % update data structures
103     HTU = update_htu(E,n,HTU,M,N,I(1));
104     HTL = update_htl(E,n,HTL,M,N,I(1));
105     [N M I] = update_NMI(HTL,HTU,E,n,I(1),I,M,N);
106     
107 end
108 
109 
110 
111 function [N M I] = update_NMI(HTL,HTU,E,n,cI,I,M,N)
112 M([cI cI+1]) =  M([cI+1 cI]);
113 oldRight = N(M(cI),2) ;
114 oldRight2 = N(M(cI+1),2) ;
115 N(M(cI+1),1)=oldRight2;
116 N(M(cI),1)=oldRight;
117 I= I(2:end); 
118 for i = cI:cI+1
119     if (HTL(M(i),2) == 1 ||HTL(M(i),2) == n )
120         x1 = [RIGHTINF RIGHTINF]   ;
121     else
122         x1 = intersectLines(E(M(i),:),E(HTL(M(i),2),:));
123     end
124     
125     if (HTU(M(i),2) == 1 ||HTU(M(i),2) == n )
126         x2 = [RIGHTINF RIGHTINF]   ;
127     else
128         x2 = intersectLines(E(M(i),:),E(HTU(M(i),2),:));
129     end
130     
131     if x1(1)<x2(1)
132         N(M(i),2) = HTL(M(i),2);
133     else
134         N(M(i),2) = HTU(M(i),2) ;
135     end
136 end
137 
138 for i = cI-1:cI+1
139     if (HTL(M(i+1),2) == M(i)   &&   HTU(M(i),2)==M(i+1))
140         I = [i I];
141     end
142 end
143 end
144 
145 
146 function htu = update_htu(E,n,htu,M,N,I)
147 htu(M(I+1),1) = M(I);
148 htu(M(I),1) = M(I+1);
149 current = M(I+2);
150 while ( ~(current == 1)  &&(above(M(I), current, htu(current,2),E)  ))
151     current = htu(current,2);
152 end
153 htu(M(I),2) = current;
154 end
155 
156 
157 function htl = update_htl(E,n,htl,M,N,I)
158 htl(M(I+1),1) = M(I);
159 htl(M(I),1) = M(I+1);
160 current = M(I-1);
161 while ( ~(current==n || current==1)  && ((~above(M(I+1), current, htl(current,2),E)  )    ))
162     current = htl(current,2);
163 end
164 htl(M(I+1),2) = current;
165 end
166 
167 
168 function [N M I] = init_NMI(HTL,HTU,E,n)
169 M = n:-1:1;
170 I = [];
171  
172 for i = 2:n-1
173     if (HTL(i,2) == 1 ||HTL(i,2) == n )
174         x1 = [RIGHTINF RIGHTINF]   ;
175     else
176         x1 = intersectLines(E(i,:),E(HTL(i,2),:));
177     end
178     if (HTU(i,2) == 1 ||HTU(i,2) == n )
179         x2 = [RIGHTINF RIGHTINF]   ;
180     else
181         x2 = intersectLines(E(i,:),E(HTU(i,2),:));
182     end
183     
184     if (HTL(M(i+1),2) == M(i)   &&   HTU(M(i),2)==M(i+1))
185         I = [i I ];
186     end    
187     N(i,1)=LEFTINF;
188     if x1(1) <x2(1)
189         N(i,2) = HTL(i,2);
190     else
191         N(i,2) = HTU(i,2) ;
192     end
193 end
194 end
195 
196 
197 function htu = init_htu(E,n)
198 htu(1,1)= LEFTINF;
199 htu(1,2)= RIGHTINF;
200 htu(n,1)= LEFTINF;
201 htu(n,2)= RIGHTINF;
202 htu(2,1)= LEFTINF;
203 htu(2,2)= 1;
204 for i = 3:n-1
205     htu(i,1)= LEFTINF;
206     current = i-1;
207     while ( ~(current == 1)  &&(above(i, current, htu(current,2),E)  ))
208         current = htu(current,2);
209     end
210     htu(i,2) = current;
211 end
212 end
213 
214 
215 function htl = init_htl(E,n)
216 htl(n,1)= LEFTINF;
217 htl(n,2)= RIGHTINF;
218 htl(1,1)= LEFTINF;
219 htl(1,2)= RIGHTINF;
220 htl(n-1,1)= LEFTINF;
221 htl(n-1,2)= n;
222 for i = n-2:-1:2
223     htl(i,1)= LEFTINF;
224     current = i+1;
225     while ( ~(current == n)  &&(~above(i, current, htl(current,2),E)  ))
226         current = htl(current,2);
227     end
228     htl(i,2) = current;
229 end
230 end
231 
232 
233 function r = above(b,i,j,E)
234 n = size(E,1);
235 if ( j==n|| j==1)
236     if E(b,1)>E(i,1)
237         r =1;
238     else
239         r=0;
240     end
241     return;
242 end
243 inters = intersectLines(E(i,:),E(j,:));
244 bir = E(b,1)*inters(1)+E(b,2);
245 r =(bir-inters(2)>0);
246 end
247 
248 
249 function r = intersectLines(a,b)
250 x= (b(2) - a(2))/ (a(1)-b(1));
251 r = [x a(1)*x+a(2)];
252 end
253 
254 
255 
256 
257 % Methods for plotting
258 
259 function inter =  calcIntersections(E,n)
260 inter = [];
261 for i = 2:n-1
262     for j=2:n-1
263         if ~(i==j)
264             inter = [inter ;intersectLines(E(i,:), E(j,:))];
265         end
266         
267     end
268 end
269 end
270 
271 
272 function h =plotCut(N,M,I,E,n)
273 h=[];
274 for i = 2:n-1
275      h = [h plotlineSegment(M(i),N(M(i),1),N(M(i),2) ,E,'m')];
276     hold on
277 end
278 
279 for i=1:length(I)
280     inter = intersectLines(E(M(I(i)),:),E(N(M(I(i)),2),:));
281     h = [h plot(inter(:,1),inter(:,2),'x','Color','r','MarkerSize',20)];
282 end
283 end
284 
285 
286 function plotlines(E,n)
287 for i = 2:n-1
288     ev = [bounds.bounds_x(1) bounds.bounds_x(2)];
289     plot(ev,E(i,1) * ev+E(i,2) );
290     text(0, E(i,2)+0.2 ,int2str(i))
291     hold on
292 end
293 end
294 
295 
296 function h = plotHTU(HTU,E)
297 n = size(HTU,1);
298 h = [];
299 for i = 2:n-1
300     h = [h plotlineSegment(i,HTU(i,1), HTU(i,2),E)];
301     hold on
302 end
303 end
304 
305 
306 function h = plotHTL(HTL,E)
307 n = size(HTL,1);
308 h = [];
309 for i = 2:n-1
310     h = [h plotlineSegment(i,HTL(i,1), HTL(i,2),E,'g')];
311     hold on
312 end
313 end
314 
315 
316 function h = plotlineSegment(e1,e2,e3,E,c)
317 if nargin < 5
318     c = 'r';
319 end
320 n = size(E,1);
321 if e2 == LEFTINF
322     x1 = [bounds.bounds_x(1) (E(e1,1)*bounds.bounds_x(1)+E(e1,2))];
323 else
324     x1 = intersectLines(E(e1,:),E(e2,:));
325 end
326 
327 if ((e3 == RIGHTINF)  || (e3==1) || (e3==n))
328     x2 = [bounds.bounds_x(2) (E(e1,1)*bounds.bounds_x(2)+E(e1,2))];
329 else
330     x2 = intersectLines(E(e1,:),E(e3,:));
331 end
332 h = plot([x1(1),x2(1)],[x1(2),x2(2)] ,c );
333 hold on
334 end
335 
336 
337 end
Download algorithm (1 file) as ZIP

Comments

Please login to post a comment.