[jira] [Commented] (GEOMETRY-146) PointSet/Map closest points
[
https://issues.apache.org/jira/browse/GEOMETRY-146?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17530318#comment-17530318
]
Matt Juntunen commented on GEOMETRY-146:
Merged in ffc9ff964654948aab93438dff8b8a2bbdab03d7
> PointSet/Map closest points
> ---
>
> Key: GEOMETRY-146
> URL: https://issues.apache.org/jira/browse/GEOMETRY-146
> Project: Commons Geometry
> Issue Type: New Feature
>Reporter: Matt Juntunen
>Priority: Major
> Fix For: 1.1
>
>
> Add methods to the new {{PointSet}} and {{PointMap}} interfaces to allow
> querying of points in order of distance from a query point.
> {code:java}
> PointSet {
> // find the closest point to pt or null if empty
> P closest(P pt);
> // iterate through points in order, with points closest to pt coming first
> Iterable closestFirst(P pt);
> // find the farthest point from pt or null if emtpy
> P farthest(P pt);
> // iterate through point in order, with points farthest from pt coming
> first
> Iterable farthestFirst(P pt);
> }
> {code}
> {{PointMap}} should have similar methods providing access to the map keys and
> entries.
--
This message was sent by Atlassian Jira
(v8.20.7#820007)
[jira] [Commented] (GEOMETRY-146) PointSet/Map closest points
[
https://issues.apache.org/jira/browse/GEOMETRY-146?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17529908#comment-17529908
]
Matt Juntunen commented on GEOMETRY-146:
I'm planning on merging the above PR either today or tomorrow unless there are
any objections.
> PointSet/Map closest points
> ---
>
> Key: GEOMETRY-146
> URL: https://issues.apache.org/jira/browse/GEOMETRY-146
> Project: Commons Geometry
> Issue Type: New Feature
>Reporter: Matt Juntunen
>Priority: Major
> Fix For: 1.1
>
>
> Add methods to the new {{PointSet}} and {{PointMap}} interfaces to allow
> querying of points in order of distance from a query point.
> {code:java}
> PointSet {
> // find the closest point to pt or null if empty
> P closest(P pt);
> // iterate through points in order, with points closest to pt coming first
> Iterable closestFirst(P pt);
> // find the farthest point from pt or null if emtpy
> P farthest(P pt);
> // iterate through point in order, with points farthest from pt coming
> first
> Iterable farthestFirst(P pt);
> }
> {code}
> {{PointMap}} should have similar methods providing access to the map keys and
> entries.
--
This message was sent by Atlassian Jira
(v8.20.7#820007)
[jira] [Commented] (GEOMETRY-146) PointSet/Map closest points
[
https://issues.apache.org/jira/browse/GEOMETRY-146?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17527268#comment-17527268
]
Matt Juntunen commented on GEOMETRY-146:
{{neighborEntriesFullBaseline}} was a baseline comparison method that simply
iterated through the _entire_ map and pulled out the ones that were within the
max distance. It was basically like this:
{code:java}
Vector3D refPt = ...
double maxDist = ...
List> neighbors = new ArrayList<>();
for (Entry entry : map.entrySet()) {
if (entry.getKey().distance(refPt) <= maxDist) {
neighbors.add(entry);
}
}
{code}
No optimizations or anything. I was completely dumbfounded that this was faster
than anything else but I was unable to see anything wrong with the tests. The
tests above are with maps with about ~8000 entries. The main culprit I could
see was the use of streams vs raw iterators. For example, {{neighborEntries}}
and {{neighborEntriesFullStreamBaseline}} use streams.
> PointSet/Map closest points
> ---
>
> Key: GEOMETRY-146
> URL: https://issues.apache.org/jira/browse/GEOMETRY-146
> Project: Commons Geometry
> Issue Type: New Feature
>Reporter: Matt Juntunen
>Priority: Major
> Fix For: 1.1
>
>
> Add methods to the new {{PointSet}} and {{PointMap}} interfaces to allow
> querying of points in order of distance from a query point.
> {code:java}
> PointSet {
> // find the closest point to pt or null if empty
> P closest(P pt);
> // iterate through points in order, with points closest to pt coming first
> Iterable closestFirst(P pt);
> // find the farthest point from pt or null if emtpy
> P farthest(P pt);
> // iterate through point in order, with points farthest from pt coming
> first
> Iterable farthestFirst(P pt);
> }
> {code}
> {{PointMap}} should have similar methods providing access to the map keys and
> entries.
--
This message was sent by Atlassian Jira
(v8.20.7#820007)
[jira] [Commented] (GEOMETRY-146) PointSet/Map closest points
[
https://issues.apache.org/jira/browse/GEOMETRY-146?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17527251#comment-17527251
]
Gilles Sadowski commented on GEOMETRY-146:
--
I don't understand {{neighborEntriesFullBaseline}}: Isn't it the fastest method?
> PointSet/Map closest points
> ---
>
> Key: GEOMETRY-146
> URL: https://issues.apache.org/jira/browse/GEOMETRY-146
> Project: Commons Geometry
> Issue Type: New Feature
>Reporter: Matt Juntunen
>Priority: Major
> Fix For: 1.1
>
>
> Add methods to the new {{PointSet}} and {{PointMap}} interfaces to allow
> querying of points in order of distance from a query point.
> {code:java}
> PointSet {
> // find the closest point to pt or null if empty
> P closest(P pt);
> // iterate through points in order, with points closest to pt coming first
> Iterable closestFirst(P pt);
> // find the farthest point from pt or null if emtpy
> P farthest(P pt);
> // iterate through point in order, with points farthest from pt coming
> first
> Iterable farthestFirst(P pt);
> }
> {code}
> {{PointMap}} should have similar methods providing access to the map keys and
> entries.
--
This message was sent by Atlassian Jira
(v8.20.7#820007)
[jira] [Commented] (GEOMETRY-146) PointSet/Map closest points
[
https://issues.apache.org/jira/browse/GEOMETRY-146?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17526835#comment-17526835
]
Matt Juntunen commented on GEOMETRY-146:
PR is in: https://github.com/apache/commons-geometry/pull/195
> PointSet/Map closest points
> ---
>
> Key: GEOMETRY-146
> URL: https://issues.apache.org/jira/browse/GEOMETRY-146
> Project: Commons Geometry
> Issue Type: New Feature
>Reporter: Matt Juntunen
>Priority: Major
> Fix For: 1.1
>
>
> Add methods to the new {{PointSet}} and {{PointMap}} interfaces to allow
> querying of points in order of distance from a query point.
> {code:java}
> PointSet {
> // find the closest point to pt or null if empty
> P closest(P pt);
> // iterate through points in order, with points closest to pt coming first
> Iterable closestFirst(P pt);
> // find the farthest point from pt or null if emtpy
> P farthest(P pt);
> // iterate through point in order, with points farthest from pt coming
> first
> Iterable farthestFirst(P pt);
> }
> {code}
> {{PointMap}} should have similar methods providing access to the map keys and
> entries.
--
This message was sent by Atlassian Jira
(v8.20.7#820007)
[jira] [Commented] (GEOMETRY-146) PointSet/Map closest points
[
https://issues.apache.org/jira/browse/GEOMETRY-146?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17526158#comment-17526158
]
Matt Juntunen commented on GEOMETRY-146:
It turns out that my instincts on the performance of {{neighborEntries}} were
incorrect and I am not able to find a performance boost over just using
{{nearToFar}} or even just iterating through the entire map. Below are the JMH
results for the best implementation I could come up with.
||Benchmark||(dist)||(randomSeed)||(shape)||Mode||Cnt||Score||Error||Units||
|neighborEntries|random|1|block|avgt|5|18078272.739|± 2855877.430|ns/op|
|neighborEntriesFullBaseline|random|1|block|avgt|5|3953413.160|±
1299435.732|ns/op|
|neighborEntriesFullStreamBaseline|random|1|block|avgt|5|19190180.574|±
3775274.018|ns/op|
|neighborEntriesNearToFarBaseline|random|1|block|avgt|5|13143387.077|±
2344194.490|ns/op|
|neighborEntryIterable|random|1|block|avgt|5|15025352.786|± 3978281.128|ns/op|
- {{neighborEntries}} - supposedly "optimized" method
- {{neighborEntriesFullBaseline}} - iterating through the entire map and
checking the distance for each entry
- {{neighborEntriesFullStreamBaseline}} - filtering a stream over the map entry
set
- {{neighborEntriesNearToFarBaseline}} - iterating over the {{nearToFar}}
collection and breaking out of the loop when the max distance is passed
- {{neighborEntryIterable}} - iterator version of {{neighborEntries}}
Based on these results, I'm going to remove {{neighborEntries}} from the API.
There isn't a performance boost and the functionality can be implemented in
terms of the other methods.
> PointSet/Map closest points
> ---
>
> Key: GEOMETRY-146
> URL: https://issues.apache.org/jira/browse/GEOMETRY-146
> Project: Commons Geometry
> Issue Type: New Feature
>Reporter: Matt Juntunen
>Priority: Major
> Fix For: 1.1
>
>
> Add methods to the new {{PointSet}} and {{PointMap}} interfaces to allow
> querying of points in order of distance from a query point.
> {code:java}
> PointSet {
> // find the closest point to pt or null if empty
> P closest(P pt);
> // iterate through points in order, with points closest to pt coming first
> Iterable closestFirst(P pt);
> // find the farthest point from pt or null if emtpy
> P farthest(P pt);
> // iterate through point in order, with points farthest from pt coming
> first
> Iterable farthestFirst(P pt);
> }
> {code}
> {{PointMap}} should have similar methods providing access to the map keys and
> entries.
--
This message was sent by Atlassian Jira
(v8.20.7#820007)
[jira] [Commented] (GEOMETRY-146) PointSet/Map closest points
[
https://issues.apache.org/jira/browse/GEOMETRY-146?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17520664#comment-17520664
]
Matt Juntunen commented on GEOMETRY-146:
It can certainly be implemented using {{nearToFar}}. However, I may be able to
get some more performance out of the current implementations if the ordering
requirement is removed. If not, I'll remove this method from the API.
> PointSet/Map closest points
> ---
>
> Key: GEOMETRY-146
> URL: https://issues.apache.org/jira/browse/GEOMETRY-146
> Project: Commons Geometry
> Issue Type: New Feature
>Reporter: Matt Juntunen
>Priority: Major
> Fix For: 1.1
>
>
> Add methods to the new {{PointSet}} and {{PointMap}} interfaces to allow
> querying of points in order of distance from a query point.
> {code:java}
> PointSet {
> // find the closest point to pt or null if empty
> P closest(P pt);
> // iterate through points in order, with points closest to pt coming first
> Iterable closestFirst(P pt);
> // find the farthest point from pt or null if emtpy
> P farthest(P pt);
> // iterate through point in order, with points farthest from pt coming
> first
> Iterable farthestFirst(P pt);
> }
> {code}
> {{PointMap}} should have similar methods providing access to the map keys and
> entries.
--
This message was sent by Atlassian Jira
(v8.20.1#820001)
[jira] [Commented] (GEOMETRY-146) PointSet/Map closest points
[
https://issues.apache.org/jira/browse/GEOMETRY-146?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17520567#comment-17520567
]
Gilles Sadowski commented on GEOMETRY-146:
--
Do you agree that
{code}
Stream> neighborEntries(P pt, double maxDist);
{code}
is not necessary?
> PointSet/Map closest points
> ---
>
> Key: GEOMETRY-146
> URL: https://issues.apache.org/jira/browse/GEOMETRY-146
> Project: Commons Geometry
> Issue Type: New Feature
>Reporter: Matt Juntunen
>Priority: Major
> Fix For: 1.1
>
>
> Add methods to the new {{PointSet}} and {{PointMap}} interfaces to allow
> querying of points in order of distance from a query point.
> {code:java}
> PointSet {
> // find the closest point to pt or null if empty
> P closest(P pt);
> // iterate through points in order, with points closest to pt coming first
> Iterable closestFirst(P pt);
> // find the farthest point from pt or null if emtpy
> P farthest(P pt);
> // iterate through point in order, with points farthest from pt coming
> first
> Iterable farthestFirst(P pt);
> }
> {code}
> {{PointMap}} should have similar methods providing access to the map keys and
> entries.
--
This message was sent by Atlassian Jira
(v8.20.1#820001)
[jira] [Commented] (GEOMETRY-146) PointSet/Map closest points
[
https://issues.apache.org/jira/browse/GEOMETRY-146?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17520505#comment-17520505
]
Matt Juntunen commented on GEOMETRY-146:
bq. Hmm, I thought that it was inefficient (requiring iterating in order to
copy all references to entries into the returned collection)
Full enumeration is only required if the size is not known ahead of time, as in
the case of returning a collection representing entries within a specified
radius. The return values from {{nearToFar}} and {{farToNear}} represent the
entire map/set so we already know the size. The collections are lazily
populated views of the map/set data and only store enough information to
determine the next element to return during iteration. (This is why {{List}}
would still be inefficient here, since it would require much more storage to
support access by index. Hence, it is left to the caller to convert to a
{{List}} if needed.)
bq. Otherwise, it is great; and, thus, why not have
Great! I'll start converting to this API.
> PointSet/Map closest points
> ---
>
> Key: GEOMETRY-146
> URL: https://issues.apache.org/jira/browse/GEOMETRY-146
> Project: Commons Geometry
> Issue Type: New Feature
>Reporter: Matt Juntunen
>Priority: Major
> Fix For: 1.1
>
>
> Add methods to the new {{PointSet}} and {{PointMap}} interfaces to allow
> querying of points in order of distance from a query point.
> {code:java}
> PointSet {
> // find the closest point to pt or null if empty
> P closest(P pt);
> // iterate through points in order, with points closest to pt coming first
> Iterable closestFirst(P pt);
> // find the farthest point from pt or null if emtpy
> P farthest(P pt);
> // iterate through point in order, with points farthest from pt coming
> first
> Iterable farthestFirst(P pt);
> }
> {code}
> {{PointMap}} should have similar methods providing access to the map keys and
> entries.
--
This message was sent by Atlassian Jira
(v8.20.1#820001)
[jira] [Commented] (GEOMETRY-146) PointSet/Map closest points
[
https://issues.apache.org/jira/browse/GEOMETRY-146?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17520168#comment-17520168
]
Gilles Sadowski commented on GEOMETRY-146:
--
{quote} * nearToFar and farToNear return Collection{quote}
Hmm, I thought that it was inefficient (requiring iterating in order to copy
all references to entries into the returned collection) (?).
Otherwise, it is great; and, thus, why not have
{code:java}
interface PointMap {
// ...
Collection> entriesNearToFar(P pt);
default List> neighborEntries(P pt, double maxDist) {
final List> nList = new ArrayList<>();
for (Entry e : entriesNearToFar(p)) {
if (distance(pt, e.key()) < maxDist) {
nList.put(e);
}
}
return nList;
}
}
{code}
?
> PointSet/Map closest points
> ---
>
> Key: GEOMETRY-146
> URL: https://issues.apache.org/jira/browse/GEOMETRY-146
> Project: Commons Geometry
> Issue Type: New Feature
>Reporter: Matt Juntunen
>Priority: Major
> Fix For: 1.1
>
>
> Add methods to the new {{PointSet}} and {{PointMap}} interfaces to allow
> querying of points in order of distance from a query point.
> {code:java}
> PointSet {
> // find the closest point to pt or null if empty
> P closest(P pt);
> // iterate through points in order, with points closest to pt coming first
> Iterable closestFirst(P pt);
> // find the farthest point from pt or null if emtpy
> P farthest(P pt);
> // iterate through point in order, with points farthest from pt coming
> first
> Iterable farthestFirst(P pt);
> }
> {code}
> {{PointMap}} should have similar methods providing access to the map keys and
> entries.
--
This message was sent by Atlassian Jira
(v8.20.1#820001)
[jira] [Commented] (GEOMETRY-146) PointSet/Map closest points
[
https://issues.apache.org/jira/browse/GEOMETRY-146?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17520056#comment-17520056
]
Matt Juntunen commented on GEOMETRY-146:
{quote}IOW, assuming "deep" access, can {{PointMap}} instantiate a {{List}}
view object that would *lazily* navigate the map's content?
{quote}
No, that is not feasible with the current implementations.
{quote}If the low-level API only provides navigation (in "natural"/near-to-far
and "reverse"/far-to-near ordering), wouldn't it be clearer to let any
additional filtering belong to a higher-level API
{quote}
Yes, that sounds like a good approach. Along those lines, what do you think of
the following simplified API?
{code:java}
interface PointSet {
// get the element nearest to pt
P nearest(P pt);
// get the element farthest from pt
P farthest(P pt);
// get all elements in order of nearest to farthest relative to pt
Collection nearToFar(P pt);
// get all elements in order of farthest to nearest relative to pt
Collection farToNear(P pt);
// get a stream containing all elements neighboring pt, i.e.
// within maxDist of pt; the points may be in any order
Stream neighbors(P pt, double maxDist);
}
// same methods as PointSet but with the words "entry"/"entries"
// added for consistency with other map methods
interface PointMap {
Entry nearestEntry(P pt);
Entry farthestEntry(P pt);
Collection> entriesNearToFar(P pt);
Collection> entriesFarToNear(P pt);
Stream> neighborEntries(P pt, double maxDist);
}
{code}
A few notes here:
- All iteration is internal to the implementing map/set.
- {{nearToFar}} and {{farToNear}} return {{Collection}} since the number of
elements is known (i.e. the Collection contains all of the elements in the
map/set). This lets us support access through both {{Iterable}} and {{Stream}}
without needing a new type like {{StreamingIterable}}.
- {{neighbors}} returns a {{Stream}} since the number of elements is not known
without enumerating all members (at least in the current implementations). The
elements may be returned in any order.
- {{nearest/farthest}} are present to allow optimized retrieval of single
values.
> PointSet/Map closest points
> ---
>
> Key: GEOMETRY-146
> URL: https://issues.apache.org/jira/browse/GEOMETRY-146
> Project: Commons Geometry
> Issue Type: New Feature
>Reporter: Matt Juntunen
>Priority: Major
> Fix For: 1.1
>
>
> Add methods to the new {{PointSet}} and {{PointMap}} interfaces to allow
> querying of points in order of distance from a query point.
> {code:java}
> PointSet {
> // find the closest point to pt or null if empty
> P closest(P pt);
> // iterate through points in order, with points closest to pt coming first
> Iterable closestFirst(P pt);
> // find the farthest point from pt or null if emtpy
> P farthest(P pt);
> // iterate through point in order, with points farthest from pt coming
> first
> Iterable farthestFirst(P pt);
> }
> {code}
> {{PointMap}} should have similar methods providing access to the map keys and
> entries.
--
This message was sent by Atlassian Jira
(v8.20.1#820001)
[jira] [Commented] (GEOMETRY-146) PointSet/Map closest points
[
https://issues.apache.org/jira/browse/GEOMETRY-146?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17519984#comment-17519984
]
Gilles Sadowski commented on GEOMETRY-146:
--
Yes, it summarizes the expectations, but I don't see that it does it
differently from the previous statements. ;)
Or perhaps it does clarify one of my so-called "inconsistency", by which I
rather meant a discrepancy between the assumed API (from the user's POV) and
the functionality required from any implementation in order to provide it.
IIUC, this is in line with your remark that
{quote}It would be unfortunate to impose this cost on callers who only care
about the actual points returned and not about their ordering.
{quote}
IOW, in this case, the ability to (efficiently) navigate the result set in
ascending/descending order is not an "implementation detail": It _must_ be
built into any {{{}PointMap{}}}; that's what I meant by "tightly coupled"
(whereas an independent {{DistanceOrdering}} interface makes it look like the
functionality could be achieved without "deep" access to the actual data
structure).
Hence have {{PointMap}} explicitly handle navigation (instead of delegating it
to {{DistanceOrdering}}).
{quote}StreamableIterator is returned instead of List for two reasons: [...]
{quote}
Sure; but my point was about the high-level API that represents a cloud of
points (i.e. coordinates + data) and how to select some of them (with any kind
of criteria, not only the "fixed radius" criterion), and _then_ sort them
according yet other criteria (which could be _outside_ this API if the "view"
_is-a_
[{{List}}|https://docs.oracle.com/javase/8/docs/api/java/util/Collections.html#sort-java.util.List-]).
IOW, assuming "deep" access, can {{PointMap}} instantiate a {{List}} view
object that would *lazily* navigate the map's content?
If that "easy API" is not possible, because of the constraints inherent to an
efficient implementation of the "cloud of points" concept, what's the benefit
of a {{DistanceOrdering}} interface wrt
{code:java}
public interface PointMap {
public Stream> stream();
public Stream> streamFrom(P point, boolean reverse);
}
{code}
?
If the low-level API only provides navigation (in "natural"/near-to-far and
"reverse"/far-to-near ordering), wouldn't it be clearer to let any additional
filtering belong to a higher-level API (which [Geometry] can provide too)
{code:java}
public class Utils {
public Iterable> selectWithinDistance(PointMap map,
P pt, double dist) {
final Stream> s = map.streamFrom(p);
// ...
}
}
{code}
?
> PointSet/Map closest points
> ---
>
> Key: GEOMETRY-146
> URL: https://issues.apache.org/jira/browse/GEOMETRY-146
> Project: Commons Geometry
> Issue Type: New Feature
>Reporter: Matt Juntunen
>Priority: Major
> Fix For: 1.1
>
>
> Add methods to the new {{PointSet}} and {{PointMap}} interfaces to allow
> querying of points in order of distance from a query point.
> {code:java}
> PointSet {
> // find the closest point to pt or null if empty
> P closest(P pt);
> // iterate through points in order, with points closest to pt coming first
> Iterable closestFirst(P pt);
> // find the farthest point from pt or null if emtpy
> P farthest(P pt);
> // iterate through point in order, with points farthest from pt coming
> first
> Iterable farthestFirst(P pt);
> }
> {code}
> {{PointMap}} should have similar methods providing access to the map keys and
> entries.
--
This message was sent by Atlassian Jira
(v8.20.1#820001)
[jira] [Commented] (GEOMETRY-146) PointSet/Map closest points
[
https://issues.apache.org/jira/browse/GEOMETRY-146?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17519970#comment-17519970
]
Matt Juntunen commented on GEOMETRY-146:
I've thought about it a bit more and I think I might see what you mean by an
inconsistency in the API. By returning {{DistanceOrdering}} from the
subset-selection methods we are assuming that the natural way to access
elements relative to a specific point or within a specific radius is by
increasing or decreasing distance. This is reasonable enough for the current
implementations, but what if this is not the case for future implementations?
What if an implementation incurs a large processing overhead in order to return
points in a specific distance ordering but can return them immediately when the
order does not matter. It would be unfortunate to impose this cost on callers
who only care about the actual points returned and not about their ordering. It
seems to me that we need an API that can perform the following:
- get the single nearest/farthest element from a given point and within an
optional search radius
- get elements in order of increasing or decreasing distance from a given point
and within an optional search radius
- get elements _in any order_ within a search radius of a specified point
Does this match what you're picturing?
> PointSet/Map closest points
> ---
>
> Key: GEOMETRY-146
> URL: https://issues.apache.org/jira/browse/GEOMETRY-146
> Project: Commons Geometry
> Issue Type: New Feature
>Reporter: Matt Juntunen
>Priority: Major
> Fix For: 1.1
>
>
> Add methods to the new {{PointSet}} and {{PointMap}} interfaces to allow
> querying of points in order of distance from a query point.
> {code:java}
> PointSet {
> // find the closest point to pt or null if empty
> P closest(P pt);
> // iterate through points in order, with points closest to pt coming first
> Iterable closestFirst(P pt);
> // find the farthest point from pt or null if emtpy
> P farthest(P pt);
> // iterate through point in order, with points farthest from pt coming
> first
> Iterable farthestFirst(P pt);
> }
> {code}
> {{PointMap}} should have similar methods providing access to the map keys and
> entries.
--
This message was sent by Atlassian Jira
(v8.20.1#820001)
[jira] [Commented] (GEOMETRY-146) PointSet/Map closest points
[
https://issues.apache.org/jira/browse/GEOMETRY-146?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17519968#comment-17519968
]
Matt Juntunen commented on GEOMETRY-146:
>From a previous response...
bq. You intentionally hid the internal implementation of PointMap, yet the
"near"/"far" methods make one assume that such an implementation must support
specific iteration "modes"; hence I'm feeling uncomfortable with the
(apparent?) inconsistency, at the "public" level.
Yes, I've made the _near/far_ concepts part of the {{PointMap/Set}} interfaces.
I don't see how this produces any inconsistency. The interfaces describe the
methods that must be available and it is up to the implementations on how they
accomplish that.
bq. For example, from your answers above, I seem to understand that PointMap
and DistanceOrdering are tightly coupled;
I wouldn't say they're "tightly coupled" since they are interfaces; more like
they are closely related.
bq. one wonders: "nearest"/farthest to what? The reference point is
"out-of-scope" (so to speak)...
Yes, intentionally so. The {{DistanceOrdering}} interface defines methods for
accessing a particular subset of the points. It does not answer the question of
what is selected. This is the separation of the _what_ and the _how_ that we
mentioned previously. I could easily picture using this interface in the future
for Euclidean 2D and 3D to access points in order of distance from a line. If
{{DistanceOrdering}} defined the target of the distance computation, this would
be more complicated.
bq. why not make the coupling obvious, as in
I don't see any added benefit in that API. Rather, it doesn't seem as
expressive or readable. Ex:
{code:java}
// I find this ...
Iterable> it = map.entriesFrom(pt).nearToFar();
// easier to read than this ...
Iterable> it = map.entries(pt, DistanceOrdering.ASCENDING);
{code}
bq. I'm also a bit wary of only returning a StreamableIterator interface rather
than e.g. a List, because in the potential use case which I have in mind, the
selected points are rather few (as compared to the map's contents) and the
number of them should be known in order to, for example, compute an
interpolation of the associated values.
{{StreamableIterator}} is returned instead of {{List}} for two reasons:
1. The total number of elements within the area of interest is generally not
known until all of the elements are enumerated. The main exception to this is
when the entire map/set is being iterated.
2. The list could be quite large so it should be up to the caller on whether or
not to incur the cost of allocation.
If a list is needed, it is a one-liner:
{{code:java}
List closePts = set.withinDistance(p,
dist).nearToFar().stream().collect(Collectors.toList());
{code}
> PointSet/Map closest points
> ---
>
> Key: GEOMETRY-146
> URL: https://issues.apache.org/jira/browse/GEOMETRY-146
> Project: Commons Geometry
> Issue Type: New Feature
>Reporter: Matt Juntunen
>Priority: Major
> Fix For: 1.1
>
>
> Add methods to the new {{PointSet}} and {{PointMap}} interfaces to allow
> querying of points in order of distance from a query point.
> {code:java}
> PointSet {
> // find the closest point to pt or null if empty
> P closest(P pt);
> // iterate through points in order, with points closest to pt coming first
> Iterable closestFirst(P pt);
> // find the farthest point from pt or null if emtpy
> P farthest(P pt);
> // iterate through point in order, with points farthest from pt coming
> first
> Iterable farthestFirst(P pt);
> }
> {code}
> {{PointMap}} should have similar methods providing access to the map keys and
> entries.
--
This message was sent by Atlassian Jira
(v8.20.1#820001)
[jira] [Commented] (GEOMETRY-146) PointSet/Map closest points
[
https://issues.apache.org/jira/browse/GEOMETRY-146?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17519582#comment-17519582
]
Gilles Sadowski commented on GEOMETRY-146:
--
{quote}It would be helpful to me if you could respond to my latest API proposal
from Mar 30. [...]
{quote}
I did comment:
{quote}You intentionally hid the internal implementation of PointMap, yet the
"near"/"far" methods make one assume that such an implementation must support
specific iteration "modes"; hence I'm feeling uncomfortable with the
(apparent?) inconsistency, at the "public" level. Sorry that I cannot convey
the feeling in a more concrete way at this moment...
{quote}
For example, from your answers above, I seem to understand that {{PointMap}}
and {{DistanceOrdering}} are tightly coupled; hence an independent interface
for the latter seems artificial: If one looks at
{code:java}
interface DistanceOrdering {
T nearest();
T farthest();
StreamingIterable nearToFar();
StreamingIterable farToNear();
}
{code}
one wonders: "nearest"/farthest to {*}what{*}? The reference point is
"out-of-scope" (so to speak)...
Rather than
{code:java}
interface PointMap {
DistanceOrdering> entriesFrom(P pt);
DistanceOrdering> entriesWithinRadius(P pt, double radius);
}
{code}
why not make the coupling obvious, as in
{code:java}
interface PointMap {
public enum DistanceOrdering {
ASCENDING,
DESCENDING
}
Iterable> entriesWithinRadius(P pt, double radius,
DistanceOrdering order);
default Iterable> entries(P pt, DistanceOrdering order) {
return entriesWithinRadius(pt, Double.POSITIVE_INFINITY, order);
}
}
{code}
?
I'm also a bit wary of only returning a {{StreamableIterator}} interface rather
than e.g. a {{{}List{}}}, because in the potential use case which I have in
mind, the selected points are rather few (as compared to the map's contents)
and the number of them should be known in order to, for example, compute an
interpolation of the associated values.
One can easily call
[{{stream()}}|https://docs.oracle.com/javase/8/docs/api/java/util/Collection.html#stream--]
on a {{{}Collection{}}}, but creating a {{Collection}} instance from a stream
is a bit more cumbersome, but also potentially less efficient, depending on the
whether the original data-structure has "privileged" access for creating the
{{Collection}} instance.
> PointSet/Map closest points
> ---
>
> Key: GEOMETRY-146
> URL: https://issues.apache.org/jira/browse/GEOMETRY-146
> Project: Commons Geometry
> Issue Type: New Feature
>Reporter: Matt Juntunen
>Priority: Major
> Fix For: 1.1
>
>
> Add methods to the new {{PointSet}} and {{PointMap}} interfaces to allow
> querying of points in order of distance from a query point.
> {code:java}
> PointSet {
> // find the closest point to pt or null if empty
> P closest(P pt);
> // iterate through points in order, with points closest to pt coming first
> Iterable closestFirst(P pt);
> // find the farthest point from pt or null if emtpy
> P farthest(P pt);
> // iterate through point in order, with points farthest from pt coming
> first
> Iterable farthestFirst(P pt);
> }
> {code}
> {{PointMap}} should have similar methods providing access to the map keys and
> entries.
--
This message was sent by Atlassian Jira
(v8.20.1#820001)
[jira] [Commented] (GEOMETRY-146) PointSet/Map closest points
[
https://issues.apache.org/jira/browse/GEOMETRY-146?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17519538#comment-17519538
]
Matt Juntunen commented on GEOMETRY-146:
{quote}From this assumption, I'd suggest that the class name reflects its
importance, similarly to the "Navigable" qualifier in the [JDK
{{NavigableMap}}|https://docs.oracle.com/javase/8/docs/api/java/util/NavigableMap.html].
{quote}
It is part of the class name: {{DistanceOrdering}}, which is returned from
several of the methods in my proposed API.
bq. In this case, there may be no reason; but we could imagine another selector
where some part of the computation is performed at instantiation and should not
be repeated for each point.
Yes. I would imagine a separate method in the API for that.
{quote}Could selectors be defined as
class PointMap {
public interface Selector extends Function, P> {};
}
?
{quote}
Do you mean
{code:java}
interface Selector extends Function> {}
{code}
?
In other words, the selector accepts a point and returns a {{PointMap}} view?
There are 2 issues with this:
- This presupposes that the only selection criteria to be used will be a point,
which may not be the case. For example, what if we wanted to select points with
a bounding box? That would not fit this interface.
- Returning another full {{PointMap}} instance as a view of the main map is not
feasible at this point. Doing so would be very complicated with the current
algorithms and I don't believe it would have much use either.
bq. Can the "sub-map" be a "view" of the same data-structure?
That's what I have implemented. {{DistanceOrdering}} is a view of the
underlying {{PointMap/Set}}. It is accessed through selection methods (e.g.
{{PointMap.entriesWithinDistance(P, double)}}), similar to {{Map.entrySet()}}.
{quote}
Given a point "p" of type P, are the 2 iterators (over all points in the
PointMap instance):
in increasing distance from "p"
in decreasing distance
"naturally" (efficiently) defined?
{quote}
Yes.
It would be helpful to me if you could respond to my latest API proposal from
Mar 30. I feel like this both meets some of the requirements that you are
mentioning as well as being similar to the approaches used in {{java.util.Map}}.
> PointSet/Map closest points
> ---
>
> Key: GEOMETRY-146
> URL: https://issues.apache.org/jira/browse/GEOMETRY-146
> Project: Commons Geometry
> Issue Type: New Feature
>Reporter: Matt Juntunen
>Priority: Major
> Fix For: 1.1
>
>
> Add methods to the new {{PointSet}} and {{PointMap}} interfaces to allow
> querying of points in order of distance from a query point.
> {code:java}
> PointSet {
> // find the closest point to pt or null if empty
> P closest(P pt);
> // iterate through points in order, with points closest to pt coming first
> Iterable closestFirst(P pt);
> // find the farthest point from pt or null if emtpy
> P farthest(P pt);
> // iterate through point in order, with points farthest from pt coming
> first
> Iterable farthestFirst(P pt);
> }
> {code}
> {{PointMap}} should have similar methods providing access to the map keys and
> entries.
--
This message was sent by Atlassian Jira
(v8.20.1#820001)
[jira] [Commented] (GEOMETRY-146) PointSet/Map closest points
[
https://issues.apache.org/jira/browse/GEOMETRY-146?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17516875#comment-17516875
]
Gilles Sadowski commented on GEOMETRY-146:
--
{quote}[...] near/far qualification is important enough to warrant inclusion in
the top-level public API.
{quote}
>From this assumption, I'd suggest that the class name reflects its importance,
>similarly to the "Navigable" qualifier in the [JDK
>{{NavigableMap}}|https://docs.oracle.com/javase/8/docs/api/java/util/NavigableMap.html].
{quote}
{code:java}
PointMap.EntrySetSelector selector =
map.withinDistance(resolution);
// ...
PointMap.EntrySet subSet = selector.apply(v);
{code}
Also, the subset selection here seems to be split into two parts: the first to
specify the distance and the second to specify the reference point. I don't see
a reason to separate these.
{quote}
In this case, there may be no reason; but we could imagine another selector
where some part of the computation is performed at instantiation and should not
be repeated for each point.
When the use-case does not need the separation, the call is a one-liner
{code:java}
PointMap.EntrySet subSet =
map.withinDistance(resolution).apply(v);
{code}
{quote}
Computing distance between points is one of the few things that all spaces and
dimensions provide [...]
{quote}
Does it allow defining selectors as
{code}
class PointMap {
public interface Selector extends Function, P> {};
}
{code}
?
> PointSet/Map closest points
> ---
>
> Key: GEOMETRY-146
> URL: https://issues.apache.org/jira/browse/GEOMETRY-146
> Project: Commons Geometry
> Issue Type: New Feature
>Reporter: Matt Juntunen
>Priority: Major
> Fix For: 1.1
>
>
> Add methods to the new {{PointSet}} and {{PointMap}} interfaces to allow
> querying of points in order of distance from a query point.
> {code:java}
> PointSet {
> // find the closest point to pt or null if empty
> P closest(P pt);
> // iterate through points in order, with points closest to pt coming first
> Iterable closestFirst(P pt);
> // find the farthest point from pt or null if emtpy
> P farthest(P pt);
> // iterate through point in order, with points farthest from pt coming
> first
> Iterable farthestFirst(P pt);
> }
> {code}
> {{PointMap}} should have similar methods providing access to the map keys and
> entries.
--
This message was sent by Atlassian Jira
(v8.20.1#820001)
[jira] [Commented] (GEOMETRY-146) PointSet/Map closest points
[
https://issues.apache.org/jira/browse/GEOMETRY-146?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17516531#comment-17516531
]
Matt Juntunen commented on GEOMETRY-146:
bq. Discussion can continue on the latter; that does not preclude committing
the former (but please include "WIP" in the commit message, and mark the
relevant codes with "TBD", with a link to here).
Good to know. I'll keep everything on my working branch for now so that we
don't have a bunch of renaming of classes/methods in master.
bq. You did not comment about what was wrong with my proposed API, i.e. one
that would keep iteration an internal part of the "result set".
I agree with your thought of separating these operations into two parts: a
"subset selection" part and an "iteration" part. My main objection to the APi
example you gave is that I didn't see a way to specify the order of iteration.
In your example above, how would one specify that the results should be
returned in order of increasing distance?
{code:java}
PointMap.EntrySetSelector selector =
map.withinDistance(resolution);
// ...
PointMap.EntrySet subSet = selector.apply(v);
// how do I iterate over subSet from near to far?
{code}
Also, the subset selection here seems to be split into two parts: the first to
specify the distance and the second to specify the reference point. I don't see
a reason to separate these.
In my most recent API proposal, I do have a separation between subset selection
and iteration.
{code:java}
PointSet set = EuclideanCollectionUtils.pointSet3D(precision);
// select the subset of points within 1 unit from the origin
DistanceOrdering subset = set.withinDistance(Vector3D.ZERO, 1);
// iterate over the subset from near to far
List subset.nearToFar().stream()
.collect(Collectors.toList());
// get the farthest entry from the origin but still within the maximum distance
Vector3D nearest = subset.nearest();
{code}
bq. You intentionally hid the internal implementation of PointMap, yet the
"near"/"far" methods make one assume that such an implementation must support
specific iteration "modes"; hence I'm feeling uncomfortable with the
(apparent?) inconsistency, at the "public" level.
Yes, I would expect all {{PointMap/Set}} implementations to provide these
near/far iteration modes. I picture this as similar to the iteration order
methods provided by {{java.util.NavigableMap}} but applying to all spaces and
dimensions. Computing distance between points is one of the few things that all
spaces and dimensions provide so I feel that placing these methods in the
public API is appropriate.
bq. Out of curiosity, could you document (in the "examples" module) the actual
use cases that require one or the other iteration direction? That would also
help us test alternative APIs and where to draw the line between "public" and
"internal".
Yes, I am planning on adding examples in the user guide as part of this ticket.
In general, it frequently happens that distance from a certain point is part of
the point selection criteria for geometric algorithms. For example, the first
step in the quickhull algorithm is typically construction of a maximally
spanning tetrahedron. The first edge in this tetrahedron could be constructed
by selecting a point with a minimum x,y, and/or z coordinate and then selecting
the point from the set farthest from that point.
As a more concrete example, consider that a {{PointMap}} is used to represent
geographic locations and meta data. A near-to-far ordering could be used to
locate the nearest city from a specified location with a population of at least
X without requiring all points to be examined. Similarly, a far-to-near
ordering could be used to determine the worst-case distance a package would
need to travel when being shipped to a location from one of a number of cities
containing distribution centers.
In general, I consider that this near/far qualification is important enough to
warrant inclusion in the top-level public API.
> PointSet/Map closest points
> ---
>
> Key: GEOMETRY-146
> URL: https://issues.apache.org/jira/browse/GEOMETRY-146
> Project: Commons Geometry
> Issue Type: New Feature
>Reporter: Matt Juntunen
>Priority: Major
> Fix For: 1.1
>
>
> Add methods to the new {{PointSet}} and {{PointMap}} interfaces to allow
> querying of points in order of distance from a query point.
> {code:java}
> PointSet {
> // find the closest point to pt or null if empty
> P closest(P pt);
> // iterate through points in order, with points closest to pt coming first
> Iterable closestFirst(P pt);
> // find the farthest point from pt or null if emtpy
> P farthest(P pt);
> // iterate through point in order, with points farthest from pt coming
> first
> Iterable fa
[jira] [Commented] (GEOMETRY-146) PointSet/Map closest points
[
https://issues.apache.org/jira/browse/GEOMETRY-146?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17516295#comment-17516295
]
Gilles Sadowski commented on GEOMETRY-146:
--
{quote}I now have the internal logic for these operations implemented in all
spaces and dimensions. All that's left now is to decide on the public API [...]
{quote}
Discussion can continue on the latter; that does not preclude committing the
former (but please include "WIP" in the commit message, and mark the relevant
codes with "TBD", with a link to here).
{quote}I see what you're saying about having a general API but I don't have any
more ideas at this time other than the one I posted more recently.
{quote}
You did not comment about what was wrong with my proposed API, i.e. one that
would keep iteration an internal part of the "result set". Or maybe I'm missing
some inherent roadblock to that approach (?).
{quote}These two operations must be separate since there is a significant
performance benefit to obtaining a single result versus iterating through the
available points.
{quote}
We should separate two issues into two discussions:
* one about the "selector" API (and iteration over the result set), and
* one about the performance gained by having a specific API for returning a
single element (rather than a set).
You intentionally hid the internal implementation of {{{}PointMap{}}}, yet the
"near"/"far" methods make one assume that such an implementation _must_ support
specific iteration "modes"; hence I'm feeling uncomfortable with the
(apparent?) inconsistency, at the "public" level. Sorry that I cannot convey
the feeling in a more concrete way at this moment...
Overall I wonder whether we can provide all the necessary functionality
(including performance), within the [stream/functional
approach|https://docs.oracle.com/javase/8/docs/api/java/util/stream/Stream.html]
that seems to characterize all recent development in Java.
Out of curiosity, could you document (in the "examples" module) the actual use
cases that require one or the other iteration direction? That would also help
us test alternative APIs and where to draw the line between "public" and
"internal".
> PointSet/Map closest points
> ---
>
> Key: GEOMETRY-146
> URL: https://issues.apache.org/jira/browse/GEOMETRY-146
> Project: Commons Geometry
> Issue Type: New Feature
>Reporter: Matt Juntunen
>Priority: Major
> Fix For: 1.1
>
>
> Add methods to the new {{PointSet}} and {{PointMap}} interfaces to allow
> querying of points in order of distance from a query point.
> {code:java}
> PointSet {
> // find the closest point to pt or null if empty
> P closest(P pt);
> // iterate through points in order, with points closest to pt coming first
> Iterable closestFirst(P pt);
> // find the farthest point from pt or null if emtpy
> P farthest(P pt);
> // iterate through point in order, with points farthest from pt coming
> first
> Iterable farthestFirst(P pt);
> }
> {code}
> {{PointMap}} should have similar methods providing access to the map keys and
> entries.
--
This message was sent by Atlassian Jira
(v8.20.1#820001)
[jira] [Commented] (GEOMETRY-146) PointSet/Map closest points
[
https://issues.apache.org/jira/browse/GEOMETRY-146?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17515937#comment-17515937
]
Matt Juntunen commented on GEOMETRY-146:
I now have the internal logic for these operations implemented in all spaces
and dimensions. All that's left now is to decide on the public API, write a few
more tests, and then document it.
I see what you're saying about having a general API but I don't have any more
ideas at this time other than the one I posted more recently. What I'm looking
for is the ability to specify a point with an optional radius and then either
* obtain the single nearest/farthest point, or
* iterate through all available points in nearest to farthest or farthest to
nearest order.
These two operations must be separate since there is a significant performance
benefit to obtaining a single result versus iterating through the available
points. (The single point version can be performed recursively in the
multidimensional cases while iteration requires allocation of queues and other
bookkeeping structures.) Also, I would like the specification of the iteration
order to be explicit and use the terms _near_/_far_ or similar in order to make
things readable and self-documenting. The API I proposed fulfills these
requirements and IMHO provides a pretty good generalization of the operations
in question. Do you have any objections to this API or any alternative
suggestions?
> PointSet/Map closest points
> ---
>
> Key: GEOMETRY-146
> URL: https://issues.apache.org/jira/browse/GEOMETRY-146
> Project: Commons Geometry
> Issue Type: New Feature
>Reporter: Matt Juntunen
>Priority: Major
> Fix For: 1.1
>
>
> Add methods to the new {{PointSet}} and {{PointMap}} interfaces to allow
> querying of points in order of distance from a query point.
> {code:java}
> PointSet {
> // find the closest point to pt or null if empty
> P closest(P pt);
> // iterate through points in order, with points closest to pt coming first
> Iterable closestFirst(P pt);
> // find the farthest point from pt or null if emtpy
> P farthest(P pt);
> // iterate through point in order, with points farthest from pt coming
> first
> Iterable farthestFirst(P pt);
> }
> {code}
> {{PointMap}} should have similar methods providing access to the map keys and
> entries.
--
This message was sent by Atlassian Jira
(v8.20.1#820001)
[jira] [Commented] (GEOMETRY-146) PointSet/Map closest points
[
https://issues.apache.org/jira/browse/GEOMETRY-146?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17514980#comment-17514980
]
Gilles Sadowski commented on GEOMETRY-146:
--
I got that you need some way to iterate either in ascending or in descending
order. My question is whether this functionality could be some instance of a
more general API (that is iterating over the result of any filtering of the
contents of the {{PointMap}} or {{PointSet}}).
> PointSet/Map closest points
> ---
>
> Key: GEOMETRY-146
> URL: https://issues.apache.org/jira/browse/GEOMETRY-146
> Project: Commons Geometry
> Issue Type: New Feature
>Reporter: Matt Juntunen
>Priority: Major
> Fix For: 1.1
>
>
> Add methods to the new {{PointSet}} and {{PointMap}} interfaces to allow
> querying of points in order of distance from a query point.
> {code:java}
> PointSet {
> // find the closest point to pt or null if empty
> P closest(P pt);
> // iterate through points in order, with points closest to pt coming first
> Iterable closestFirst(P pt);
> // find the farthest point from pt or null if emtpy
> P farthest(P pt);
> // iterate through point in order, with points farthest from pt coming
> first
> Iterable farthestFirst(P pt);
> }
> {code}
> {{PointMap}} should have similar methods providing access to the map keys and
> entries.
--
This message was sent by Atlassian Jira
(v8.20.1#820001)
[jira] [Commented] (GEOMETRY-146) PointSet/Map closest points
[
https://issues.apache.org/jira/browse/GEOMETRY-146?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17514757#comment-17514757
]
Matt Juntunen commented on GEOMETRY-146:
How about this?
{code:java}
// interface allowing easy conversion to streams in situations where
// the number of elements is not known ahead of time
interface StreamingIterable extends Iterable {
default Stream stream() {
return StreamSupport.stream(spliterator(), false);
}
}
// represents a view of a collection ordered by distance
// relative to a reference point
interface DistanceOrdering {
T nearest();
T farthest();
StreamingIterable nearToFar();
StreamingIterable farToNear();
}
interface PointSet {
DistanceOrdering from(P pt);
DistanceOrdering withinRadius(P pt, double radius);
}
interface PointMap {
DistanceOrdering> entriesFrom(P pt);
DistanceOrdering> entriesWithinRadius(P pt, double radius);
}
{code}
Usage would then look like this:
{code:java}
// get the entry in the map farthest from the origin
PointMap map = ...
Entry result = map.from(Vector3D.ZERO).farthest();
// find the element nearest to refPt in the set that has a positive x coordinate
// and is not farther away than 3
PointSet set = ...
Vector3D refPt = Vector3D.of(1, 2, 3);
Vector3D result = null;
for (Vector3D pt : set.withinRadius(refPt, 3).nearToFar()) {
if (pt.getX() > 0) {
result = pt;
break;
}
}
// find the k nearest neighbors of pt
PointSet set = ...
Vector3D pt = Vector3D.of(1, 2, 3);
List neighbors = set.from(pt).nearToFar().stream()
.limit(k)
.collect(Collectors.toList());
{code}
> PointSet/Map closest points
> ---
>
> Key: GEOMETRY-146
> URL: https://issues.apache.org/jira/browse/GEOMETRY-146
> Project: Commons Geometry
> Issue Type: New Feature
>Reporter: Matt Juntunen
>Priority: Major
> Fix For: 1.1
>
>
> Add methods to the new {{PointSet}} and {{PointMap}} interfaces to allow
> querying of points in order of distance from a query point.
> {code:java}
> PointSet {
> // find the closest point to pt or null if empty
> P closest(P pt);
> // iterate through points in order, with points closest to pt coming first
> Iterable closestFirst(P pt);
> // find the farthest point from pt or null if emtpy
> P farthest(P pt);
> // iterate through point in order, with points farthest from pt coming
> first
> Iterable farthestFirst(P pt);
> }
> {code}
> {{PointMap}} should have similar methods providing access to the map keys and
> entries.
--
This message was sent by Atlassian Jira
(v8.20.1#820001)
[jira] [Commented] (GEOMETRY-146) PointSet/Map closest points
[
https://issues.apache.org/jira/browse/GEOMETRY-146?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17514110#comment-17514110
]
Gilles Sadowski commented on GEOMETRY-146:
--
{quote}I'm not sure if we can make this work well. We can definitely make it
work, but without access to the private details of the data structures the
EntrySetSelector interfaces would be left to iterate through the entire map in
order to find the correct entries.
{quote}
You asked for a _usage_ example.
The {{EntrySet}} and {{EntrySetSelector}} interfaces mentioned above would
define the public API. However the actual instance being returned can certainly
be a private (non-static) inner class that retains all the necessary access to
the {{PointMap}} data-structure in order to provide an efficient view.
I think that iteration order (ascending vs descending) should be build on top
of any view (i.e. the result of a "selector").
> PointSet/Map closest points
> ---
>
> Key: GEOMETRY-146
> URL: https://issues.apache.org/jira/browse/GEOMETRY-146
> Project: Commons Geometry
> Issue Type: New Feature
>Reporter: Matt Juntunen
>Priority: Major
> Fix For: 1.1
>
>
> Add methods to the new {{PointSet}} and {{PointMap}} interfaces to allow
> querying of points in order of distance from a query point.
> {code:java}
> PointSet {
> // find the closest point to pt or null if empty
> P closest(P pt);
> // iterate through points in order, with points closest to pt coming first
> Iterable closestFirst(P pt);
> // find the farthest point from pt or null if emtpy
> P farthest(P pt);
> // iterate through point in order, with points farthest from pt coming
> first
> Iterable farthestFirst(P pt);
> }
> {code}
> {{PointMap}} should have similar methods providing access to the map keys and
> entries.
--
This message was sent by Atlassian Jira
(v8.20.1#820001)
[jira] [Commented] (GEOMETRY-146) PointSet/Map closest points
[
https://issues.apache.org/jira/browse/GEOMETRY-146?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17514065#comment-17514065
]
Matt Juntunen commented on GEOMETRY-146:
I'm not sure if we can make this work well. We can definitely make it _work_,
but without access to the private details of the data structures the
{{EntrySetSelector}} interfaces would be left to iterate through the entire map
in order to find the correct entries.
I've thought about the names some more and I've come up with what I consider
better alternatives based on the antonym pair _near_/_far_ (as opposed to
_close_/_far_).
{code:java}
PointSet {
P nearest(P pt);
P nearestWithinRadius(P pt, double radius);
P farthest(P pt);
Collection nearToFar(P pt);
Collection farToNear(P pt);
}
PointMap {
Map.Entry nearestEntry(P pt);
Map.Entry nearestEntryWithinRadius(P pt, double radius);
Map.Entry farthestEntry(P pt);
Collection> entriesNearToFar(P pt);
Collection> entriesFarToNearP pt);
}
{code}
These names are concise and (to me, at least) provide a good mental image of
the operation.
> PointSet/Map closest points
> ---
>
> Key: GEOMETRY-146
> URL: https://issues.apache.org/jira/browse/GEOMETRY-146
> Project: Commons Geometry
> Issue Type: New Feature
>Reporter: Matt Juntunen
>Priority: Major
> Fix For: 1.1
>
>
> Add methods to the new {{PointSet}} and {{PointMap}} interfaces to allow
> querying of points in order of distance from a query point.
> {code:java}
> PointSet {
> // find the closest point to pt or null if empty
> P closest(P pt);
> // iterate through points in order, with points closest to pt coming first
> Iterable closestFirst(P pt);
> // find the farthest point from pt or null if emtpy
> P farthest(P pt);
> // iterate through point in order, with points farthest from pt coming
> first
> Iterable farthestFirst(P pt);
> }
> {code}
> {{PointMap}} should have similar methods providing access to the map keys and
> entries.
--
This message was sent by Atlassian Jira
(v8.20.1#820001)
[jira] [Commented] (GEOMETRY-146) PointSet/Map closest points
[
https://issues.apache.org/jira/browse/GEOMETRY-146?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17513998#comment-17513998
]
Gilles Sadowski commented on GEOMETRY-146:
--
bq. What would the calling code look like?
{code:java}
PointMap map =
EuclideanCollections.pointMap2D(Precision.DoubleEquivalence.of(1e-7));
// Populate "map".
// Create selector.
final double resolution = 1e-2;
PointMap.EntrySetSelector selector =
map.WithinDistance.of(resolution);
// Interpolate on a regular grid.
final double[][] grid = ...
for (double x = xMin; x <= xMax; x+= resolution) {
final int j = toColumnIndex(x, xMin, xMax);
for (double y = yMin; y <= yMax; y+= resolution) {
final int i = toRowIndex(j, yMin, yMax);
final Vector2D v = Vector2D.of(x, y);
// Retrieve neighbours of "v".
final PointMap.EntrySet subSet = selector.apply(v);
grid[i][j] = interpolate(subSet);
}
}
{code}
All _untested_... ;-)
> PointSet/Map closest points
> ---
>
> Key: GEOMETRY-146
> URL: https://issues.apache.org/jira/browse/GEOMETRY-146
> Project: Commons Geometry
> Issue Type: New Feature
>Reporter: Matt Juntunen
>Priority: Major
> Fix For: 1.1
>
>
> Add methods to the new {{PointSet}} and {{PointMap}} interfaces to allow
> querying of points in order of distance from a query point.
> {code:java}
> PointSet {
> // find the closest point to pt or null if empty
> P closest(P pt);
> // iterate through points in order, with points closest to pt coming first
> Iterable closestFirst(P pt);
> // find the farthest point from pt or null if emtpy
> P farthest(P pt);
> // iterate through point in order, with points farthest from pt coming
> first
> Iterable farthestFirst(P pt);
> }
> {code}
> {{PointMap}} should have similar methods providing access to the map keys and
> entries.
--
This message was sent by Atlassian Jira
(v8.20.1#820001)
[jira] [Commented] (GEOMETRY-146) PointSet/Map closest points
[
https://issues.apache.org/jira/browse/GEOMETRY-146?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17513662#comment-17513662
]
Matt Juntunen commented on GEOMETRY-146:
This looks interesting. Could you provide some examples? What would the calling
code look like?
> PointSet/Map closest points
> ---
>
> Key: GEOMETRY-146
> URL: https://issues.apache.org/jira/browse/GEOMETRY-146
> Project: Commons Geometry
> Issue Type: New Feature
>Reporter: Matt Juntunen
>Priority: Major
> Fix For: 1.1
>
>
> Add methods to the new {{PointSet}} and {{PointMap}} interfaces to allow
> querying of points in order of distance from a query point.
> {code:java}
> PointSet {
> // find the closest point to pt or null if empty
> P closest(P pt);
> // iterate through points in order, with points closest to pt coming first
> Iterable closestFirst(P pt);
> // find the farthest point from pt or null if emtpy
> P farthest(P pt);
> // iterate through point in order, with points farthest from pt coming
> first
> Iterable farthestFirst(P pt);
> }
> {code}
> {{PointMap}} should have similar methods providing access to the map keys and
> entries.
--
This message was sent by Atlassian Jira
(v8.20.1#820001)
[jira] [Commented] (GEOMETRY-146) PointSet/Map closest points
[
https://issues.apache.org/jira/browse/GEOMETRY-146?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17513655#comment-17513655
]
Gilles Sadowski commented on GEOMETRY-146:
--
{quote}Thoughts?
{quote}
{code:java}
PointMap {
// ...
public interface EntrySetSelector extends
Function>, P> {}
public class WithinDistance implements EntrySetSelector {
public WithinDistance(double dist) {
// ...
}
}
public enum ByDistance implements EntrySetSelector {
ASCENDING(/* ... */),
DESCENDING(/* ... */);
// ...
}
}
{code}
> PointSet/Map closest points
> ---
>
> Key: GEOMETRY-146
> URL: https://issues.apache.org/jira/browse/GEOMETRY-146
> Project: Commons Geometry
> Issue Type: New Feature
>Reporter: Matt Juntunen
>Priority: Major
> Fix For: 1.1
>
>
> Add methods to the new {{PointSet}} and {{PointMap}} interfaces to allow
> querying of points in order of distance from a query point.
> {code:java}
> PointSet {
> // find the closest point to pt or null if empty
> P closest(P pt);
> // iterate through points in order, with points closest to pt coming first
> Iterable closestFirst(P pt);
> // find the farthest point from pt or null if emtpy
> P farthest(P pt);
> // iterate through point in order, with points farthest from pt coming
> first
> Iterable farthestFirst(P pt);
> }
> {code}
> {{PointMap}} should have similar methods providing access to the map keys and
> entries.
--
This message was sent by Atlassian Jira
(v8.20.1#820001)
[jira] [Commented] (GEOMETRY-146) PointSet/Map closest points
[
https://issues.apache.org/jira/browse/GEOMETRY-146?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17513593#comment-17513593
]
Matt Juntunen commented on GEOMETRY-146:
Here is another shot at the API. I've added a {{closestWithinDistance}} method
and the map names all contain the word "entry" in some form to indicate that an
entry is returned (similar to {{entrySet}}). I've also realized that we can
return full {{Collection}} instances from the view methods instead of just
{{Iterable}} since we already know the number of entries. This will make the
returned views easier to work with, especially since callers can convert to a
stream just by calling {{stream()}}.
I am still not sold on the method names. They feel kind of clunky to me so I'm
open to suggestions.
{code:java}
PointSet {
// return the element closest to pt or null if empty
P closest(P pt);
// return the element closest to pt and within the specified
// distance or null if it does not exist
P closestWithinDistance(P pt, double dist);
// return the element farthest from pt or null if empty
P farthest(P pt);
// view of all elements in order of ascending distance from pt
Collection distanceAscending(P pt);
// view of all elements in order of descending distance from pt
Collection distanceDescending(P pt);
}
PointMap {
// return the entry closest to pt or null if empty
Map.Entry closestEntry(P pt);
// return the entry closest to pt and within the specified
// distance or null if it does not exist
Map.Entry closeEntryWithinDistance(P pt, double dist);
// return the entry farthest from pt or null if empty
Map.Entry farthestEntry(P pt);
// view of all entries in order of ascending distance from pt
Collection> entriesByDistanceAscending(P pt);
// view of all entries in order of descending distance from pt
Collection> entriesByDistanceDescending(P pt);
}
{code}
Thoughts?
> PointSet/Map closest points
> ---
>
> Key: GEOMETRY-146
> URL: https://issues.apache.org/jira/browse/GEOMETRY-146
> Project: Commons Geometry
> Issue Type: New Feature
>Reporter: Matt Juntunen
>Priority: Major
> Fix For: 1.1
>
>
> Add methods to the new {{PointSet}} and {{PointMap}} interfaces to allow
> querying of points in order of distance from a query point.
> {code:java}
> PointSet {
> // find the closest point to pt or null if empty
> P closest(P pt);
> // iterate through points in order, with points closest to pt coming first
> Iterable closestFirst(P pt);
> // find the farthest point from pt or null if emtpy
> P farthest(P pt);
> // iterate through point in order, with points farthest from pt coming
> first
> Iterable farthestFirst(P pt);
> }
> {code}
> {{PointMap}} should have similar methods providing access to the map keys and
> entries.
--
This message was sent by Atlassian Jira
(v8.20.1#820001)
[jira] [Commented] (GEOMETRY-146) PointSet/Map closest points
[
https://issues.apache.org/jira/browse/GEOMETRY-146?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17512726#comment-17512726
]
Matt Juntunen commented on GEOMETRY-146:
Working on this here:
https://github.com/darkma773r/commons-geometry/tree/closest
> PointSet/Map closest points
> ---
>
> Key: GEOMETRY-146
> URL: https://issues.apache.org/jira/browse/GEOMETRY-146
> Project: Commons Geometry
> Issue Type: New Feature
>Reporter: Matt Juntunen
>Priority: Major
> Fix For: 1.1
>
>
> Add methods to the new {{PointSet}} and {{PointMap}} interfaces to allow
> querying of points in order of distance from a query point.
> {code:java}
> PointSet {
> // find the closest point to pt or null if empty
> P closest(P pt);
> // iterate through points in order, with points closest to pt coming first
> Iterable closestFirst(P pt);
> // find the farthest point from pt or null if emtpy
> P farthest(P pt);
> // iterate through point in order, with points farthest from pt coming
> first
> Iterable farthestFirst(P pt);
> }
> {code}
> {{PointMap}} should have similar methods providing access to the map keys and
> entries.
--
This message was sent by Atlassian Jira
(v8.20.1#820001)
[jira] [Commented] (GEOMETRY-146) PointSet/Map closest points
[
https://issues.apache.org/jira/browse/GEOMETRY-146?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17508796#comment-17508796
]
Matt Juntunen commented on GEOMETRY-146:
The general iteration methods are required for the use cases I'm picturing.
Say, for example, you need to find the point closest to a query point that also
satisfies some other condition, such as being associated with a particular
value. This could be accomplished with a map as follows:
{code:java}
PointMap map = EuclideanCollections.pointMap3D(precision);
// add points and values ...
Vector3D queryPt = Vector3D.of(1, 2, 3);
Vector3D resultPt = null;
for (Map.Entry entry : map.closestFirst(queryPt)) {
if (entry.getValue() > 100) {
resultPt = entry.getKey();
break;
}
}
{code}
A similar use case for {{PointSet}} could look like this:
{code:java}
PointSet set = EuclideanCollections.pointSet3D(precision);
// add points ...
Vector3D queryPt = Vector3D.of(1, 2, 3);
Vector3D resultPt = null;
for (Vector3D pt : entry) {
if (pt.getX() > queryPt.getX()) {
resultPt = pt;
break;
}
}
{code}
The {{closestInRange}} methods could actually be implemented using this general
approach.
{code:java}
public List closestInRange(P pt, double dist) {
List result = new ArrayList<>();
for (P setPt : set.closestFirst(pt)) {
if (setPt.distance(pt) > dist) {
break;
}
result.add(setPt);
}
return result;
}
{code}
I'm picturing the implemented iteration operations being lazy (as they are in
the {{RegionBSPTreeXD}} classes) and only pulling values as needed. There then
shouldn't be any wasted resources from this approach.
> PointSet/Map closest points
> ---
>
> Key: GEOMETRY-146
> URL: https://issues.apache.org/jira/browse/GEOMETRY-146
> Project: Commons Geometry
> Issue Type: New Feature
>Reporter: Matt Juntunen
>Priority: Major
> Fix For: 1.1
>
>
> Add methods to the new {{PointSet}} and {{PointMap}} interfaces to allow
> querying of points in order of distance from a query point.
> {code:java}
> PointSet {
> // find the closest point to pt or null if empty
> P closest(P pt);
> // iterate through points in order, with points closest to pt coming first
> Iterable closestFirst(P pt);
> // find the farthest point from pt or null if emtpy
> P farthest(P pt);
> // iterate through point in order, with points farthest from pt coming
> first
> Iterable farthestFirst(P pt);
> }
> {code}
> {{PointMap}} should have similar methods providing access to the map keys and
> entries.
--
This message was sent by Atlassian Jira
(v8.20.1#820001)
[jira] [Commented] (GEOMETRY-146) PointSet/Map closest points
[
https://issues.apache.org/jira/browse/GEOMETRY-146?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17506415#comment-17506415
]
Gilles Sadowski commented on GEOMETRY-146:
--
My impression is that the API should be more general:
{noformat}
public Iterable closestInRange(P point, double radius);
{noformat}
Methods
* {{closestFirst}}
* {{farthestFirst}}
don't seem useful (unless I'm missing something).
They also seem wasteful of computing resources: If iterating over the whole
set, why would one want to start from some particular point?
> PointSet/Map closest points
> ---
>
> Key: GEOMETRY-146
> URL: https://issues.apache.org/jira/browse/GEOMETRY-146
> Project: Commons Geometry
> Issue Type: New Feature
>Reporter: Matt Juntunen
>Priority: Major
> Fix For: 1.1
>
>
> Add methods to the new {{PointSet}} and {{PointMap}} interfaces to allow
> querying of points in order of distance from a query point.
> {code:java}
> PointSet {
> // find the closest point to pt or null if empty
> P closest(P pt);
> // iterate through points in order, with points closest to pt coming first
> Iterable closestFirst(P pt);
> // find the farthest point from pt or null if emtpy
> P farthest(P pt);
> // iterate through point in order, with points farthest from pt coming
> first
> Iterable farthestFirst(P pt);
> }
> {code}
> {{PointMap}} should have similar methods providing access to the map keys and
> entries.
--
This message was sent by Atlassian Jira
(v8.20.1#820001)
