How to sweep like a Sir

Правка en19, от DanAlex, 2015-09-17 17:00:46

Cutting to the chase

Clearly you don't need a PhD in Computing to sweep in the yard , but one might be usefull in order to know linear and radial sweep algorithm. So , what's all about ? It's just what it sounds it is , sweeping linear ( up to down , for example ) or radial ( making a 360 degrees loop ).

How this can help ? Well...

Linear sweep

Suppose you a set of objects in an Euclidean plane. We need to extract information about some objects. The method of linear sweeping takes a line and moves it on a fixed direction. Usually the line taken would be vertical and the direction would be left to right or up to down.

Quite abstract for the moment , huh ? Let's go to a more specific example.

Rectangle union area

This example is well known. You have a set of rectangles with edges parallel to the OX and OY axes. What is their union area.

Well , first of all , let's take a particular case in order to achieve a different perspective. Let's suppose the lower edges are fixed on the OX axis. This would lead us to the following case :

Now let's take a look at the property we established. The property fixes the lower edge. So the only edge we are interested in is the upper edge. The other two will be united by the point projections of the ends of the edge. For example D and C will be projected in B and A. Furthermore , these edges are useless in our problem so we will take into acount only the upper edges.

Now as we established that the sweep can go. We will "move" an imaginary line from left to right. As we meet a left corner of the segment we should take it into account for the moment. When we reach it's end it should not be considered any more. On a space between two sweep lines we take all the active segments and memorise the bigest Y. The area added would be maxY * length between sweep lines.

The only remaining question is how we move the imaginary line ? Sorting , of course.

Now let's summarise. We devide each segment in two tipes of querys : in ( a segment is active ) and out ( a segment becomes unactive ). Sort the querys increasingly by X coordinate and for each two consecutive sweep lines take the maximum Y out of the active sweep lines. We can easyly do that with a priority queue. Therefore , the complexity would be O(N log N).

To be sure we understood all , let's look again at the example. The querys will be : in(D) , in(F) , out(C) , out(G) , in(J) , out(K). On interval DF' we have one active segment , therefore maxY = 2. On interval F'C we have two active segments , maxY = 3 from FG segment. On interval CG , maxY = 3 and finally on interval JK , maxY = 5. Total area is 3*2 + 1*3 + 4*3 + 1*5 = 26. Easy.

Radial sweep

Basically , it would go like that:

Теги geometry, sort, segment tree, line sweep

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en46 Английский DanAlex 2019-01-19 14:21:07 13 Tiny change: 's can help ? Well... [cut]\n\n### Li' -> 's can help? Well... [cut] \n\n### Li'
en45 Английский DanAlex 2016-02-07 15:40:27 6 Tiny change: ' ? Well...\n\n### Li' -> ' ? Well... [cut]\n\n### Li'
en44 Английский DanAlex 2015-09-18 18:43:14 8
en43 Английский DanAlex 2015-09-18 18:42:18 338
en42 Английский DanAlex 2015-09-18 11:56:57 71
en41 Английский DanAlex 2015-09-18 08:36:50 108
en40 Английский DanAlex 2015-09-18 08:21:59 0 (published)
en39 Английский DanAlex 2015-09-18 08:21:41 74 (saved to drafts)
en38 Английский DanAlex 2015-09-18 08:16:05 162
en37 Английский DanAlex 2015-09-17 22:22:11 12 Tiny change: 'he sweep abordation. \n\n####' -> 'he sweep approach. \n\n####'
en36 Английский DanAlex 2015-09-17 22:17:36 15 Tiny change: 'rmine the minimum radius circle of' -> 'rmine the circle of'
en35 Английский DanAlex 2015-09-17 19:22:50 28
en34 Английский DanAlex 2015-09-17 18:56:11 2 Tiny change: '\n#### [Bouns](https:/' -> '\n#### [Bonus](https:/'
en33 Английский DanAlex 2015-09-17 18:55:36 0 (published)
en32 Английский DanAlex 2015-09-17 18:55:28 5 Tiny change: 'le how to a point w' -> 'le how to find a point w'
en31 Английский DanAlex 2015-09-17 18:52:44 7 Tiny change: 'he points on the that can ' -> 'he points that can ' (saved to drafts)
en30 Английский DanAlex 2015-09-17 18:35:08 50
en29 Английский DanAlex 2015-09-17 18:31:25 172 (published)
en28 Английский DanAlex 2015-09-17 18:28:57 33
en27 Английский DanAlex 2015-09-17 18:26:07 1 Tiny change: ' algorithm. So , wha' -> ' algorithms. So , wha'
en26 Английский DanAlex 2015-09-17 18:23:50 45
en25 Английский DanAlex 2015-09-17 18:21:17 1085
en24 Английский DanAlex 2015-09-17 18:07:35 343
en23 Английский DanAlex 2015-09-17 17:45:20 1926
en22 Английский DanAlex 2015-09-17 17:13:20 48
en21 Английский DanAlex 2015-09-17 17:12:35 4
en20 Английский DanAlex 2015-09-17 17:12:15 954
en19 Английский DanAlex 2015-09-17 17:00:46 848
en18 Английский DanAlex 2015-09-17 16:49:04 789
en17 Английский DanAlex 2015-09-17 16:38:44 70
en16 Английский DanAlex 2015-09-17 16:37:50 138
en15 Английский DanAlex 2015-09-17 16:13:58 532
en14 Английский DanAlex 2015-09-17 16:06:55 14
en13 Английский DanAlex 2015-09-17 16:05:42 2 Tiny change: 'down. \n\n[](https://' -> 'down. \n\n![ ](https://'
en12 Английский DanAlex 2015-09-17 16:05:22 364
en11 Английский DanAlex 2015-09-17 16:00:12 12
en10 Английский DanAlex 2015-09-17 15:58:09 59
en9 Английский DanAlex 2015-09-17 15:55:42 38 Reverted to en7
en8 Английский DanAlex 2015-09-17 15:54:34 38 Reverted to en6
en7 Английский DanAlex 2015-09-17 15:53:14 38 Reverted to en5
en6 Английский DanAlex 2015-09-17 15:52:30 38
en5 Английский DanAlex 2015-09-17 15:48:06 464
en4 Английский DanAlex 2015-09-17 15:43:02 76
en3 Английский DanAlex 2015-09-17 15:41:49 0 Tiny change: 'ation1.gif)' -> 'ation1.gif'
en2 Английский DanAlex 2015-09-17 15:39:01 784
en1 Английский DanAlex 2015-09-17 15:37:44 935 Initial revision (saved to drafts)