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.

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

Implement binary search for VPolygon support vector #40

Closed
mforets opened this issue Nov 20, 2017 · 1 comment · Fixed by #1475
Closed

Implement binary search for VPolygon support vector #40

mforets opened this issue Nov 20, 2017 · 1 comment · Fixed by #1475
Assignees
Labels
good first issue 🐤 Good for newcomers performance 🐎 More efficient code

Comments

@mforets
Copy link
Member

mforets commented Nov 20, 2017

In #13 we implemented a O(n) algorithm to compute the support vector of a VPolygon. Since the vertices are sorted in CCW fashion by construction, we can do better than that using a binary search, see references below.


  • extreme points in convex polygons in the geomalgorithms site
  • Joseph O'Rourke, Computational Geometry in C (2nd Edition), Sect 7.9 "Extreme Point of Convex Polygon" (1998).
@mforets mforets added the performance 🐎 More efficient code label Nov 20, 2017
@schillic schillic assigned schillic and unassigned schillic Jul 11, 2018
@schillic schillic changed the title Implement binary search for VPolygon support function Implement binary search for VPolygon support vector Mar 17, 2019
@schillic
Copy link
Member

schillic commented Mar 17, 2019

Since the vertices are sorted, it should be sufficient to compare a vertex to its neighbors to detect that a maximizing vertex has been found. This optimization scheme is convex, i.e., local extrema are global extrema (however, there can be plateaus).

@schillic schillic added the good first issue 🐤 Good for newcomers label May 23, 2019
mforets pushed a commit that referenced this issue Jul 20, 2019
* add binary search for VPolygon support vector

* wrap binary and brute force code in new functions

* add N<:Real

* move inlined functions

* Update src/VPolygon.jl

Co-Authored-By: Christian Schilling <schillic@informatik.uni-freiburg.de>

* Update src/VPolygon.jl

Co-Authored-By: Christian Schilling <schillic@informatik.uni-freiburg.de>

* Update src/VPolygon.jl

Co-Authored-By: Christian Schilling <schillic@informatik.uni-freiburg.de>

* Update binary search

* fix inline functions

* update minkowski sum

* solve merge error

* Update src/Arrays/vector_operations.jl

Co-Authored-By: Christian Schilling <schillic@informatik.uni-freiburg.de>

* Update src/Arrays/vector_operations.jl

Co-Authored-By: Christian Schilling <schillic@informatik.uni-freiburg.de>

* Update src/VPolygon.jl

Co-Authored-By: Christian Schilling <schillic@informatik.uni-freiburg.de>

* Update src/VPolygon.jl

Co-Authored-By: Christian Schilling <schillic@informatik.uni-freiburg.de>

* solve problem in minkowski sum

* Update src/VPolygon.jl

Co-Authored-By: Christian Schilling <schillic@informatik.uni-freiburg.de>

* rotate hexadecagon

* rename variables in minkowski sum function

* export inline functions

* fix problem in unit test

* solve critical error in binary search and tests

* fix unit test

* add docs for inline functions

* fix comments and minkowski sum

* Update src/Arrays/vector_operations.jl

Co-Authored-By: Christian Schilling <schillic@informatik.uni-freiburg.de>

* Update src/Arrays/vector_operations.jl

Co-Authored-By: Christian Schilling <schillic@informatik.uni-freiburg.de>

* Update src/Arrays/vector_operations.jl

Co-Authored-By: Christian Schilling <schillic@informatik.uni-freiburg.de>

* Update src/Arrays/vector_operations.jl

Co-Authored-By: Christian Schilling <schillic@informatik.uni-freiburg.de>

* Update src/Arrays/vector_operations.jl

Co-Authored-By: Christian Schilling <schillic@informatik.uni-freiburg.de>

* Update src/Arrays/vector_operations.jl

Co-Authored-By: Christian Schilling <schillic@informatik.uni-freiburg.de>

* Update src/VPolygon.jl

Co-Authored-By: Christian Schilling <schillic@informatik.uni-freiburg.de>

* Update src/VPolygon.jl

Co-Authored-By: Christian Schilling <schillic@informatik.uni-freiburg.de>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
good first issue 🐤 Good for newcomers performance 🐎 More efficient code
Projects
None yet
Development

Successfully merging a pull request may close this issue.

3 participants