10000 GitHub - bzadorozhnyi/circles-packing
[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to content

bzadorozhnyi/circles-packing

BranchesTags

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

83 Commits
src
src
 
 
.gitignore
.gitignore
 
 
Cargo.lock
Cargo.lock
 
 
Cargo.toml
Cargo.toml
 
 
README.md
README.md
 
 
circle.png
circle.png
 
 

Repository files navigation

Code for science research work

Important

This is my bachelor's thesis code for "PROBLEM OF OPTIMAL PACKING OF UNEVEN CIRCLES AND APPROACHES TO ITS SOLUTION."

Condition

A set of small circles needed to be packed into a circle and placed in $(0, 0)$ so that any circles would not overlap and would be inside the main (the biggest) circle. The program finds one of the local minima of the problem of packing circles into a circle of the minimum radius.

$$ \begin{cases} (x_i-x_j)^2 + (y_i-y_j)^2 \ge (r_i+r_j)^2, &&\forall i,j (i \ne j) \\ x_i^2+y_i^2 \le (R - r_i)^2, &&\forall i \\ \end{cases} $$

$$ R \to \min $$

Where $(x_i, y_i)$ is the coordinate of the given circle's center, $r_i$ - radius (same for $j$), $R$ - radius of the main circle.

Code usage

There are several different strategies for finding local answers:

  • heuristic algorithm
  • heuristic algorithm + r-algorithm
  • start point random generation + r-algorithm

A big part of the code has been used to evaluate test sets (input folder) and compare them with existing results (output folder). To run code for some cases - check out codes in the evaluate folder.

Note

no input and output folders in the repository. Check the code in the evaluate folder to know the structure of input and output files.

Example of results

About

No description, website, or topics provided.

Resources

Readme
Activity

Stars

1 star

Watchers

1 watching

Forks

0 forks
Report repository

Releases

No releases published

Packages

No packages published

Languages
0