Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Make circle drawing more scalable #33

Open
wants to merge 2 commits into
base: master
Choose a base branch
from
Open

Make circle drawing more scalable #33

wants to merge 2 commits into from

Conversation

albinahlback
Copy link
Contributor

@albinahlback albinahlback commented Jan 14, 2021 •
edited
Loading

By usage of trigonometric function, I was able to reduce the computational complexity of the algorithm from O(r^2) to O(r). Further note the lack of if statements within the for loops.

Note that some smaller circles (r ~= 2), the appearance is somewhat wierd. Maybe someone can see if one should use ceil or floor instead of round. However, I think this is worth the performance gain.

Resolves #7

@albinahlback
Make circle drawing more scalable
9f742e3 
By usage of trigonometric function, I was able to reduce the
computational complexity of the algorithm from O(r^2) to O(r).
@aviks
Copy link
Owner

aviks commented Jan 15, 2021

Thanks for this. I presume you have seen #13 to check the history of this code?

Can you provide some screenshots with the new algorithm for different sizes of circles, as well as some timings for the old and new code?

@albinahlback
Copy link
Contributor Author

I added the testfile in test/. Here's the result, which clearly proves that this way is faster:

# Starting julia

julia> include("circleperformance.jl")
testnew (generic function with 1 method)

# Running every test, so everything gets compiled before timing

julia> ren = myinit()
Ptr{SimpleDirectMediaLayer.Renderer} @0x0000000004768490

julia> @time testold(ren, circles, 1000, false)
  1.325373 seconds

julia> ren = myinit()
Ptr{SimpleDirectMediaLayer.Renderer} @0x0000000004bfd2d0

julia> @time testold(ren, circles, 1000, true)
  2.234989 seconds

julia> ren = myinit()
Ptr{SimpleDirectMediaLayer.Renderer} @0x000000006cdce890

julia> @time testnew(ren, circles, 1000, false)
  0.898482 seconds (40.00 k allocations: 3.662 MiB)

julia> ren = myinit()
Ptr{SimpleDirectMediaLayer.Renderer} @0x000000006cd6e8a0

julia> @time testnew(ren, circles, 1000, true)
  0.596087 seconds (40.00 k allocations: 3.662 MiB)

@albinahlback
Copy link
Contributor Author

circles
The first sequence of circles on the left have the radius 1 to 7. The ones to the right have the radius 49 to 81.

As you can see, the smaller ones have a somewhat odd shape. But in my opinion, this is fine when considering that the code is smaller and faster.

@albinahlback albinahlback mentioned this pull request Jan 16, 2021
Open
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers
No reviews
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.

Better circle drawing algorithm
2 participants
@albinahlback @aviks