How to sweep like a Sir

Правка en15, от DanAlex, 2015-09-17 16:13:58

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 :

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)