Re: Re: [geometry] PointMap and PointSet
Hello,
This kind of API sounds useful but not directly related to the
PointMap/Set types. As you mentioned, it seems like the API would most
likely use PointMap/Set internally. I believe the next step should be
to create a JIRA issue and figure out the details there.
Since it sounds like there are no objections to the current
PointMap/Set PR, I'm going to go ahead and merge it in and then
continue on with the closest point/farthest point API (GEOMETRY-146).
Regards,
Matt
On Wed, Mar 23, 2022 at 12:58 PM Gilles Sadowski wrote:
>
> Hi.
>
> Le mer. 23 mars 2022 à 03:27, Matt Juntunen
> a écrit :
> >
> > Gilles,
> >
> > > Say, for example, that "V" holds a single (floating-point) value. We
> > > insert entries
> > > map.put(x, 2);
> > > map.put(y, 8);
> > > assuming that "x" and "y" and just barely different, according to the
> > > chosen "precision context". Then:
> > > z = (x + y) / 2; // Pseudo-code.
> > > m = map.get(z);
> > > Does "m" equal "2" or "8", depending on whether "z" is (however
> > > slightly) closer to either "x" or "y"? Or is it "5" (interpolated value)?
> >
> > It would be either 2 or 8. In the current implementations the first
> > matching entry is returned and since entries are typically searched
> > low to high, the entry corresponding to the lower of the two keys
> > would be returned. However, I do not consider this "lowest match wins"
> > behavior to be part of the public API since it depends on the
> > implementation details.
>
> For sure, any functionality must start from some low-level data
> structure with some prescribed behaviour. Here, we assume that
> the "mechanism" returns "2" or "8" (depending on the "details").
>
> My point is rather that the "cloud of points" abstraction seems to
> require a higher-level API (for which "PointMap" would, in turn,
> be an "implementation detail" too).
> Within that abstraction, querying the value at location between
> "x" and "y" would return some interpolation (i.e. any user-defined
> "combiner") of the data stored within a given "radius" of the
> queried location.
> This would make more sense (IMO) than the application having
> to deal with a result ("2" or "8") that is implementation-dependent:
> Such an additional API layer would allow the caller to specify the
> "combiner" as, for example, "the average of the values", the result
> would then be univocally defined ("5").
> [Obviously, when specifying a radius smaller than the "precision
> context", the behaviour would be identical to a direct query to the
> underlying "PointMap".]
>
> >
> > > But is it the right behaviour in all cases, or should there be a
> > > "replacement policy" (to apply whenever points are already stored
> > > within the "precision context" neighbourhood)?
> >
> > This seems to me like additional logic that could be built on top of
> > PointMap/Set, probably using the distance query methods in
> > GEOMETRY-146.
>
> Indeed; my question aimed at pointing to the importance of providing
> such an API.
>
> > Do you have a use case in mind here?
>
> In 2D: create an image (i.e. rectangular regular grid) that represents
> the (interpolated) data associated with the (scattered) points.
>
> Another (unrelated to the above discussion) feature: Allow different
> precision contexts in different regions of the space (cf. [1]).
>
> Best,
> Gilles
>
> [1] https://en.wikipedia.org/wiki/Unstructured_grid
>
> >
> > Regards,
> > Matt
> >
> > On Tue, Mar 22, 2022 at 1:05 PM Gilles Sadowski
> > wrote:
> > >
> > > Le mar. 22 mars 2022 à 14:46, Matt Juntunen
> > > a écrit :
> > > >
> > > > Hello,
> > > >
> > > > Unless there are any other comments on the PR, I'm going to plan on
> > > > merging it into master within the next couple of days.
> > > >
> > >
> > > Thanks for providing this new functionality.
> > >
> > > Do you envision that [Geometry] will also provide ways to manipulate
> > > data stored in the map (the "V" in e.g. "PointMap")?
> > >
> > > Say, for example, that "V" holds a single (floating-point) value. We
> > > insert entries
> > > map.put(x, 2);
> > > map.put(y, 8);
> > > assuming that "x" and "y" and just barely different, according to the
> > > chosen "precision context". Then:
> > > z = (x + y) / 2; // Pseudo-code.
> > > m = map.get(z);
> > > Does "m" equal "2" or "8", depending on whether "z" is (however
> > > slightly) closer to either "x" or "y"? Or is it "5" (interpolated value)?
> > >
> > > This is related to the feature which I mentioned in GEOMETRY-146.
> > > I get that the low-level data-structure cannot "make up" a value that
> > > is not actually stored but it seems that the next step would be an API
> > > that lets the user specify what it means to retrieve data from the map.
> > >
> > > Then, there is also
> > > map.put(z, 10);
> > > Currently "10" will replace either the value at "x" or the value at "y".
> > > But is it the right behaviour in all cases, or should there be a
> > > "replacement policy" (to apply whenever points
Re: Re: [geometry] PointMap and PointSet
Hi.
Le mer. 23 mars 2022 à 03:27, Matt Juntunen
a écrit :
>
> Gilles,
>
> > Say, for example, that "V" holds a single (floating-point) value. We
> > insert entries
> > map.put(x, 2);
> > map.put(y, 8);
> > assuming that "x" and "y" and just barely different, according to the
> > chosen "precision context". Then:
> > z = (x + y) / 2; // Pseudo-code.
> > m = map.get(z);
> > Does "m" equal "2" or "8", depending on whether "z" is (however
> > slightly) closer to either "x" or "y"? Or is it "5" (interpolated value)?
>
> It would be either 2 or 8. In the current implementations the first
> matching entry is returned and since entries are typically searched
> low to high, the entry corresponding to the lower of the two keys
> would be returned. However, I do not consider this "lowest match wins"
> behavior to be part of the public API since it depends on the
> implementation details.
For sure, any functionality must start from some low-level data
structure with some prescribed behaviour. Here, we assume that
the "mechanism" returns "2" or "8" (depending on the "details").
My point is rather that the "cloud of points" abstraction seems to
require a higher-level API (for which "PointMap" would, in turn,
be an "implementation detail" too).
Within that abstraction, querying the value at location between
"x" and "y" would return some interpolation (i.e. any user-defined
"combiner") of the data stored within a given "radius" of the
queried location.
This would make more sense (IMO) than the application having
to deal with a result ("2" or "8") that is implementation-dependent:
Such an additional API layer would allow the caller to specify the
"combiner" as, for example, "the average of the values", the result
would then be univocally defined ("5").
[Obviously, when specifying a radius smaller than the "precision
context", the behaviour would be identical to a direct query to the
underlying "PointMap".]
>
> > But is it the right behaviour in all cases, or should there be a
> > "replacement policy" (to apply whenever points are already stored
> > within the "precision context" neighbourhood)?
>
> This seems to me like additional logic that could be built on top of
> PointMap/Set, probably using the distance query methods in
> GEOMETRY-146.
Indeed; my question aimed at pointing to the importance of providing
such an API.
> Do you have a use case in mind here?
In 2D: create an image (i.e. rectangular regular grid) that represents
the (interpolated) data associated with the (scattered) points.
Another (unrelated to the above discussion) feature: Allow different
precision contexts in different regions of the space (cf. [1]).
Best,
Gilles
[1] https://en.wikipedia.org/wiki/Unstructured_grid
>
> Regards,
> Matt
>
> On Tue, Mar 22, 2022 at 1:05 PM Gilles Sadowski wrote:
> >
> > Le mar. 22 mars 2022 à 14:46, Matt Juntunen
> > a écrit :
> > >
> > > Hello,
> > >
> > > Unless there are any other comments on the PR, I'm going to plan on
> > > merging it into master within the next couple of days.
> > >
> >
> > Thanks for providing this new functionality.
> >
> > Do you envision that [Geometry] will also provide ways to manipulate
> > data stored in the map (the "V" in e.g. "PointMap")?
> >
> > Say, for example, that "V" holds a single (floating-point) value. We
> > insert entries
> > map.put(x, 2);
> > map.put(y, 8);
> > assuming that "x" and "y" and just barely different, according to the
> > chosen "precision context". Then:
> > z = (x + y) / 2; // Pseudo-code.
> > m = map.get(z);
> > Does "m" equal "2" or "8", depending on whether "z" is (however
> > slightly) closer to either "x" or "y"? Or is it "5" (interpolated value)?
> >
> > This is related to the feature which I mentioned in GEOMETRY-146.
> > I get that the low-level data-structure cannot "make up" a value that
> > is not actually stored but it seems that the next step would be an API
> > that lets the user specify what it means to retrieve data from the map.
> >
> > Then, there is also
> > map.put(z, 10);
> > Currently "10" will replace either the value at "x" or the value at "y".
> > But is it the right behaviour in all cases, or should there be a
> > "replacement policy" (to apply whenever points are already stored
> > within the "precision context" neighbourhood)?
> >
> > Does this make sense?
> >
> > Gilles
-
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org
Re: Re: [geometry] PointMap and PointSet
Gilles, > Say, for example, that "V" holds a single (floating-point) value. We > insert entries > map.put(x, 2); > map.put(y, 8); > assuming that "x" and "y" and just barely different, according to the > chosen "precision context". Then: > z = (x + y) / 2; // Pseudo-code. > m = map.get(z); > Does "m" equal "2" or "8", depending on whether "z" is (however > slightly) closer to either "x" or "y"? Or is it "5" (interpolated value)? It would be either 2 or 8. In the current implementations the first matching entry is returned and since entries are typically searched low to high, the entry corresponding to the lower of the two keys would be returned. However, I do not consider this "lowest match wins" behavior to be part of the public API since it depends on the implementation details. > But is it the right behaviour in all cases, or should there be a > "replacement policy" (to apply whenever points are already stored > within the "precision context" neighbourhood)? This seems to me like additional logic that could be built on top of PointMap/Set, probably using the distance query methods in GEOMETRY-146. Do you have a use case in mind here? Regards, Matt On Tue, Mar 22, 2022 at 1:05 PM Gilles Sadowski wrote: > > Le mar. 22 mars 2022 à 14:46, Matt Juntunen > a écrit : > > > > Hello, > > > > Unless there are any other comments on the PR, I'm going to plan on > > merging it into master within the next couple of days. > > > > Thanks for providing this new functionality. > > Do you envision that [Geometry] will also provide ways to manipulate > data stored in the map (the "V" in e.g. "PointMap")? > > Say, for example, that "V" holds a single (floating-point) value. We > insert entries > map.put(x, 2); > map.put(y, 8); > assuming that "x" and "y" and just barely different, according to the > chosen "precision context". Then: > z = (x + y) / 2; // Pseudo-code. > m = map.get(z); > Does "m" equal "2" or "8", depending on whether "z" is (however > slightly) closer to either "x" or "y"? Or is it "5" (interpolated value)? > > This is related to the feature which I mentioned in GEOMETRY-146. > I get that the low-level data-structure cannot "make up" a value that > is not actually stored but it seems that the next step would be an API > that lets the user specify what it means to retrieve data from the map. > > Then, there is also > map.put(z, 10); > Currently "10" will replace either the value at "x" or the value at "y". > But is it the right behaviour in all cases, or should there be a > "replacement policy" (to apply whenever points are already stored > within the "precision context" neighbourhood)? > > Does this make sense? > > Gilles > > - > To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org > For additional commands, e-mail: dev-h...@commons.apache.org > - To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
Re: Re: [geometry] PointMap and PointSet
Le mar. 22 mars 2022 à 14:46, Matt Juntunen a écrit : > > Hello, > > Unless there are any other comments on the PR, I'm going to plan on > merging it into master within the next couple of days. > Thanks for providing this new functionality. Do you envision that [Geometry] will also provide ways to manipulate data stored in the map (the "V" in e.g. "PointMap")? Say, for example, that "V" holds a single (floating-point) value. We insert entries map.put(x, 2); map.put(y, 8); assuming that "x" and "y" and just barely different, according to the chosen "precision context". Then: z = (x + y) / 2; // Pseudo-code. m = map.get(z); Does "m" equal "2" or "8", depending on whether "z" is (however slightly) closer to either "x" or "y"? Or is it "5" (interpolated value)? This is related to the feature which I mentioned in GEOMETRY-146. I get that the low-level data-structure cannot "make up" a value that is not actually stored but it seems that the next step would be an API that lets the user specify what it means to retrieve data from the map. Then, there is also map.put(z, 10); Currently "10" will replace either the value at "x" or the value at "y". But is it the right behaviour in all cases, or should there be a "replacement policy" (to apply whenever points are already stored within the "precision context" neighbourhood)? Does this make sense? Gilles - To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
Re: Re: [geometry] PointMap and PointSet
Hello, Unless there are any other comments on the PR, I'm going to plan on merging it into master within the next couple of days. Regards, Matt On Sun, Mar 20, 2022 at 11:39 AM Matt Juntunen wrote: > > Hi Eric, > > > Would Java’s Map.entrySet provide the “getEntry” type method needed? > > https://docs.oracle.com/javase/8/docs/api/java/util/Map.html#entrySet-- > > Or would this provide all entry’s and still need to find the specific entry > > so maybe a forEach variation to filter for a specific entry? > > https://docs.oracle.com/javase/8/docs/api/java/util/Map.html#forEach-java.util.function.BiConsumer- > > This would work but it would require iterating through half of the set > on average in order to find the correct entry, meaning we would lose > the performance benefits of the spatial data structure. The > PointMap.getEntry() method currently in the PR avoids this iteration > requirement. > > Regards, > Matt > > On Sun, Mar 20, 2022 at 9:13 AM Eric Bresie wrote: > > > > > > > > > > On March 14, 2022 at 10:19:14 AM CDT, Matt Juntunen > > wrote: > > > > I'm a little bit confused: Isn't it always the case that > > > > getEntry(p).getKey() > > will return the originally inserted (i.e. "canonical") point (i.e. not "p")? > > > > Map does not contain a "getEntry" method. If it did, that would indeed > > be preferable. > > > > > > Would Java’s Map.entrySet provide the “getEntry” type method needed? > > > > https://docs.oracle.com/javase/8/docs/api/java/util/Map.html#entrySet-- > > > > Or would this provide all entry’s and still need to find the specific entry > > so maybe a forEach variation to filter for a specific entry? > > https://docs.oracle.com/javase/8/docs/api/java/util/Map.html#forEach-java.util.function.BiConsumer- > > > > Unless I'm missing a standard use-case, the specialized methods > > > > "closestFirst" and "farthestFirst" don't seem useful (and wasteful > > of computing resources: If iterating over the whole set, why would > > one want to start from some particular point?). > > > > > > Eric Bresie > > ebre...@gmail.com > > > > - To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
Re: Re: [geometry] PointMap and PointSet
Hi Eric, > Would Java’s Map.entrySet provide the “getEntry” type method needed? > https://docs.oracle.com/javase/8/docs/api/java/util/Map.html#entrySet-- > Or would this provide all entry’s and still need to find the specific entry > so maybe a forEach variation to filter for a specific entry? > https://docs.oracle.com/javase/8/docs/api/java/util/Map.html#forEach-java.util.function.BiConsumer- This would work but it would require iterating through half of the set on average in order to find the correct entry, meaning we would lose the performance benefits of the spatial data structure. The PointMap.getEntry() method currently in the PR avoids this iteration requirement. Regards, Matt On Sun, Mar 20, 2022 at 9:13 AM Eric Bresie wrote: > > > > > On March 14, 2022 at 10:19:14 AM CDT, Matt Juntunen > wrote: > > I'm a little bit confused: Isn't it always the case that > > getEntry(p).getKey() > will return the originally inserted (i.e. "canonical") point (i.e. not "p")? > > Map does not contain a "getEntry" method. If it did, that would indeed > be preferable. > > > Would Java’s Map.entrySet provide the “getEntry” type method needed? > > https://docs.oracle.com/javase/8/docs/api/java/util/Map.html#entrySet-- > > Or would this provide all entry’s and still need to find the specific entry > so maybe a forEach variation to filter for a specific entry? > https://docs.oracle.com/javase/8/docs/api/java/util/Map.html#forEach-java.util.function.BiConsumer- > > Unless I'm missing a standard use-case, the specialized methods > > "closestFirst" and "farthestFirst" don't seem useful (and wasteful > of computing resources: If iterating over the whole set, why would > one want to start from some particular point?). > > > Eric Bresie > ebre...@gmail.com > > - To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
Re: Re: [geometry] PointMap and PointSet
> > On March 14, 2022 at 10:19:14 AM CDT, Matt Juntunen > mailto:matt.a.juntu...@gmail.com)> wrote: > > > I'm a little bit confused: Isn't it always the case that > getEntry(p).getKey() > will return the originally inserted (i.e. "canonical") point (i.e. not "p")? > > Map does not contain a "getEntry" method. If it did, that would indeed > be preferable. Would Java’s Map.entrySet provide the “getEntry” type method needed? https://docs.oracle.com/javase/8/docs/api/java/util/Map.html#entrySet-- Or would this provide all entry’s and still need to find the specific entry so maybe a forEach variation to filter for a specific entry? https://docs.oracle.com/javase/8/docs/api/java/util/Map.html#forEach-java.util.function.BiConsumer- > > Unless I'm missing a standard use-case, the specialized methods > "closestFirst" and "farthestFirst" don't seem useful (and wasteful > of computing resources: If iterating over the whole set, why would > one want to start from some particular point?). Eric Bresie ebre...@gmail.com >
Re: [geometry] PointMap and PointSet
Hello, I've updated the PR [1] with the following changes: - made the Map.Entry instance returned by PointMap.getEntry() support the setValue() method for all spaces and dimensions - created an abstract base class to share code between the 1D PointMap implementations - fixed a bug in the 1D spherical point map remove() method - added additional unit tests Supporting setValue() in the multidimensional cases was trivial since I simply returned the actual SimpleEntry instance stored in the map instead of an immutable wrapper instance. For the 1D cases, I made getEntry() return a wrapper instance that calls Map.replace() on the underlying TreeMap when the value is changed. This forces another key look up but I believe that the small overhead is worth it in order to provide a consistent PointMap API. In any case, the overall performance is not affected since calling put() or replace() is the only method available to modify a TreeMap entry (outside of using the entrySet). Let me know what you think. Regards, Matt [1] https://github.com/apache/commons-geometry/pull/194 On Wed, Mar 16, 2022 at 12:30 PM Gilles Sadowski wrote: > > Hi. > > Le mer. 16 mars 2022 à 15:42, Matt Juntunen > a écrit : > > > > Hello, > > > > > I suggest to carefully consider whether to return a "SimpleEntry" > > (and prominently note that any sort of concurrent modification is > > a caller responsibility). > > > > I see what you mean and I think that would be a good idea. However, > > the sticking point is that the 1D implementations for both Euclidean > > and spherical space internally use the JDK's TreeMap class to store > > entries, due to its superior performance when compared to the > > AbstractBucketPointMap class used for other dimensions. TreeMap > > returns immutable Map.Entry instances from its entry-access methods > > (e.g., ceilingEntry, floorEntry), > > The apidocs[1] state: > ---CUT--- > Map.Entry ceilingEntry(K key) >Returns a key-value mapping associated with the least key greater > than or equal to the given key, or null if there is no such key. > ---CUT--- > > > so there is not a straightforward > > way for us to implement the behavior you propose for these dimensions. > > AFAICT, (im)mutability of the returned entry is not part of the > JDK-mandated API. > So, assuming that the behaviour is implementation-dependent, > it can be chosen to be different for different dimensions on the > basis of which behaviour is most "natural" for applications. > > > The options I see are: > > 1. Have all returned entries be immutable (the current behavior). > > 2. Return specialized Map.Entry implementations for the 1D cases that > > call the "put" method on the underlying map when "setValue" is called. > > > > Option #2 seems less than ideal so unless there is another approach > > that I'm missing, I vote for #1. > > I agree that the situation is somewhat unsatisfying. But, as said, I'd > favour #1 only if there were an actual security promise. Otherwise, > immutability is a false claim. > Unless I'm mistaken, calling "put" in order to update the "value" is > necessarily less performant than calling "setValue" (map search in > the former, no-op in the latter). > > Regards, > Gilles > > [1] > https://docs.oracle.com/javase/8/docs/api/java/util/TreeMap.html#ceilingEntry-K- > > > Regards, > > Matt > > > > > > On Wed, Mar 16, 2022 at 9:48 AM Gilles Sadowski > > wrote: > > > > > > Hi. > > > > > > Le mer. 16 mars 2022 à 03:17, Matt Juntunen > > > a écrit : > > > > > > > > Hello, > > > > > > > > I've made the following changes to the PR: > > > > - removed the "resolveKey" method from PointMap > > > > - renamed PointMap.resolveEntry to PointMap.getEntry and > > > > PointSet.resolve to PointSet.get > > > > - added an entry on PointMap/PointSet to the user guide > > > > - addressed Github comments (thanks, Bruno!) > > > > > > > > I ran some performance tests regarding the immutable entry instance > > > > created in the PointMap.getEntry method and there seems to be no > > > > impact. > > > > > > > > > Furthermore, what is actually meant here by "immutable > > > > instance" (since the "value" could be mutable without the > > > > map being aware of the fact)? > > > > > > > > It is immutable in that the object reference used as the entry value > > > > cannot be changed. This reference could point to a mutable object. > > > > This is the same behavior as other Map implementations. > > > > > > I don't see that "reference immutability" is mandated by the > > > "Map" interface (see e.g. [1]). > > > > > > I've noted many times that I generally favour (true) immutability: > > > It makes much sense for "small" data-structures (e.g. for future > > > potential optimizations[2]). > > > > > > However, the "cloud of points" data-structure is at the opposite > > > of the spectrum from this POV: It is intended to contain a large > > > number of points whose "key" should indeed be (truly) immutable > > > but whose value would likely need to be mu
Re: [geometry] PointMap and PointSet
Hi. Le mer. 16 mars 2022 à 15:42, Matt Juntunen a écrit : > > Hello, > > > I suggest to carefully consider whether to return a "SimpleEntry" > (and prominently note that any sort of concurrent modification is > a caller responsibility). > > I see what you mean and I think that would be a good idea. However, > the sticking point is that the 1D implementations for both Euclidean > and spherical space internally use the JDK's TreeMap class to store > entries, due to its superior performance when compared to the > AbstractBucketPointMap class used for other dimensions. TreeMap > returns immutable Map.Entry instances from its entry-access methods > (e.g., ceilingEntry, floorEntry), The apidocs[1] state: ---CUT--- Map.Entry ceilingEntry(K key) Returns a key-value mapping associated with the least key greater than or equal to the given key, or null if there is no such key. ---CUT--- > so there is not a straightforward > way for us to implement the behavior you propose for these dimensions. AFAICT, (im)mutability of the returned entry is not part of the JDK-mandated API. So, assuming that the behaviour is implementation-dependent, it can be chosen to be different for different dimensions on the basis of which behaviour is most "natural" for applications. > The options I see are: > 1. Have all returned entries be immutable (the current behavior). > 2. Return specialized Map.Entry implementations for the 1D cases that > call the "put" method on the underlying map when "setValue" is called. > > Option #2 seems less than ideal so unless there is another approach > that I'm missing, I vote for #1. I agree that the situation is somewhat unsatisfying. But, as said, I'd favour #1 only if there were an actual security promise. Otherwise, immutability is a false claim. Unless I'm mistaken, calling "put" in order to update the "value" is necessarily less performant than calling "setValue" (map search in the former, no-op in the latter). Regards, Gilles [1] https://docs.oracle.com/javase/8/docs/api/java/util/TreeMap.html#ceilingEntry-K- > Regards, > Matt > > > On Wed, Mar 16, 2022 at 9:48 AM Gilles Sadowski wrote: > > > > Hi. > > > > Le mer. 16 mars 2022 à 03:17, Matt Juntunen > > a écrit : > > > > > > Hello, > > > > > > I've made the following changes to the PR: > > > - removed the "resolveKey" method from PointMap > > > - renamed PointMap.resolveEntry to PointMap.getEntry and > > > PointSet.resolve to PointSet.get > > > - added an entry on PointMap/PointSet to the user guide > > > - addressed Github comments (thanks, Bruno!) > > > > > > I ran some performance tests regarding the immutable entry instance > > > created in the PointMap.getEntry method and there seems to be no > > > impact. > > > > > > > Furthermore, what is actually meant here by "immutable > > > instance" (since the "value" could be mutable without the > > > map being aware of the fact)? > > > > > > It is immutable in that the object reference used as the entry value > > > cannot be changed. This reference could point to a mutable object. > > > This is the same behavior as other Map implementations. > > > > I don't see that "reference immutability" is mandated by the > > "Map" interface (see e.g. [1]). > > > > I've noted many times that I generally favour (true) immutability: > > It makes much sense for "small" data-structures (e.g. for future > > potential optimizations[2]). > > > > However, the "cloud of points" data-structure is at the opposite > > of the spectrum from this POV: It is intended to contain a large > > number of points whose "key" should indeed be (truly) immutable > > but whose value would likely need to be mutable for many actual > > use cases. > > If a "SimpleImmutableEntry" is returned, then in order to modify > > the map's "value" contents, one has to (IIUC) > > * retrieve the entry, > > * create a new value, > > * call "put" (on the map) > > rather than > > * retrieve the entry > > * call "setValue" (on the entry). > > So we have a somewhat crippled API that does not bring any > > advantage since reference immutability doesn't provide any > > security to the map's user (any other caller who is being passed > > the same map, is able to change its contents anyways). > > > > I suggest to carefully consider whether to return a "SimpleEntry" > > (and prominently note that any sort of concurrent modification is > > a caller responsibility). > > > > Regards, > > Gilles > > > > [1] > > https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html#entrySet-- > > [2] > > https://cr.openjdk.java.net/~briangoetz/valhalla/sov/02-object-model.html > > > > >>> [...] - To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
Re: [geometry] PointMap and PointSet
On Wed, 16 Mar 2022 at 14:42, Matt Juntunen
wrote:
> Hello,
>
> > I suggest to carefully consider whether to return a "SimpleEntry"
> (and prominently note that any sort of concurrent modification is
> a caller responsibility).
>
> I see what you mean and I think that would be a good idea. However,
> the sticking point is that the 1D implementations for both Euclidean
> and spherical space internally use the JDK's TreeMap class to store
> entries, due to its superior performance when compared to the
> AbstractBucketPointMap class used for other dimensions. TreeMap
> returns immutable Map.Entry instances from its entry-access methods
> (e.g., ceilingEntry, floorEntry), so there is not a straightforward
> way for us to implement the behavior you propose for these dimensions.
> The options I see are:
> 1. Have all returned entries be immutable (the current behavior).
> 2. Return specialized Map.Entry implementations for the 1D cases that
> call the "put" method on the underlying map when "setValue" is called.
>
> Option #2 seems less than ideal so unless there is another approach
> that I'm missing, I vote for #1.
>
>
Option #3
Since the 1D TreeMap is hidden, you store entries in it as an
updatable reference, e.g. 'new Object[1]'. You can then get the immutable
entry from the TreeMap and update the contents stored in the immutable
object array without ever having to call set on the TreeMap after
modification:
class Hidden {
TreeMap map = new TreeMap<>();
V put(K k, V v) {
if (map.isEmpty()) {
map.put(k, new Object[] {v});
return null;
}
Entry e = map.ceilingEntry(k);
Object[] o = e.getValue();
// ugly
@SuppressWarnings("unchecked")
V old = (V) o[0];
o[0] = v;
return old;
}
}
This will be memory inefficient as each entry in the TreeMap has an
additional pointer.
Depending on what your API is then other methods requiring indirection will
also be inefficient. However you can provide methods to bulk search the
collection with minimal object allocation (forEach) or to do bulk changes
(replaceAll).
Alex
Re: [geometry] PointMap and PointSet
Hello, > I suggest to carefully consider whether to return a "SimpleEntry" (and prominently note that any sort of concurrent modification is a caller responsibility). I see what you mean and I think that would be a good idea. However, the sticking point is that the 1D implementations for both Euclidean and spherical space internally use the JDK's TreeMap class to store entries, due to its superior performance when compared to the AbstractBucketPointMap class used for other dimensions. TreeMap returns immutable Map.Entry instances from its entry-access methods (e.g., ceilingEntry, floorEntry), so there is not a straightforward way for us to implement the behavior you propose for these dimensions. The options I see are: 1. Have all returned entries be immutable (the current behavior). 2. Return specialized Map.Entry implementations for the 1D cases that call the "put" method on the underlying map when "setValue" is called. Option #2 seems less than ideal so unless there is another approach that I'm missing, I vote for #1. Regards, Matt On Wed, Mar 16, 2022 at 9:48 AM Gilles Sadowski wrote: > > Hi. > > Le mer. 16 mars 2022 à 03:17, Matt Juntunen > a écrit : > > > > Hello, > > > > I've made the following changes to the PR: > > - removed the "resolveKey" method from PointMap > > - renamed PointMap.resolveEntry to PointMap.getEntry and > > PointSet.resolve to PointSet.get > > - added an entry on PointMap/PointSet to the user guide > > - addressed Github comments (thanks, Bruno!) > > > > I ran some performance tests regarding the immutable entry instance > > created in the PointMap.getEntry method and there seems to be no > > impact. > > > > > Furthermore, what is actually meant here by "immutable > > instance" (since the "value" could be mutable without the > > map being aware of the fact)? > > > > It is immutable in that the object reference used as the entry value > > cannot be changed. This reference could point to a mutable object. > > This is the same behavior as other Map implementations. > > I don't see that "reference immutability" is mandated by the > "Map" interface (see e.g. [1]). > > I've noted many times that I generally favour (true) immutability: > It makes much sense for "small" data-structures (e.g. for future > potential optimizations[2]). > > However, the "cloud of points" data-structure is at the opposite > of the spectrum from this POV: It is intended to contain a large > number of points whose "key" should indeed be (truly) immutable > but whose value would likely need to be mutable for many actual > use cases. > If a "SimpleImmutableEntry" is returned, then in order to modify > the map's "value" contents, one has to (IIUC) > * retrieve the entry, > * create a new value, > * call "put" (on the map) > rather than > * retrieve the entry > * call "setValue" (on the entry). > So we have a somewhat crippled API that does not bring any > advantage since reference immutability doesn't provide any > security to the map's user (any other caller who is being passed > the same map, is able to change its contents anyways). > > I suggest to carefully consider whether to return a "SimpleEntry" > (and prominently note that any sort of concurrent modification is > a caller responsibility). > > Regards, > Gilles > > [1] > https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html#entrySet-- > [2] https://cr.openjdk.java.net/~briangoetz/valhalla/sov/02-object-model.html > > >>> [...] > > - > To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org > For additional commands, e-mail: dev-h...@commons.apache.org > - To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
Re: [geometry] PointMap and PointSet
Hi. Le mer. 16 mars 2022 à 03:17, Matt Juntunen a écrit : > > Hello, > > I've made the following changes to the PR: > - removed the "resolveKey" method from PointMap > - renamed PointMap.resolveEntry to PointMap.getEntry and > PointSet.resolve to PointSet.get > - added an entry on PointMap/PointSet to the user guide > - addressed Github comments (thanks, Bruno!) > > I ran some performance tests regarding the immutable entry instance > created in the PointMap.getEntry method and there seems to be no > impact. > > > Furthermore, what is actually meant here by "immutable > instance" (since the "value" could be mutable without the > map being aware of the fact)? > > It is immutable in that the object reference used as the entry value > cannot be changed. This reference could point to a mutable object. > This is the same behavior as other Map implementations. I don't see that "reference immutability" is mandated by the "Map" interface (see e.g. [1]). I've noted many times that I generally favour (true) immutability: It makes much sense for "small" data-structures (e.g. for future potential optimizations[2]). However, the "cloud of points" data-structure is at the opposite of the spectrum from this POV: It is intended to contain a large number of points whose "key" should indeed be (truly) immutable but whose value would likely need to be mutable for many actual use cases. If a "SimpleImmutableEntry" is returned, then in order to modify the map's "value" contents, one has to (IIUC) * retrieve the entry, * create a new value, * call "put" (on the map) rather than * retrieve the entry * call "setValue" (on the entry). So we have a somewhat crippled API that does not bring any advantage since reference immutability doesn't provide any security to the map's user (any other caller who is being passed the same map, is able to change its contents anyways). I suggest to carefully consider whether to return a "SimpleEntry" (and prominently note that any sort of concurrent modification is a caller responsibility). Regards, Gilles [1] https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html#entrySet-- [2] https://cr.openjdk.java.net/~briangoetz/valhalla/sov/02-object-model.html >>> [...] - To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
Re: [geometry] PointMap and PointSet
Hello, I've made the following changes to the PR: - removed the "resolveKey" method from PointMap - renamed PointMap.resolveEntry to PointMap.getEntry and PointSet.resolve to PointSet.get - added an entry on PointMap/PointSet to the user guide - addressed Github comments (thanks, Bruno!) I ran some performance tests regarding the immutable entry instance created in the PointMap.getEntry method and there seems to be no impact. > Furthermore, what is actually meant here by "immutable instance" (since the "value" could be mutable without the map being aware of the fact)? It is immutable in that the object reference used as the entry value cannot be changed. This reference could point to a mutable object. This is the same behavior as other Map implementations. Regards, Matt On Tue, Mar 15, 2022 at 10:51 AM Gilles Sadowski wrote: > > Hi. > > Le mar. 15 mars 2022 à 00:47, Matt Juntunen > a écrit : > > > > Hello, > > > > > Do I understand correctly that the "resolveEntry" method which > > you added behaves as my above "getEntry"? > > > > Correct. > > > > > If so, the latter can > > replace both "resolve" methods, for a (c)leaner API. > > > > That would work. I would need to add a matching "get" method to > > PointSet to provide the same functionality there. One consideration > > here is that the "resolveEntry" method creates and returns an > > immutable Entry instance with each call. The "resolveKey" method > > avoids this. > > I had missed that subtlety; but it entails the question of what > this functionality's intended usage is; e.g. would a user often > need to access the "key" but not the associated "value"? > > Furthermore, what is actually meant here by "immutable > instance" (since the "value" could be mutable without the > map being aware of the fact)? > > > I'm not sure if this will have an impact on performance. > > I'll try reducing the API as you suggest and include it in the PR if > > it doesn't make a difference in performance. > > > > Do you prefer the "get" verb over "resolve", > > Yes (I'm missing what is being resolved; it's just something > being accessed). > > Best, > Gilles > > > e.g. "getEntry" vs "resolveEntry"? > > > > Regards, > > Matt > > > > On Mon, Mar 14, 2022 at 2:19 PM Gilles Sadowski > > wrote: > > > > > > Hello. > > > > > > Le lun. 14 mars 2022 à 16:19, Matt Juntunen > > > a écrit : > > > > > > > > Gilles, > > > > > > > > > it would be great to keep the tutorials/userguide in sync. > > > > > > > > Sounds good. I'll update the user guide in this PR. > > > > > > > > > I'm a little bit confused: Isn't it always the case that > > > > getEntry(p).getKey() > > > > will return the originally inserted (i.e. "canonical") point (i.e. not > > > > "p")? > > > > > > > > Map does not contain a "getEntry" method. If it did, that would indeed > > > > be preferable. > > > > > > Do I understand correctly that the "resolveEntry" method which > > > you added behaves as my above "getEntry"? If so, the latter can > > > replace both "resolve" methods, for a (c)leaner API. > > > > > > > > Unless I'm missing a standard use-case, the specialized methods > > > > "closestFirst" and "farthestFirst" don't seem useful (and wasteful > > > > of computing resources: If iterating over the whole set, why would > > > > one want to start from some particular point?). > > > > > > > > Could you post this comment on the JIRA issue and we can continue the > > > > discussion there? > > > > > > Done. > > > > > > Regards, > > > Gilles > > - > To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org > For additional commands, e-mail: dev-h...@commons.apache.org > - To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
Re: [geometry] PointMap and PointSet
Hi. Le mar. 15 mars 2022 à 00:47, Matt Juntunen a écrit : > > Hello, > > > Do I understand correctly that the "resolveEntry" method which > you added behaves as my above "getEntry"? > > Correct. > > > If so, the latter can > replace both "resolve" methods, for a (c)leaner API. > > That would work. I would need to add a matching "get" method to > PointSet to provide the same functionality there. One consideration > here is that the "resolveEntry" method creates and returns an > immutable Entry instance with each call. The "resolveKey" method > avoids this. I had missed that subtlety; but it entails the question of what this functionality's intended usage is; e.g. would a user often need to access the "key" but not the associated "value"? Furthermore, what is actually meant here by "immutable instance" (since the "value" could be mutable without the map being aware of the fact)? > I'm not sure if this will have an impact on performance. > I'll try reducing the API as you suggest and include it in the PR if > it doesn't make a difference in performance. > > Do you prefer the "get" verb over "resolve", Yes (I'm missing what is being resolved; it's just something being accessed). Best, Gilles > e.g. "getEntry" vs "resolveEntry"? > > Regards, > Matt > > On Mon, Mar 14, 2022 at 2:19 PM Gilles Sadowski wrote: > > > > Hello. > > > > Le lun. 14 mars 2022 à 16:19, Matt Juntunen > > a écrit : > > > > > > Gilles, > > > > > > > it would be great to keep the tutorials/userguide in sync. > > > > > > Sounds good. I'll update the user guide in this PR. > > > > > > > I'm a little bit confused: Isn't it always the case that > > > getEntry(p).getKey() > > > will return the originally inserted (i.e. "canonical") point (i.e. not > > > "p")? > > > > > > Map does not contain a "getEntry" method. If it did, that would indeed > > > be preferable. > > > > Do I understand correctly that the "resolveEntry" method which > > you added behaves as my above "getEntry"? If so, the latter can > > replace both "resolve" methods, for a (c)leaner API. > > > > > > Unless I'm missing a standard use-case, the specialized methods > > > "closestFirst" and "farthestFirst" don't seem useful (and wasteful > > > of computing resources: If iterating over the whole set, why would > > > one want to start from some particular point?). > > > > > > Could you post this comment on the JIRA issue and we can continue the > > > discussion there? > > > > Done. > > > > Regards, > > Gilles - To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
Re: [geometry] PointMap and PointSet
Hello, > Do I understand correctly that the "resolveEntry" method which you added behaves as my above "getEntry"? Correct. > If so, the latter can replace both "resolve" methods, for a (c)leaner API. That would work. I would need to add a matching "get" method to PointSet to provide the same functionality there. One consideration here is that the "resolveEntry" method creates and returns an immutable Entry instance with each call. The "resolveKey" method avoids this. I'm not sure if this will have an impact on performance. I'll try reducing the API as you suggest and include it in the PR if it doesn't make a difference in performance. Do you prefer the "get" verb over "resolve", e.g. "getEntry" vs "resolveEntry"? Regards, Matt On Mon, Mar 14, 2022 at 2:19 PM Gilles Sadowski wrote: > > Hello. > > Le lun. 14 mars 2022 à 16:19, Matt Juntunen > a écrit : > > > > Gilles, > > > > > it would be great to keep the tutorials/userguide in sync. > > > > Sounds good. I'll update the user guide in this PR. > > > > > I'm a little bit confused: Isn't it always the case that > > getEntry(p).getKey() > > will return the originally inserted (i.e. "canonical") point (i.e. not "p")? > > > > Map does not contain a "getEntry" method. If it did, that would indeed > > be preferable. > > Do I understand correctly that the "resolveEntry" method which > you added behaves as my above "getEntry"? If so, the latter can > replace both "resolve" methods, for a (c)leaner API. > > > > Unless I'm missing a standard use-case, the specialized methods > > "closestFirst" and "farthestFirst" don't seem useful (and wasteful > > of computing resources: If iterating over the whole set, why would > > one want to start from some particular point?). > > > > Could you post this comment on the JIRA issue and we can continue the > > discussion there? > > Done. > > Regards, > Gilles > > - > To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org > For additional commands, e-mail: dev-h...@commons.apache.org > - To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
Re: [geometry] PointMap and PointSet
Hello. Le lun. 14 mars 2022 à 16:19, Matt Juntunen a écrit : > > Gilles, > > > it would be great to keep the tutorials/userguide in sync. > > Sounds good. I'll update the user guide in this PR. > > > I'm a little bit confused: Isn't it always the case that > getEntry(p).getKey() > will return the originally inserted (i.e. "canonical") point (i.e. not "p")? > > Map does not contain a "getEntry" method. If it did, that would indeed > be preferable. Do I understand correctly that the "resolveEntry" method which you added behaves as my above "getEntry"? If so, the latter can replace both "resolve" methods, for a (c)leaner API. > > Unless I'm missing a standard use-case, the specialized methods > "closestFirst" and "farthestFirst" don't seem useful (and wasteful > of computing resources: If iterating over the whole set, why would > one want to start from some particular point?). > > Could you post this comment on the JIRA issue and we can continue the > discussion there? Done. Regards, Gilles - To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
Re: [geometry] PointMap and PointSet
Gilles, > it would be great to keep the tutorials/userguide in sync. Sounds good. I'll update the user guide in this PR. > I'm a little bit confused: Isn't it always the case that getEntry(p).getKey() will return the originally inserted (i.e. "canonical") point (i.e. not "p")? Map does not contain a "getEntry" method. If it did, that would indeed be preferable. > Unless I'm missing a standard use-case, the specialized methods "closestFirst" and "farthestFirst" don't seem useful (and wasteful of computing resources: If iterating over the whole set, why would one want to start from some particular point?). Could you post this comment on the JIRA issue and we can continue the discussion there? Regards, Matt On Sun, Mar 13, 2022 at 11:25 AM Gilles Sadowski wrote: > > Hello Matt. > > Le dim. 13 mars 2022 à 15:41, Matt Juntunen > a écrit : > > > > Hello, > > > > > Is there a gentle introduction to how it works and/or the intended > > use cases? > > > > Not specifically. The implementations are used the same way as JDK > > Maps and Sets so usage should be very familiar. As far as the internal > > implementation details, I've tried to describe that in the javadocs > > for the implementing classes. > > > > One example use case is construction of meshes from a stream of > > triangles. This is used internally in > > o.a.c.geometry.euclidean.threed.mesh.SimpleTriangleMesh. Another use > > case is finding unique entries in a cloud of points, where many points > > are close but not exactly equal to each other. This case was actually > > posted on the user mailing list (I believe) way back when I started > > implementing this feature. > > I know; but as the code base provides more and more functionality > (thank you!) it would be great to keep the tutorials/userguide in sync. > A simple "How to..." is often enough (and faster than browsing the > Javadoc) in order to get at the most common usage. > > > > > > Does it entail issues about some use cases or applications that > > need this functionality? Or do they not generally care about that > > contract? > > If so, maybe this collection shouldn't implement the standard JDK > > interfaces (?). > > > > No, there shouldn't be any issues. java.util.TreeMap documents that > > it's behavior is well-defined and consistent even when a Comparator > > that doesn't match equals is given, such as > > String.CASE_INSENSITIVE_ORDER. This is the same sort of situation. The > > map/set is still quite useful even without the strict contract. > > > > > Where does the anticipation come from? > > > > The approach I used for helping to maintain somewhat balanced trees in > > Euclidean 2D and 3D and spherical 2D regardless of insertion order is > > not based on a well-known algorithm or paper since I was unable to > > find one. The literature on the subject seems to focus on situations > > where the inserted points are all known beforehand and can be inserted > > in a particular order. I did not want to enforce this condition on the > > API. What I ended up with is just an idea I had for tree balancing > > that seems to work pretty well. As such, I fully expect that there > > will be a better option discovered later on. > > IMHO, the above two Q & A are worth mentioning in the userguide. > The second especially may attract some user's attention who could > provide the missing info. [Of course, it should also appear at the > relevant places in the Javadoc.] > > > > > > I don't quite follow; which are the corresponding "non-canonical" > > accessors? > > > > My thought here is that there will be situations where a set of points > > is placed into a map/set and then these points are queried using > > values determined from some other source, such as through computations > > of some sort. > > Indeed. > > > These query points may vary from the originally inserted > > points by distances allowed by the Precision.DoubleEquivalence. In > > these cases, it's useful to be able to obtain the exact value of the > > originally inserted (i.e. "canonical") point. This is the purpose of > > the "resolve" methods. > > I'm a little bit confused: Isn't it always the case that > getEntry(p).getKey() > will return the originally inserted (i.e. "canonical") point (i.e. not "p")? > > Anyways, I'd suggest that this be illustrated in the userguide (linked > to a working application in "commons-geometry-examples"). > > > > > > Is there a notion of neighbours (as in: return the "n" entries that > > are closest to a given point)? > > > > I am picturing that functionality being implemented in a follow-up issue. > > [1] > > Thanks. > However, my impression is that the API should be more general: > ---CUT--- > public Iterable closestInRange(P point, double radius); > ---CUT--- > > Unless I'm missing a standard use-case, the specialized methods > "closestFirst" and "farthestFirst" don't seem useful (and wasteful > of computing resources: If iterating over the whole set, why would > one want to start from some
Re: [geometry] PointMap and PointSet
Hello Matt. Le dim. 13 mars 2022 à 15:41, Matt Juntunen a écrit : > > Hello, > > > Is there a gentle introduction to how it works and/or the intended > use cases? > > Not specifically. The implementations are used the same way as JDK > Maps and Sets so usage should be very familiar. As far as the internal > implementation details, I've tried to describe that in the javadocs > for the implementing classes. > > One example use case is construction of meshes from a stream of > triangles. This is used internally in > o.a.c.geometry.euclidean.threed.mesh.SimpleTriangleMesh. Another use > case is finding unique entries in a cloud of points, where many points > are close but not exactly equal to each other. This case was actually > posted on the user mailing list (I believe) way back when I started > implementing this feature. I know; but as the code base provides more and more functionality (thank you!) it would be great to keep the tutorials/userguide in sync. A simple "How to..." is often enough (and faster than browsing the Javadoc) in order to get at the most common usage. > > > Does it entail issues about some use cases or applications that > need this functionality? Or do they not generally care about that > contract? > If so, maybe this collection shouldn't implement the standard JDK > interfaces (?). > > No, there shouldn't be any issues. java.util.TreeMap documents that > it's behavior is well-defined and consistent even when a Comparator > that doesn't match equals is given, such as > String.CASE_INSENSITIVE_ORDER. This is the same sort of situation. The > map/set is still quite useful even without the strict contract. > > > Where does the anticipation come from? > > The approach I used for helping to maintain somewhat balanced trees in > Euclidean 2D and 3D and spherical 2D regardless of insertion order is > not based on a well-known algorithm or paper since I was unable to > find one. The literature on the subject seems to focus on situations > where the inserted points are all known beforehand and can be inserted > in a particular order. I did not want to enforce this condition on the > API. What I ended up with is just an idea I had for tree balancing > that seems to work pretty well. As such, I fully expect that there > will be a better option discovered later on. IMHO, the above two Q & A are worth mentioning in the userguide. The second especially may attract some user's attention who could provide the missing info. [Of course, it should also appear at the relevant places in the Javadoc.] > > > I don't quite follow; which are the corresponding "non-canonical" > accessors? > > My thought here is that there will be situations where a set of points > is placed into a map/set and then these points are queried using > values determined from some other source, such as through computations > of some sort. Indeed. > These query points may vary from the originally inserted > points by distances allowed by the Precision.DoubleEquivalence. In > these cases, it's useful to be able to obtain the exact value of the > originally inserted (i.e. "canonical") point. This is the purpose of > the "resolve" methods. I'm a little bit confused: Isn't it always the case that getEntry(p).getKey() will return the originally inserted (i.e. "canonical") point (i.e. not "p")? Anyways, I'd suggest that this be illustrated in the userguide (linked to a working application in "commons-geometry-examples"). > > > Is there a notion of neighbours (as in: return the "n" entries that > are closest to a given point)? > > I am picturing that functionality being implemented in a follow-up issue. [1] Thanks. However, my impression is that the API should be more general: ---CUT--- public Iterable closestInRange(P point, double radius); ---CUT--- Unless I'm missing a standard use-case, the specialized methods "closestFirst" and "farthestFirst" don't seem useful (and wasteful of computing resources: If iterating over the whole set, why would one want to start from some particular point?). Regards, Gilles > > Regards, > Matt > > [1] https://issues.apache.org/jira/browse/GEOMETRY-146 > > > [...] - To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
Re: [geometry] PointMap and PointSet
Hello,
> Is there a gentle introduction to how it works and/or the intended
use cases?
Not specifically. The implementations are used the same way as JDK
Maps and Sets so usage should be very familiar. As far as the internal
implementation details, I've tried to describe that in the javadocs
for the implementing classes.
One example use case is construction of meshes from a stream of
triangles. This is used internally in
o.a.c.geometry.euclidean.threed.mesh.SimpleTriangleMesh. Another use
case is finding unique entries in a cloud of points, where many points
are close but not exactly equal to each other. This case was actually
posted on the user mailing list (I believe) way back when I started
implementing this feature.
> Does it entail issues about some use cases or applications that
need this functionality? Or do they not generally care about that
contract?
If so, maybe this collection shouldn't implement the standard JDK
interfaces (?).
No, there shouldn't be any issues. java.util.TreeMap documents that
it's behavior is well-defined and consistent even when a Comparator
that doesn't match equals is given, such as
String.CASE_INSENSITIVE_ORDER. This is the same sort of situation. The
map/set is still quite useful even without the strict contract.
> Where does the anticipation come from?
The approach I used for helping to maintain somewhat balanced trees in
Euclidean 2D and 3D and spherical 2D regardless of insertion order is
not based on a well-known algorithm or paper since I was unable to
find one. The literature on the subject seems to focus on situations
where the inserted points are all known beforehand and can be inserted
in a particular order. I did not want to enforce this condition on the
API. What I ended up with is just an idea I had for tree balancing
that seems to work pretty well. As such, I fully expect that there
will be a better option discovered later on.
> I don't quite follow; which are the corresponding "non-canonical"
accessors?
My thought here is that there will be situations where a set of points
is placed into a map/set and then these points are queried using
values determined from some other source, such as through computations
of some sort. These query points may vary from the originally inserted
points by distances allowed by the Precision.DoubleEquivalence. In
these cases, it's useful to be able to obtain the exact value of the
originally inserted (i.e. "canonical") point. This is the purpose of
the "resolve" methods.
> Is there a notion of neighbours (as in: return the "n" entries that
are closest to a given point)?
I am picturing that functionality being implemented in a follow-up issue. [1]
Regards,
Matt
[1] https://issues.apache.org/jira/browse/GEOMETRY-146
On Sat, Mar 12, 2022 at 10:36 AM Gilles Sadowski wrote:
>
> Hello.
>
> Le ven. 11 mars 2022 à 16:18, Matt Juntunen
> a écrit :
> >
> > Hello,
> >
> > I recently posted a PR [1] for GEOMETRY-142 [2], which is for adding
> > PointMap and PointSet implementations. These are Map and Set
> > implementations specifically designed to use Points as keys.
>
> Is there a gentle introduction to how it works and/or the intended
> use cases?
>
> > They
> > support fuzzy key comparison, meaning that points do not have to be
> > exactly equal to each other in order to be considered equal by the
> > map/set. (Note that this means these types do not follow the strict
> > Map/Set contracts since they are not consistent with equals. This is
> > documented in the PointMap/PointSet javadocs.)
>
> Does it entail issues about some use cases or applications that
> need this functionality? Or do they not generally care about that
> contract?
> If so, maybe this collection shouldn't implement the standard JDK
> interfaces (?).
>
> > I've completely hidden
> > the implementation details from the public API
>
> Thanks.
>
> > since I anticipate
> > changes in the future with regard to the algorithms used.
>
> Where does the anticipation come from?
>
> > Instances
> > are created through factory classes in each space. Ex:
> >
> > PointMap map = EuclideanCollections.pointMap3D(precision);
> > PointSet set = SphericalCollections.pointSet2S(precision);
> >
> > Since fuzzy key comparison is used, I've added the following methods
> > to the interfaces to allow access to the exact, "canonical" version of
> > the key stored in the collection.
> >
> > PointMap {
> > // return the key corresponding to pt, or null if not found
> > P resolveKey(P pt);
> >
> > // return the map entry corresponding to pt, or null if not found
> > Map.Entry resolveEntry(P pt);
> > }
> >
> > PointSet {
> > // return the key corresponding to pt, or null if not found
> > P resolve(P pt);
> > }
>
> I don't quite follow; which are the corresponding "non-canonical"
> accessors?
>
> >
> > Reviews and comments are welcome.
>
> Is there a notion of neighbours (as in: return the "n" entries that
> are closest to a given point)?
>
> Regards,
> Gil
Re: [geometry] PointMap and PointSet
Hello.
Le ven. 11 mars 2022 à 16:18, Matt Juntunen
a écrit :
>
> Hello,
>
> I recently posted a PR [1] for GEOMETRY-142 [2], which is for adding
> PointMap and PointSet implementations. These are Map and Set
> implementations specifically designed to use Points as keys.
Is there a gentle introduction to how it works and/or the intended
use cases?
> They
> support fuzzy key comparison, meaning that points do not have to be
> exactly equal to each other in order to be considered equal by the
> map/set. (Note that this means these types do not follow the strict
> Map/Set contracts since they are not consistent with equals. This is
> documented in the PointMap/PointSet javadocs.)
Does it entail issues about some use cases or applications that
need this functionality? Or do they not generally care about that
contract?
If so, maybe this collection shouldn't implement the standard JDK
interfaces (?).
> I've completely hidden
> the implementation details from the public API
Thanks.
> since I anticipate
> changes in the future with regard to the algorithms used.
Where does the anticipation come from?
> Instances
> are created through factory classes in each space. Ex:
>
> PointMap map = EuclideanCollections.pointMap3D(precision);
> PointSet set = SphericalCollections.pointSet2S(precision);
>
> Since fuzzy key comparison is used, I've added the following methods
> to the interfaces to allow access to the exact, "canonical" version of
> the key stored in the collection.
>
> PointMap {
> // return the key corresponding to pt, or null if not found
> P resolveKey(P pt);
>
> // return the map entry corresponding to pt, or null if not found
> Map.Entry resolveEntry(P pt);
> }
>
> PointSet {
> // return the key corresponding to pt, or null if not found
> P resolve(P pt);
> }
I don't quite follow; which are the corresponding "non-canonical"
accessors?
>
> Reviews and comments are welcome.
Is there a notion of neighbours (as in: return the "n" entries that
are closest to a given point)?
Regards,
Gilles
>
> Regards,
> Matt Juntunen
>
>
> [1] https://github.com/apache/commons-geometry/pull/194
> [2] https://issues.apache.org/jira/projects/GEOMETRY/issues/GEOMETRY-142
>
-
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org
