algorithm - Number of areas overlapped by exactly 3 circles -

-

i have task have number of circles. know 1 centre , radius. need find number of areas overlapped exactly 3 circles. tried solve knowing circles overlap when distance between centres shorter sum of radiuses, got me nowhere.

a sweep-line algorithm should job.

read sweep-line algorithms in general here, 1 particular (very important) algorithm here. overall structure of algorithm problem similar of bentley–ottmann algorithm. below details (not full description rather sketch; full description

take leftmost (min x) , rightmost (max x) points on each circle. sort these points x coordinate. put them priority queue.

run vertical sweep line along x axis. line contains collection of y coordinates of points intersects circles @ current x coordinate, sorted y.

once sweep line hits leftmost circle point, add the collection twice — once upper semicircle , once lower semicircle. once sweep line hits rightmost circle point, remove corresponding points collection. keep track of number of times each interval between 2 successive points covered circles. keep track of identity of these areas. whenever 2 points belong different circles appear next each other, calculate intersection points, , insert them point queue. every time sweep line hits intersection point, swap corresponding points in collection , adjust area identities , overlap counts.

it's easy visualise algorithm drawing circles on piece of paper, coloring each area differently, , moving ruler across drawing, noting how intersects circles , areas.

also google "line sweep algorithm" "circles".


Comments

Post a Comment

Popular posts from this blog

php - How to display all orders for a single product showing the most recent first? Woocommerce -

-
i have password protected page on frontend. on page, want display full list of purchases associated single woocommerce product id. option 1: i've looked through woocommerce docs , , found: wc_cli_order , list_( $args, $assoc_args ) function lists orders. presumably, orders can filtered product id [--=] filter orders based on order property. line item fields (numeric array, started index zero): line_items.0.product_id option 2: i found article , based on customer id. i've modified code based on guesses meta_key , meta_value. $customer_orders = get_posts( array( 'numberposts' => -1, 'meta_key' => '_product', 'meta_value' => get_product_id(), 'post_type' => wc_get_order_types(), 'post_status' => array_keys( wc_get_order_statuses() ), ) ); how display orders single product showing recent order first? here solution put based on these articles: http://www.w...
Read more

asp.net - How to correctly use QUERY_STRING in ISAPI rewrite? -

-
i'm having difficult time , hope guys can help. using helicon isapi rewrite version 3.1.0.104 on our iis server. edit http.conf file , have tried , still fail. this trying do: redirect url: https://www.domain.com/switch-by-version?version=2.8.5.2594 to: https://test.domain.com/load/load.aspx?tver=2.8.5.2594 the version number @ end source url change, , need target url have same version number @ end of url example above shows. i tried following not work: rewritecond %{query_string} ^version=(\d\d?)\.(\d\d?)\.(\d\d?)\.(.*)$ [nc] rewriterule ^/switch-by-version(.*)$ https://test.domain.com/load/load.aspx?tver=%1 [r=307,nc,l] any appreciated! thanks. if it's running in equivalent context of .htaccess , rule shouldn't start / . here's simpler version: rewritecond %{query_string} ^version=(\d+\.\d+\.\d+(?:\..+)?)$ [nc] rewriterule ^switch-by-version/?$ https://test.domain.com/load/load.aspx?tver=%1 [r=307,nc,l]
Read more

angularjs - How restrict admin panel using in backend laravel and admin panel on angular? -

-
https://scotch.io/tutorials/token-based-authentication-for-angularjs-and-laravel-apps following tutorials, try write authentication restrict admin panel, didn't understood how can that. this admin panel, admin panel don't want show , request database unauthenticated users. my laravel-routes route::get('/admin',function(){ return view('index'); }); route::get('/api/v1/employees/{id?}', 'employees@index'); route::get('/api/v1/users/{id?}', 'employees@users'); route::post('/api/v1/employees', 'employees@store'); route::post('/api/v1/employees/{id}', 'employees@update'); route::delete('/api/v1/employees/{id}', 'employees@destroy'); route::group(['prefix' => 'api'], function() { route::resource('authenticate', 'authenticatecontroller', ['only' => ['index']]); route::post('authenticate', 'authentic...
Read more