Optimize point-in-circle (geodesic) calc tracking results of previous results
Nobody has claimed this yet.
Assessment
- Difficulty
- 5/5
- Estimated time
- Over a week
- Newbie friendliness
- 25/100
- Issue type
- Refactor
- Clarity
- Needs clarification
- Activity status
- Stale
- Tech stack
- java
- Domain
- performance
Research direction
Start by reading the Circle shape relationship checks and the DistanceCalculator.withinDistance calls described in the issue. Measure whether the internal 45-degree rectangle improves geodesic performance before considering incremental inner and outer frontier tracking; any mutable shape state must have a thread-safety or API plan.
Written by the indexing model from the issue text.
Description
The Circle shape determines the relationship between another shape (notable a point or rectangle) with itself (e.g. Within, Disjoint, ...). To do this, usually needs to call DistanceCalculator.withinDistance(point, point, distance) one or more times. For the geodesic implementation, the distance calculation is somewhat expensive.
Milestone 1: An idea here is to first use the internal 45-degree rectangle to more quickly calculate if the point is within that. It's in effect an inner-box (versus an outer bounding box).
Milestone 2. If measurements show milestone 1 to be faster then proceed here. As withinDistance() needs to be called and returns true, expand the inner box creating a sort of inner convex hull polygon shape, starting with the 45-degree inner box from before. But don't track "too many" points. When withinDistance() returns false, an outer polygon frontier can be incrementally built similarly to the inside. To constrain the detail, for each quadrant of the circle, you might add no more than say 64 frontier points on each side. So that it's evenly distributed, you might furthermore limit points being added to a fixed 1/64th band per quadrant.
A problem with Milestone 2 is that it would make the shape mutable, to some extent. Some care would be needed to make it thread-safe or devise some other API approach.
- Dominant language
- Java
- Stars
- 961
- Forks
- 173
- PR merge metrics
- No merged PRs in 30d
Getting set up
- No Dockerfile or Docker Compose file
- No pull request template
- Read the contributing guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
More from locationtech/spatial4j
-
question
Difficulty 5/5 Over a week Newbie friendliness 20/100
locationtech/spatial4j#233 · 1 comment ·
-
bug
Difficulty 3/5 1-2 days Newbie friendliness 35/100
locationtech/spatial4j#232 · 1 comment ·
-
Difficulty 4/5 3-5 days Newbie friendliness 25/100
locationtech/spatial4j#231 · 1 comment ·
-
Difficulty 5/5 Over a week Newbie friendliness 25/100
locationtech/spatial4j#230 · 2 comments ·
-
bug
Difficulty 3/5 1-2 days Newbie friendliness 45/100
locationtech/spatial4j#227 · 2 comments ·
All issues in locationtech/spatial4j
Similar issues
-
Update license yearOpen0 - Backlog 1 - Ready documentation good first issue help wanted
Difficulty 2/5 1-3 hours Newbie friendliness 78/100
-
cbor
Difficulty 2/5 1-3 hours Newbie friendliness 84/100
FasterXML/jackson-dataformats-binary#844 ·
Maintainers usually reply within 1 day
-
Issue: Bug
Difficulty 2/5 1-3 hours Newbie friendliness 82/100
OpenAPITools/openapi-generator#25107 ·
Maintainers usually reply within 1 day
-
improvement
Difficulty 2/5 1-3 hours Newbie friendliness 78/100
apache/iceberg#18351 · 1 comment ·
Maintainers usually reply within 1 day
-
bug good first issue
Difficulty 2/5 1-3 hours Newbie friendliness 90/100
repowise-dev/repowise#2945 · 1 comment ·
Maintainers usually reply within 1 day