Merge branch 'master' into 1.0-release
diff --git a/RELEASE-NOTES.txt b/RELEASE-NOTES.txt
index 552bda6..ba2e707 100644
--- a/RELEASE-NOTES.txt
+++ b/RELEASE-NOTES.txt
@@ -1,4 +1,58 @@
+ Apache Commons Geometry 1.0 RELEASE NOTES
+
+The Apache Commons Geometry team is pleased to announce the release of
+commons-geometry-parent-1.0
+
+The Apache Commons Geometry project provides geometric types and utilities.
+
+This is the first major release of Apache Commons Geometry.
+Apache Commons Geometry 1.0 contains the following library modules:
+ commons-geometry-core (requires Java 8+)
+ commons-geometry-euclidean (requires Java 8+)
+ commons-geometry-spherical (requires Java 8+)
+ commons-geometry-io-core (requires Java 8+)
+ commons-geometry-io-euclidean (requires Java 8+)
+
+Changes in this version include:
+
+New features:
+o GEOMETRY-118: Add coordinate-specific transform methods to AffineTransformMatrixXD classes,
+ e.g. "applyX", "applyY", "applyZ".
+o GEOMETRY-95: Add solid geometry tutorial.
+o GEOMETRY-120: Add SimpleTriangleMeshBuilder.addFace(int[]) method as alternative to
+ addFace(int, int, int).
+o GEOMETRY-117: Add shear methods to AffineTransformMatrix2D. Thanks to Christoph Läubrich.
+o GEOMETRY-119: Add VectorXD.normalizeOrNull() methods so that callers can detect normalization
+ failures without needing to catch an exception.
+o GEOMETRY-115: Add modules for IO functionality: commons-geometry-io-core,
+ commons-geometry-io-euclidean.
+o GEOMETRY-108: Add BoundaryList interface and implementation classes.
+
+Fixed Bugs:
+o GEOMETRY-116: Fix incorrect OSGi headers. Reported by Christoph Läubrich.
+
+Changes:
+o GEOMETRY-138: Do not use checked exceptions in IO modules.
+o GEOMETRY-13: Use Norms.EUCLIDEAN from Commons Numbers to compute 3D Euclidean norm values.
+o GEOMETRY-126: Replace VectorXD.linearCombination methods with VectorXD.Sum classes. Use
+ Sum class from Commons Numbers for computing internal linear combinations.
+o GEOMETRY-124: Replace DoublePrecisionContext with Precision.DoubleEquivalence from
+ Commons Numbers.
+o GEOMETRY-109: Rename the BoundarySourceXX.from() static factory methods to "of" to better
+ match the JDK's Stream.of() method.
+o GEOMETRY-103: Migrate unit tests to JUnit 5. Thanks to Arturo Bernal.
+
+
+For complete information on Apache Commons Geometry, including instructions on how to submit
+ bug reports, patches, or suggestions for improvement, see the Apache Commons Geometry
+ website:
+
+https://commons.apache.org/proper/commons-geometry/
+
+
+=============================================================================
+
Apache Commons Geometry 1.0-beta1 RELEASE NOTES
The Apache Commons Geometry team is pleased to announce the release of
@@ -22,5 +76,3 @@
reports, patches, or suggestions for improvement, see the Apache Commons Geometry website:
https://commons.apache.org/proper/commons-geometry/
-
-
diff --git a/commons-geometry-core/pom.xml b/commons-geometry-core/pom.xml
index 2521911..3b12615 100644
--- a/commons-geometry-core/pom.xml
+++ b/commons-geometry-core/pom.xml
@@ -23,7 +23,7 @@
<parent>
<groupId>org.apache.commons</groupId>
<artifactId>commons-geometry-parent</artifactId>
- <version>1.0-SNAPSHOT</version>
+ <version>1.0</version>
</parent>
<artifactId>commons-geometry-core</artifactId>
diff --git a/commons-geometry-core/src/site/site.xml b/commons-geometry-core/src/site/site.xml
index d9d4ce5..7adbb0a 100644
--- a/commons-geometry-core/src/site/site.xml
+++ b/commons-geometry-core/src/site/site.xml
@@ -28,8 +28,8 @@
<item name="Overview" href="/index.html"/>
<item name="Latest API docs (development)"
href="apidocs/index.html"/>
- <!-- <item name="Javadoc (1.0 release)"
- href="https://commons.apache.org/geometry/commons-geometry-core/javadocs/api-1.0/index.html"/> -->
+ <item name="Javadoc (1.0 release)"
+ href="https://commons.apache.org/geometry/commons-geometry-core/javadocs/api-1.0/index.html"/>
</menu>
<head>
diff --git a/commons-geometry-enclosing/CONTRIBUTING.md b/commons-geometry-enclosing/CONTRIBUTING.md
deleted file mode 100644
index dad0a8d..0000000
--- a/commons-geometry-enclosing/CONTRIBUTING.md
+++ /dev/null
@@ -1,115 +0,0 @@
-<!---
- Licensed to the Apache Software Foundation (ASF) under one or more
- contributor license agreements. See the NOTICE file distributed with
- this work for additional information regarding copyright ownership.
- The ASF licenses this file to You under the Apache License, Version 2.0
- (the "License"); you may not use this file except in compliance with
- the License. You may obtain a copy of the License at
-
- http://www.apache.org/licenses/LICENSE-2.0
-
- Unless required by applicable law or agreed to in writing, software
- distributed under the License is distributed on an "AS IS" BASIS,
- WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- See the License for the specific language governing permissions and
- limitations under the License.
--->
-<!---
- +======================================================================+
- |**** ****|
- |**** THIS FILE IS GENERATED BY THE COMMONS BUILD PLUGIN ****|
- |**** DO NOT EDIT DIRECTLY ****|
- |**** ****|
- +======================================================================+
- | TEMPLATE FILE: contributing-md-template.md |
- | commons-build-plugin/trunk/src/main/resources/commons-xdoc-templates |
- +======================================================================+
- | |
- | 1) Re-generate using: mvn commons-build:contributing-md |
- | |
- | 2) Set the following properties in the component's pom: |
- | - commons.jira.id (required, alphabetic, upper case) |
- | |
- | 3) Example Properties |
- | |
- | <properties> |
- | <commons.jira.id>MATH</commons.jira.id> |
- | </properties> |
- | |
- +======================================================================+
---->
-Contributing to Apache Commons Geometry Enclosing
-======================
-
-You have found a bug or you have an idea for a cool new feature? Contributing code is a great way to give something back to
-the open source community. Before you dig right into the code there are a few guidelines that we need contributors to
-follow so that we can have a chance of keeping on top of things.
-
-Getting Started
----------------
-
-+ Make sure you have a [JIRA account](https://issues.apache.org/jira/).
-+ Make sure you have a [GitHub account](https://github.com/signup/free).
-+ If you're planning to implement a new feature it makes sense to discuss your changes on the [dev list](https://commons.apache.org/mail-lists.html) first. This way you can make sure you're not wasting your time on something that isn't considered to be in Apache Commons Geometry Enclosing's scope.
-+ Submit a [Jira Ticket][jira] for your issue, assuming one does not already exist.
- + Clearly describe the issue including steps to reproduce when it is a bug.
- + Make sure you fill in the earliest version that you know has the issue.
-+ Find the corresponding [repository on GitHub](https://github.com/apache/?query=commons-),
-[fork](https://help.github.com/articles/fork-a-repo/) and check out your forked repository.
-
-Making Changes
---------------
-
-+ Create a _topic branch_ for your isolated work.
- * Usually you should base your branch on the `master` or `trunk` branch.
- * A good topic branch name can be the JIRA bug id plus a keyword, e.g. `GEOMETRY-123-InputStream`.
- * If you have submitted multiple JIRA issues, try to maintain separate branches and pull requests.
-+ Make commits of logical units.
- * Make sure your commit messages are meaningful and in the proper format. Your commit message should contain the key of the JIRA issue.
- * e.g. `GEOMETRY-123: Close input stream earlier`
-+ Respect the original code style:
- + Only use spaces for indentation.
- + Create minimal diffs - disable _On Save_ actions like _Reformat Source Code_ or _Organize Imports_. If you feel the source code should be reformatted create a separate PR for this change first.
- + Check for unnecessary whitespace with `git diff` -- check before committing.
-+ Make sure you have added the necessary tests for your changes, typically in `src/test/java`.
-+ Run all the tests with `mvn clean verify` to assure nothing else was accidentally broken.
-
-Making Trivial Changes
-----------------------
-
-The JIRA tickets are used to generate the changelog for the next release.
-
-For changes of a trivial nature to comments and documentation, it is not always necessary to create a new ticket in JIRA.
-In this case, it is appropriate to start the first line of a commit with '(doc)' instead of a ticket number.
-
-
-Submitting Changes
-------------------
-
-+ Sign and submit the Apache [Contributor License Agreement][cla] if you haven't already.
- * Note that small patches & typical bug fixes do not require a CLA as
- clause 5 of the [Apache License](https://www.apache.org/licenses/LICENSE-2.0.html#contributions)
- covers them.
-+ Push your changes to a topic branch in your fork of the repository.
-+ Submit a _Pull Request_ to the corresponding repository in the `apache` organization.
- * Verify _Files Changed_ shows only your intended changes and does not
- include additional files like `target/*.class`
-+ Update your JIRA ticket and include a link to the pull request in the ticket.
-
-If you prefer to not use GitHub, then you can instead use
-`git format-patch` (or `svn diff`) and attach the patch file to the JIRA issue.
-
-
-Additional Resources
---------------------
-
-+ [Contributing patches](https://commons.apache.org/patches.html)
-+ [Apache Commons Geometry Enclosing JIRA project page][jira]
-+ [Contributor License Agreement][cla]
-+ [General GitHub documentation](https://help.github.com/)
-+ [GitHub pull request documentation](https://help.github.com/articles/creating-a-pull-request/)
-+ [Apache Commons Twitter Account](https://twitter.com/ApacheCommons)
-+ `#apache-commons` IRC channel on `irc.freenode.net`
-
-[cla]:https://www.apache.org/licenses/#clas
-[jira]:https://issues.apache.org/jira/browse/GEOMETRY
diff --git a/commons-geometry-enclosing/LICENSE.txt b/commons-geometry-enclosing/LICENSE.txt
deleted file mode 100644
index 261eeb9..0000000
--- a/commons-geometry-enclosing/LICENSE.txt
+++ /dev/null
@@ -1,201 +0,0 @@
- Apache License
- Version 2.0, January 2004
- http://www.apache.org/licenses/
-
- TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION
-
- 1. Definitions.
-
- "License" shall mean the terms and conditions for use, reproduction,
- and distribution as defined by Sections 1 through 9 of this document.
-
- "Licensor" shall mean the copyright owner or entity authorized by
- the copyright owner that is granting the License.
-
- "Legal Entity" shall mean the union of the acting entity and all
- other entities that control, are controlled by, or are under common
- control with that entity. For the purposes of this definition,
- "control" means (i) the power, direct or indirect, to cause the
- direction or management of such entity, whether by contract or
- otherwise, or (ii) ownership of fifty percent (50%) or more of the
- outstanding shares, or (iii) beneficial ownership of such entity.
-
- "You" (or "Your") shall mean an individual or Legal Entity
- exercising permissions granted by this License.
-
- "Source" form shall mean the preferred form for making modifications,
- including but not limited to software source code, documentation
- source, and configuration files.
-
- "Object" form shall mean any form resulting from mechanical
- transformation or translation of a Source form, including but
- not limited to compiled object code, generated documentation,
- and conversions to other media types.
-
- "Work" shall mean the work of authorship, whether in Source or
- Object form, made available under the License, as indicated by a
- copyright notice that is included in or attached to the work
- (an example is provided in the Appendix below).
-
- "Derivative Works" shall mean any work, whether in Source or Object
- form, that is based on (or derived from) the Work and for which the
- editorial revisions, annotations, elaborations, or other modifications
- represent, as a whole, an original work of authorship. For the purposes
- of this License, Derivative Works shall not include works that remain
- separable from, or merely link (or bind by name) to the interfaces of,
- the Work and Derivative Works thereof.
-
- "Contribution" shall mean any work of authorship, including
- the original version of the Work and any modifications or additions
- to that Work or Derivative Works thereof, that is intentionally
- submitted to Licensor for inclusion in the Work by the copyright owner
- or by an individual or Legal Entity authorized to submit on behalf of
- the copyright owner. For the purposes of this definition, "submitted"
- means any form of electronic, verbal, or written communication sent
- to the Licensor or its representatives, including but not limited to
- communication on electronic mailing lists, source code control systems,
- and issue tracking systems that are managed by, or on behalf of, the
- Licensor for the purpose of discussing and improving the Work, but
- excluding communication that is conspicuously marked or otherwise
- designated in writing by the copyright owner as "Not a Contribution."
-
- "Contributor" shall mean Licensor and any individual or Legal Entity
- on behalf of whom a Contribution has been received by Licensor and
- subsequently incorporated within the Work.
-
- 2. Grant of Copyright License. Subject to the terms and conditions of
- this License, each Contributor hereby grants to You a perpetual,
- worldwide, non-exclusive, no-charge, royalty-free, irrevocable
- copyright license to reproduce, prepare Derivative Works of,
- publicly display, publicly perform, sublicense, and distribute the
- Work and such Derivative Works in Source or Object form.
-
- 3. Grant of Patent License. Subject to the terms and conditions of
- this License, each Contributor hereby grants to You a perpetual,
- worldwide, non-exclusive, no-charge, royalty-free, irrevocable
- (except as stated in this section) patent license to make, have made,
- use, offer to sell, sell, import, and otherwise transfer the Work,
- where such license applies only to those patent claims licensable
- by such Contributor that are necessarily infringed by their
- Contribution(s) alone or by combination of their Contribution(s)
- with the Work to which such Contribution(s) was submitted. If You
- institute patent litigation against any entity (including a
- cross-claim or counterclaim in a lawsuit) alleging that the Work
- or a Contribution incorporated within the Work constitutes direct
- or contributory patent infringement, then any patent licenses
- granted to You under this License for that Work shall terminate
- as of the date such litigation is filed.
-
- 4. Redistribution. You may reproduce and distribute copies of the
- Work or Derivative Works thereof in any medium, with or without
- modifications, and in Source or Object form, provided that You
- meet the following conditions:
-
- (a) You must give any other recipients of the Work or
- Derivative Works a copy of this License; and
-
- (b) You must cause any modified files to carry prominent notices
- stating that You changed the files; and
-
- (c) You must retain, in the Source form of any Derivative Works
- that You distribute, all copyright, patent, trademark, and
- attribution notices from the Source form of the Work,
- excluding those notices that do not pertain to any part of
- the Derivative Works; and
-
- (d) If the Work includes a "NOTICE" text file as part of its
- distribution, then any Derivative Works that You distribute must
- include a readable copy of the attribution notices contained
- within such NOTICE file, excluding those notices that do not
- pertain to any part of the Derivative Works, in at least one
- of the following places: within a NOTICE text file distributed
- as part of the Derivative Works; within the Source form or
- documentation, if provided along with the Derivative Works; or,
- within a display generated by the Derivative Works, if and
- wherever such third-party notices normally appear. The contents
- of the NOTICE file are for informational purposes only and
- do not modify the License. You may add Your own attribution
- notices within Derivative Works that You distribute, alongside
- or as an addendum to the NOTICE text from the Work, provided
- that such additional attribution notices cannot be construed
- as modifying the License.
-
- You may add Your own copyright statement to Your modifications and
- may provide additional or different license terms and conditions
- for use, reproduction, or distribution of Your modifications, or
- for any such Derivative Works as a whole, provided Your use,
- reproduction, and distribution of the Work otherwise complies with
- the conditions stated in this License.
-
- 5. Submission of Contributions. Unless You explicitly state otherwise,
- any Contribution intentionally submitted for inclusion in the Work
- by You to the Licensor shall be under the terms and conditions of
- this License, without any additional terms or conditions.
- Notwithstanding the above, nothing herein shall supersede or modify
- the terms of any separate license agreement you may have executed
- with Licensor regarding such Contributions.
-
- 6. Trademarks. This License does not grant permission to use the trade
- names, trademarks, service marks, or product names of the Licensor,
- except as required for reasonable and customary use in describing the
- origin of the Work and reproducing the content of the NOTICE file.
-
- 7. Disclaimer of Warranty. Unless required by applicable law or
- agreed to in writing, Licensor provides the Work (and each
- Contributor provides its Contributions) on an "AS IS" BASIS,
- WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
- implied, including, without limitation, any warranties or conditions
- of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A
- PARTICULAR PURPOSE. You are solely responsible for determining the
- appropriateness of using or redistributing the Work and assume any
- risks associated with Your exercise of permissions under this License.
-
- 8. Limitation of Liability. In no event and under no legal theory,
- whether in tort (including negligence), contract, or otherwise,
- unless required by applicable law (such as deliberate and grossly
- negligent acts) or agreed to in writing, shall any Contributor be
- liable to You for damages, including any direct, indirect, special,
- incidental, or consequential damages of any character arising as a
- result of this License or out of the use or inability to use the
- Work (including but not limited to damages for loss of goodwill,
- work stoppage, computer failure or malfunction, or any and all
- other commercial damages or losses), even if such Contributor
- has been advised of the possibility of such damages.
-
- 9. Accepting Warranty or Additional Liability. While redistributing
- the Work or Derivative Works thereof, You may choose to offer,
- and charge a fee for, acceptance of support, warranty, indemnity,
- or other liability obligations and/or rights consistent with this
- License. However, in accepting such obligations, You may act only
- on Your own behalf and on Your sole responsibility, not on behalf
- of any other Contributor, and only if You agree to indemnify,
- defend, and hold each Contributor harmless for any liability
- incurred by, or claims asserted against, such Contributor by reason
- of your accepting any such warranty or additional liability.
-
- END OF TERMS AND CONDITIONS
-
- APPENDIX: How to apply the Apache License to your work.
-
- To apply the Apache License to your work, attach the following
- boilerplate notice, with the fields enclosed by brackets "[]"
- replaced with your own identifying information. (Don't include
- the brackets!) The text should be enclosed in the appropriate
- comment syntax for the file format. We also recommend that a
- file or class name and description of purpose be included on the
- same "printed page" as the copyright notice for easier
- identification within third-party archives.
-
- Copyright [yyyy] [name of copyright owner]
-
- Licensed under the Apache License, Version 2.0 (the "License");
- you may not use this file except in compliance with the License.
- You may obtain a copy of the License at
-
- http://www.apache.org/licenses/LICENSE-2.0
-
- Unless required by applicable law or agreed to in writing, software
- distributed under the License is distributed on an "AS IS" BASIS,
- WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- See the License for the specific language governing permissions and
- limitations under the License.
diff --git a/commons-geometry-enclosing/NOTICE.txt b/commons-geometry-enclosing/NOTICE.txt
deleted file mode 100644
index 8d9849f..0000000
--- a/commons-geometry-enclosing/NOTICE.txt
+++ /dev/null
@@ -1,6 +0,0 @@
-Apache Commons Geometry
-Copyright 2020 The Apache Software Foundation
-
-This product includes software developed at
-The Apache Software Foundation (http://www.apache.org/).
-
diff --git a/commons-geometry-enclosing/README.md b/commons-geometry-enclosing/README.md
deleted file mode 100644
index 27db2f6..0000000
--- a/commons-geometry-enclosing/README.md
+++ /dev/null
@@ -1,105 +0,0 @@
-<!---
- Licensed to the Apache Software Foundation (ASF) under one or more
- contributor license agreements. See the NOTICE file distributed with
- this work for additional information regarding copyright ownership.
- The ASF licenses this file to You under the Apache License, Version 2.0
- (the "License"); you may not use this file except in compliance with
- the License. You may obtain a copy of the License at
-
- http://www.apache.org/licenses/LICENSE-2.0
-
- Unless required by applicable law or agreed to in writing, software
- distributed under the License is distributed on an "AS IS" BASIS,
- WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- See the License for the specific language governing permissions and
- limitations under the License.
--->
-<!---
- +======================================================================+
- |**** ****|
- |**** THIS FILE IS GENERATED BY THE COMMONS BUILD PLUGIN ****|
- |**** DO NOT EDIT DIRECTLY ****|
- |**** ****|
- +======================================================================+
- | TEMPLATE FILE: readme-md-template.md |
- | commons-build-plugin/trunk/src/main/resources/commons-xdoc-templates |
- +======================================================================+
- | |
- | 1) Re-generate using: mvn commons:readme-md |
- | |
- | 2) Set the following properties in the component's pom: |
- | - commons.componentid (required, alphabetic, lower case) |
- | - commons.release.version (required) |
- | |
- | 3) Example Properties |
- | |
- | <properties> |
- | <commons.componentid>math</commons.componentid> |
- | <commons.release.version>1.2</commons.release.version> |
- | </properties> |
- | |
- +======================================================================+
---->
-Apache Commons Geometry Enclosing
-===================
-
-[](https://travis-ci.org/apache/commons-geometry-enclosing)
-[](https://coveralls.io/r/apache/commons-geometry-enclosing)
-[](https://maven-badges.herokuapp.com/maven-central/org.apache.commons/commons-geometry-enclosing/)
-[](http://www.apache.org/licenses/LICENSE-2.0.html)
-
-Algorithms for computing enclosing balls.
-
-Documentation
--------------
-
-More information can be found on the [Apache Commons Geometry Enclosing homepage](https://commons.apache.org/proper/commons-geometry).
-The [JavaDoc](https://commons.apache.org/proper/commons-geometry/javadocs/api-release) can be browsed.
-Questions related to the usage of Apache Commons Geometry Enclosing should be posted to the [user mailing list][ml].
-
-Where can I get the latest release?
------------------------------------
-You can download source and binaries from our [download page](https://commons.apache.org/proper/commons-geometry/download_geometry.cgi).
-
-Alternatively you can pull it from the central Maven repositories:
-
-```xml
-<dependency>
- <groupId>org.apache.commons</groupId>
- <artifactId>commons-geometry-enclosing</artifactId>
- <version>1.0-beta1</version>
-</dependency>
-```
-
-Contributing
-------------
-
-We accept Pull Requests via GitHub. The [developer mailing list][ml] is the main channel of communication for contributors.
-There are some guidelines which will make applying PRs easier for us:
-+ No tabs! Please use spaces for indentation.
-+ Respect the code style.
-+ Create minimal diffs - disable on save actions like reformat source code or organize imports. If you feel the source code should be reformatted create a separate PR for this change.
-+ Provide JUnit tests for your changes and make sure your changes don't break any existing tests by running ```mvn clean test```.
-
-If you plan to contribute on a regular basis, please consider filing a [contributor license agreement](https://www.apache.org/licenses/#clas).
-You can learn more about contributing via GitHub in our [contribution guidelines](CONTRIBUTING.md).
-
-License
--------
-This code is under the [Apache Licence v2](https://www.apache.org/licenses/LICENSE-2.0).
-
-See the `NOTICE.txt` file for required notices and attributions.
-
-Donations
----------
-You like Apache Commons Geometry Enclosing? Then [donate back to the ASF](https://www.apache.org/foundation/contributing.html) to support the development.
-
-Additional Resources
---------------------
-
-+ [Apache Commons Homepage](https://commons.apache.org/)
-+ [Apache Issue Tracker (JIRA)](https://issues.apache.org/jira/browse/GEOMETRY)
-+ [Apache Commons Twitter Account](https://twitter.com/ApacheCommons)
-+ `#apache-commons` IRC channel on `irc.freenode.org`
-
-[ml]:https://commons.apache.org/mail-lists.html
diff --git a/commons-geometry-enclosing/pom.xml b/commons-geometry-enclosing/pom.xml
deleted file mode 100644
index 9b0ed2a..0000000
--- a/commons-geometry-enclosing/pom.xml
+++ /dev/null
@@ -1,102 +0,0 @@
-<?xml version="1.0"?>
-<!--
- Licensed to the Apache Software Foundation (ASF) under one or more
- contributor license agreements. See the NOTICE file distributed with
- this work for additional information regarding copyright ownership.
- The ASF licenses this file to You under the Apache License, Version 2.0
- (the "License"); you may not use this file except in compliance with
- the License. You may obtain a copy of the License at
-
- http://www.apache.org/licenses/LICENSE-2.0
-
- Unless required by applicable law or agreed to in writing, software
- distributed under the License is distributed on an "AS IS" BASIS,
- WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- See the License for the specific language governing permissions and
- limitations under the License.
--->
-<project xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd"
- xmlns="http://maven.apache.org/POM/4.0.0"
- xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance">
- <modelVersion>4.0.0</modelVersion>
-
- <parent>
- <groupId>org.apache.commons</groupId>
- <artifactId>commons-geometry-parent</artifactId>
- <version>1.0-SNAPSHOT</version>
- </parent>
-
- <artifactId>commons-geometry-enclosing</artifactId>
- <name>Apache Commons Geometry Enclosing</name>
-
- <description>Algorithms for computing enclosing balls.</description>
-
- <properties>
- <!-- OSGi -->
- <commons.osgi.symbolicName>org.apache.commons.geometry.enclosing</commons.osgi.symbolicName>
- <commons.osgi.export>org.apache.commons.geometry.enclosing.*</commons.osgi.export>
- <!-- Java 9+ -->
- <commons.automatic.module.name>org.apache.commons.geometry.enclosing</commons.automatic.module.name>
- <!-- Workaround to avoid duplicating config files. -->
- <geometry.parent.dir>${basedir}/..</geometry.parent.dir>
- </properties>
-
- <dependencies>
- <dependency>
- <groupId>org.apache.commons</groupId>
- <artifactId>commons-geometry-core</artifactId>
- <version>${project.version}</version>
- </dependency>
- <dependency>
- <groupId>org.apache.commons</groupId>
- <artifactId>commons-geometry-euclidean</artifactId>
- <version>${project.version}</version>
- </dependency>
-
- <dependency>
- <groupId>org.apache.commons</groupId>
- <artifactId>commons-numbers-fraction</artifactId>
- </dependency>
-
- <dependency>
- <groupId>org.apache.commons</groupId>
- <artifactId>commons-geometry-core</artifactId>
- <version>${project.version}</version>
- <classifier>tests</classifier>
- <type>test-jar</type>
- <scope>test</scope>
- </dependency>
-
- <dependency>
- <groupId>org.apache.commons</groupId>
- <artifactId>commons-geometry-euclidean</artifactId>
- <version>${project.version}</version>
- <classifier>tests</classifier>
- <type>test-jar</type>
- <scope>test</scope>
- </dependency>
-
- <dependency>
- <groupId>org.apache.commons</groupId>
- <artifactId>commons-rng-client-api</artifactId>
- <scope>test</scope>
- </dependency>
- <dependency>
- <groupId>org.apache.commons</groupId>
- <artifactId>commons-rng-simple</artifactId>
- <scope>test</scope>
- </dependency>
- <dependency>
- <groupId>org.apache.commons</groupId>
- <artifactId>commons-rng-sampling</artifactId>
- <scope>test</scope>
- </dependency>
- <!-- testing -->
- <dependency>
- <groupId>org.junit.jupiter</groupId>
- <artifactId>junit-jupiter</artifactId>
- <scope>test</scope>
- </dependency>
- </dependencies>
-
-</project>
diff --git a/commons-geometry-enclosing/src/main/java/org/apache/commons/geometry/enclosing/Encloser.java b/commons-geometry-enclosing/src/main/java/org/apache/commons/geometry/enclosing/Encloser.java
deleted file mode 100644
index ca5bf38..0000000
--- a/commons-geometry-enclosing/src/main/java/org/apache/commons/geometry/enclosing/Encloser.java
+++ /dev/null
@@ -1,34 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements. See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-package org.apache.commons.geometry.enclosing;
-
-import org.apache.commons.geometry.core.Point;
-
-/** Interface for algorithms computing enclosing balls.
- * @param <P> Point type.
- * @see EnclosingBall
- */
-public interface Encloser<P extends Point<P>> {
-
- /** Find a ball enclosing a list of points.
- * @param points points to enclose
- * @return enclosing ball
- * @throws IllegalArgumentException if the argument does not contain any points
- */
- EnclosingBall<P> enclose(Iterable<P> points);
-
-}
diff --git a/commons-geometry-enclosing/src/main/java/org/apache/commons/geometry/enclosing/EnclosingBall.java b/commons-geometry-enclosing/src/main/java/org/apache/commons/geometry/enclosing/EnclosingBall.java
deleted file mode 100644
index a7fb9bb..0000000
--- a/commons-geometry-enclosing/src/main/java/org/apache/commons/geometry/enclosing/EnclosingBall.java
+++ /dev/null
@@ -1,118 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements. See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-package org.apache.commons.geometry.enclosing;
-
-import java.util.ArrayList;
-import java.util.Collection;
-import java.util.Collections;
-import java.util.List;
-
-import org.apache.commons.geometry.core.Point;
-import org.apache.commons.numbers.core.Precision;
-
-/** This class represents a ball enclosing some points.
- * @param <P> Point type.
- * @see Point
- * @see Encloser
- */
-public class EnclosingBall<P extends Point<P>> {
- /** Center of the ball. */
- private final P center;
-
- /** Radius of the ball. */
- private final double radius;
-
- /** Support points used to define the ball. */
- private final List<P> support;
-
- /** Construct an enclosing ball defined by a collection of support points. Callers are responsible
- * for ensuring that the given points lie inside the ball. No validation is performed.
- * @param center center of the ball
- * @param radius radius of the ball
- * @param support support points used to define the ball
- */
- public EnclosingBall(final P center, final double radius, final Collection<P> support) {
- this.center = center;
- this.radius = radius;
- this.support = Collections.unmodifiableList(new ArrayList<>(support));
- }
-
- /** Get the center of the ball.
- * @return center of the ball
- */
- public P getCenter() {
- return center;
- }
-
- /** Get the radius of the ball.
- * @return radius of the ball (can be negative if the ball is empty)
- */
- public double getRadius() {
- return radius;
- }
-
- /** Get the support points used to define the ball.
- * @return support points used to define the ball
- */
- public List<P> getSupport() {
- return support;
- }
-
- /** Get the number of support points used to define the ball.
- * @return number of support points used to define the ball
- */
- public int getSupportSize() {
- return support.size();
- }
-
- /** Check if a point is within the ball or on the boundary. True is returned if the
- * distance from the center of the ball to the given point is strictly less than
- * or equal to the ball radius.
- * @param point point to test
- * @return true if the point is within the ball or on the boundary
- */
- public boolean contains(final P point) {
- return point.distance(center) <= radius;
- }
-
- /** Check if a point is within the ball or on the boundary, using the given precision
- * context for floating point comparison. True is returned if the distance from the
- * center of the ball to the given point is less than or equal to the ball radius
- * as evaluated by the precision context.
- * @param point point to test
- * @param precision precision context to use for floating point comparisons
- * @return true if the point is within the ball or on the boundary as evaluated by
- * the precision context
- */
- public boolean contains(final P point, final Precision.DoubleEquivalence precision) {
- return precision.lte(point.distance(center), radius);
- }
-
- /** {@inheritDoc} */
- @Override
- public String toString() {
- final StringBuilder sb = new StringBuilder();
- sb.append(getClass().getSimpleName())
- .append("[center= ")
- .append(getCenter())
- .append(", radius= ")
- .append(getRadius())
- .append(']');
-
- return sb.toString();
- }
-}
diff --git a/commons-geometry-enclosing/src/main/java/org/apache/commons/geometry/enclosing/SupportBallGenerator.java b/commons-geometry-enclosing/src/main/java/org/apache/commons/geometry/enclosing/SupportBallGenerator.java
deleted file mode 100644
index ad2631a..0000000
--- a/commons-geometry-enclosing/src/main/java/org/apache/commons/geometry/enclosing/SupportBallGenerator.java
+++ /dev/null
@@ -1,39 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements. See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-package org.apache.commons.geometry.enclosing;
-
-import java.util.List;
-
-import org.apache.commons.geometry.core.Point;
-
-/** Interface for generating balls based on support points.
- * <p>
- * This generator is used in the {@link WelzlEncloser Emo Welzl} algorithm
- * and its derivatives.
- * </p>
- * @param <P> Point type.
- * @see EnclosingBall
- */
-public interface SupportBallGenerator<P extends Point<P>> {
-
- /** Create a ball whose boundary lies on prescribed support points.
- * @param support support points (may be empty)
- * @return ball whose boundary lies on the prescribed support points
- */
- EnclosingBall<P> ballOnSupport(List<P> support);
-
-}
diff --git a/commons-geometry-enclosing/src/main/java/org/apache/commons/geometry/enclosing/WelzlEncloser.java b/commons-geometry-enclosing/src/main/java/org/apache/commons/geometry/enclosing/WelzlEncloser.java
deleted file mode 100755
index d246f46..0000000
--- a/commons-geometry-enclosing/src/main/java/org/apache/commons/geometry/enclosing/WelzlEncloser.java
+++ /dev/null
@@ -1,170 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements. See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-package org.apache.commons.geometry.enclosing;
-
-import java.util.ArrayList;
-import java.util.List;
-
-import org.apache.commons.geometry.core.Point;
-import org.apache.commons.geometry.core.internal.GeometryInternalError;
-import org.apache.commons.numbers.core.Precision;
-
-/** Class implementing Emo Welzl's algorithm to find the smallest enclosing ball in linear time.
- * <p>
- * The class implements the algorithm described in paper <a
- * href="http://www.inf.ethz.ch/personal/emo/PublFiles/SmallEnclDisk_LNCS555_91.pdf">Smallest
- * Enclosing Disks (Balls and Ellipsoids)</a> by Emo Welzl, Lecture Notes in Computer Science
- * 555 (1991) 359-370. The pivoting improvement published in the paper <a
- * href="http://www.inf.ethz.ch/personal/gaertner/texts/own_work/esa99_final.pdf">Fast and
- * Robust Smallest Enclosing Balls</a>, by Bernd Gärtner and further modified in
- * paper <a
- * href="http://www.idt.mdh.se/kurser/ct3340/ht12/MINICONFERENCE/FinalPapers/ircse12_submission_30.pdf">
- * Efficient Computation of Smallest Enclosing Balls in Three Dimensions</a> by Linus Källberg
- * to avoid performing local copies of data have been included.
- * </p>
- * @param <P> Point type.
- */
-public class WelzlEncloser<P extends Point<P>> implements Encloser<P> {
-
- /** Precision context used to compare floating point numbers. */
- private final Precision.DoubleEquivalence precision;
-
- /** Object used to generate balls from support points. */
- private final SupportBallGenerator<P> generator;
-
- /** Simple constructor.
- * @param generator generator for balls on support
- * @param precision precision context used to compare floating point values
- */
- public WelzlEncloser(final SupportBallGenerator<P> generator, final Precision.DoubleEquivalence precision) {
- this.generator = generator;
- this.precision = precision;
- }
-
- /** {@inheritDoc} */
- @Override
- public EnclosingBall<P> enclose(final Iterable<P> points) {
-
- if (points == null || !points.iterator().hasNext()) {
- throw new IllegalArgumentException("Unable to generate enclosing ball: no points given");
- }
-
- // Emo Welzl algorithm with Bernd Gärtner and Linus Källberg improvements
- return pivotingBall(points);
- }
-
- /** Compute enclosing ball using Gärtner's pivoting heuristic.
- * @param points points to be enclosed
- * @return enclosing ball
- */
- private EnclosingBall<P> pivotingBall(final Iterable<P> points) {
-
- final P first = points.iterator().next();
- final List<P> extreme = new ArrayList<>(first.getDimension() + 1);
- final List<P> support = new ArrayList<>(first.getDimension() + 1);
-
- // start with only first point selected as a candidate support
- extreme.add(first);
- EnclosingBall<P> ball = moveToFrontBall(extreme, extreme.size(), support);
-
- while (true) {
-
- // select the point farthest to current ball
- final P farthest = selectFarthest(points, ball);
-
- if (ball.contains(farthest, precision)) {
- // we have found a ball containing all points
- return ball;
- }
-
- // recurse search, restricted to the small subset containing support and farthest point
- support.clear();
- support.add(farthest);
- final EnclosingBall<P> savedBall = ball;
- ball = moveToFrontBall(extreme, extreme.size(), support);
- if (precision.lt(ball.getRadius(), savedBall.getRadius())) {
- // this should never happen
- throw new GeometryInternalError();
- }
-
- // it was an interesting point, move it to the front
- // according to Gärtner's heuristic
- extreme.add(0, farthest);
-
- // prune the least interesting points
- extreme.subList(ball.getSupportSize(), extreme.size()).clear();
- }
- }
-
- /** Compute enclosing ball using Welzl's move to front heuristic.
- * @param extreme subset of extreme points
- * @param nbExtreme number of extreme points to consider
- * @param support points that must belong to the ball support
- * @return enclosing ball, for the extreme subset only
- */
- private EnclosingBall<P> moveToFrontBall(final List<P> extreme, final int nbExtreme,
- final List<P> support) {
- // create a new ball on the prescribed support
- EnclosingBall<P> ball = generator.ballOnSupport(support);
-
- if (ball.getSupportSize() <= ball.getCenter().getDimension()) {
-
- for (int i = 0; i < nbExtreme; ++i) {
- final P pi = extreme.get(i);
- if (!ball.contains(pi, precision)) {
-
- // we have found an outside point,
- // enlarge the ball by adding it to the support
- support.add(pi);
- ball = moveToFrontBall(extreme, i, support);
- support.remove(support.size() - 1);
-
- // it was an interesting point, move it to the front
- // according to Welzl's heuristic
- for (int j = i; j > 0; --j) {
- extreme.set(j, extreme.get(j - 1));
- }
- extreme.set(0, pi);
- }
- }
- }
-
- return ball;
- }
-
- /** Select the point farthest to the current ball.
- * @param points points to be enclosed
- * @param ball current ball
- * @return farthest point
- */
- private P selectFarthest(final Iterable<P> points, final EnclosingBall<P> ball) {
-
- final P center = ball.getCenter();
- P farthest = null;
- double dMax = -1.0;
-
- for (final P point : points) {
- final double d = point.distance(center);
- if (d > dMax) {
- farthest = point;
- dMax = d;
- }
- }
-
- return farthest;
- }
-}
diff --git a/commons-geometry-enclosing/src/main/java/org/apache/commons/geometry/enclosing/euclidean/threed/SphereGenerator.java b/commons-geometry-enclosing/src/main/java/org/apache/commons/geometry/enclosing/euclidean/threed/SphereGenerator.java
deleted file mode 100644
index 6fd1068..0000000
--- a/commons-geometry-enclosing/src/main/java/org/apache/commons/geometry/enclosing/euclidean/threed/SphereGenerator.java
+++ /dev/null
@@ -1,157 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements. See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-package org.apache.commons.geometry.enclosing.euclidean.threed;
-
-import java.util.Arrays;
-import java.util.Collections;
-import java.util.List;
-
-import org.apache.commons.geometry.enclosing.EnclosingBall;
-import org.apache.commons.geometry.enclosing.SupportBallGenerator;
-import org.apache.commons.geometry.enclosing.euclidean.twod.DiskGenerator;
-import org.apache.commons.geometry.euclidean.threed.EmbeddingPlane;
-import org.apache.commons.geometry.euclidean.threed.Planes;
-import org.apache.commons.geometry.euclidean.threed.Vector3D;
-import org.apache.commons.geometry.euclidean.twod.Vector2D;
-import org.apache.commons.numbers.core.Precision;
-import org.apache.commons.numbers.fraction.BigFraction;
-
-/** Class generating a sphere from its support points.
- */
-public class SphereGenerator implements SupportBallGenerator<Vector3D> {
-
- /** Precision context used to compare floating point numbers. */
- private final Precision.DoubleEquivalence precision;
-
- /** Construct a new instance with the given precision context.
- * @param precision precision context used to compare floating point numbers
- */
- public SphereGenerator(final Precision.DoubleEquivalence precision) {
- this.precision = precision;
- }
-
- /** {@inheritDoc} */
- @Override
- public EnclosingBall<Vector3D> ballOnSupport(final List<Vector3D> support) {
- if (support.isEmpty()) {
- return new EnclosingBall<>(Vector3D.ZERO, Double.NEGATIVE_INFINITY, Collections.emptyList());
- }
- final Vector3D vA = support.get(0);
- if (support.size() < 2) {
- return new EnclosingBall<>(vA, 0, Collections.singletonList(vA));
- }
- final Vector3D vB = support.get(1);
- if (support.size() < 3) {
- return new EnclosingBall<>(vA.lerp(vB, 0.5),
- 0.5 * vA.distance(vB),
- Arrays.asList(vA, vB));
- }
- final Vector3D vC = support.get(2);
- if (support.size() < 4) {
- final EmbeddingPlane p = Planes.fromPoints(vA, vB, vC, precision).getEmbedding();
- final EnclosingBall<Vector2D> disk =
- new DiskGenerator().ballOnSupport(Arrays.asList(p.toSubspace(vA),
- p.toSubspace(vB),
- p.toSubspace(vC)));
-
- // convert back to 3D
- return new EnclosingBall<>(p.toSpace(disk.getCenter()),
- disk.getRadius(),
- Arrays.asList(vA, vB, vC));
-
- }
- final Vector3D vD = support.get(3);
- // a sphere is 3D can be defined as:
- // (1) (x - x_0)^2 + (y - y_0)^2 + (z - z_0)^2 = r^2
- // which can be written:
- // (2) (x^2 + y^2 + z^2) - 2 x_0 x - 2 y_0 y - 2 z_0 z + (x_0^2 + y_0^2 + z_0^2 - r^2) = 0
- // or simply:
- // (3) (x^2 + y^2 + z^2) + a x + b y + c z + d = 0
- // with sphere center coordinates -a/2, -b/2, -c/2
- // If the sphere exists, a b, c and d are a non zero solution to
- // [ (x^2 + y^2 + z^2) x y z 1 ] [ 1 ] [ 0 ]
- // [ (xA^2 + yA^2 + zA^2) xA yA zA 1 ] [ a ] [ 0 ]
- // [ (xB^2 + yB^2 + zB^2) xB yB zB 1 ] * [ b ] = [ 0 ]
- // [ (xC^2 + yC^2 + zC^2) xC yC zC 1 ] [ c ] [ 0 ]
- // [ (xD^2 + yD^2 + zD^2) xD yD zD 1 ] [ d ] [ 0 ]
- // So the determinant of the matrix is zero. Computing this determinant
- // by expanding it using the minors m_ij of first row leads to
- // (4) m_11 (x^2 + y^2 + z^2) - m_12 x + m_13 y - m_14 z + m_15 = 0
- // So by identifying equations (2) and (4) we get the coordinates
- // of center as:
- // x_0 = +m_12 / (2 m_11)
- // y_0 = -m_13 / (2 m_11)
- // z_0 = +m_14 / (2 m_11)
- // Note that the minors m_11, m_12, m_13 and m_14 all have the last column
- // filled with 1.0, hence simplifying the computation
- final BigFraction[] c2 = {
- BigFraction.from(vA.getX()), BigFraction.from(vB.getX()),
- BigFraction.from(vC.getX()), BigFraction.from(vD.getX())
- };
- final BigFraction[] c3 = {
- BigFraction.from(vA.getY()), BigFraction.from(vB.getY()),
- BigFraction.from(vC.getY()), BigFraction.from(vD.getY())
- };
- final BigFraction[] c4 = {
- BigFraction.from(vA.getZ()), BigFraction.from(vB.getZ()),
- BigFraction.from(vC.getZ()), BigFraction.from(vD.getZ())
- };
- final BigFraction[] c1 = {
- c2[0].multiply(c2[0]).add(c3[0].multiply(c3[0])).add(c4[0].multiply(c4[0])),
- c2[1].multiply(c2[1]).add(c3[1].multiply(c3[1])).add(c4[1].multiply(c4[1])),
- c2[2].multiply(c2[2]).add(c3[2].multiply(c3[2])).add(c4[2].multiply(c4[2])),
- c2[3].multiply(c2[3]).add(c3[3].multiply(c3[3])).add(c4[3].multiply(c4[3]))
- };
- final BigFraction twoM11 = minor(c2, c3, c4).multiply(2);
- final BigFraction m12 = minor(c1, c3, c4);
- final BigFraction m13 = minor(c1, c2, c4);
- final BigFraction m14 = minor(c1, c2, c3);
- final BigFraction centerX = m12.divide(twoM11);
- final BigFraction centerY = m13.divide(twoM11).negate();
- final BigFraction centerZ = m14.divide(twoM11);
- final BigFraction dx = c2[0].subtract(centerX);
- final BigFraction dy = c3[0].subtract(centerY);
- final BigFraction dz = c4[0].subtract(centerZ);
- final BigFraction r2 = dx.multiply(dx).add(dy.multiply(dy)).add(dz.multiply(dz));
- return new EnclosingBall<>(Vector3D.of(centerX.doubleValue(),
- centerY.doubleValue(),
- centerZ.doubleValue()),
- Math.sqrt(r2.doubleValue()),
- Arrays.asList(vA, vB, vC, vD));
- }
-
- /** Compute a dimension 4 minor, when 4<sup>th</sup> column is known to be filled with 1.0.
- * @param c1 first column
- * @param c2 second column
- * @param c3 third column
- * @return value of the minor computed has an exact fraction
- */
- private BigFraction minor(final BigFraction[] c1, final BigFraction[] c2, final BigFraction[] c3) {
- return c2[0].multiply(c3[1]).multiply(c1[2].subtract(c1[3])).
- add(c2[0].multiply(c3[2]).multiply(c1[3].subtract(c1[1]))).
- add(c2[0].multiply(c3[3]).multiply(c1[1].subtract(c1[2]))).
- add(c2[1].multiply(c3[0]).multiply(c1[3].subtract(c1[2]))).
- add(c2[1].multiply(c3[2]).multiply(c1[0].subtract(c1[3]))).
- add(c2[1].multiply(c3[3]).multiply(c1[2].subtract(c1[0]))).
- add(c2[2].multiply(c3[0]).multiply(c1[1].subtract(c1[3]))).
- add(c2[2].multiply(c3[1]).multiply(c1[3].subtract(c1[0]))).
- add(c2[2].multiply(c3[3]).multiply(c1[0].subtract(c1[1]))).
- add(c2[3].multiply(c3[0]).multiply(c1[2].subtract(c1[1]))).
- add(c2[3].multiply(c3[1]).multiply(c1[0].subtract(c1[2]))).
- add(c2[3].multiply(c3[2]).multiply(c1[1].subtract(c1[0])));
- }
-}
diff --git a/commons-geometry-enclosing/src/main/java/org/apache/commons/geometry/enclosing/euclidean/threed/WelzlEncloser3D.java b/commons-geometry-enclosing/src/main/java/org/apache/commons/geometry/enclosing/euclidean/threed/WelzlEncloser3D.java
deleted file mode 100644
index d17e515..0000000
--- a/commons-geometry-enclosing/src/main/java/org/apache/commons/geometry/enclosing/euclidean/threed/WelzlEncloser3D.java
+++ /dev/null
@@ -1,35 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements. See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-package org.apache.commons.geometry.enclosing.euclidean.threed;
-
-import org.apache.commons.geometry.enclosing.WelzlEncloser;
-import org.apache.commons.geometry.euclidean.threed.Vector3D;
-import org.apache.commons.numbers.core.Precision;
-
-/** Extension of the {@link WelzlEncloser} class for Euclidean 3D space. This is
- * primarily a convenience class to simplify instantiation.
- */
-public class WelzlEncloser3D extends WelzlEncloser<Vector3D> {
-
- /** Construct a new instance with the given precision context. A new {@link SphereGenerator}
- * instance is used as the support ball generator.
- * @param precision precision context to use for floating point comparisons
- */
- public WelzlEncloser3D(final Precision.DoubleEquivalence precision) {
- super(new SphereGenerator(precision), precision);
- }
-}
diff --git a/commons-geometry-enclosing/src/main/java/org/apache/commons/geometry/enclosing/euclidean/threed/package-info.java b/commons-geometry-enclosing/src/main/java/org/apache/commons/geometry/enclosing/euclidean/threed/package-info.java
deleted file mode 100644
index a5420c8..0000000
--- a/commons-geometry-enclosing/src/main/java/org/apache/commons/geometry/enclosing/euclidean/threed/package-info.java
+++ /dev/null
@@ -1,24 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements. See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-/**
- *
- * <p>
- * This package provides classes related to the smallest enclosing ball problem in three dimensions.
- * </p>
- *
- */
-package org.apache.commons.geometry.enclosing.euclidean.threed;
diff --git a/commons-geometry-enclosing/src/main/java/org/apache/commons/geometry/enclosing/euclidean/twod/DiskGenerator.java b/commons-geometry-enclosing/src/main/java/org/apache/commons/geometry/enclosing/euclidean/twod/DiskGenerator.java
deleted file mode 100644
index 77eb5d1..0000000
--- a/commons-geometry-enclosing/src/main/java/org/apache/commons/geometry/enclosing/euclidean/twod/DiskGenerator.java
+++ /dev/null
@@ -1,105 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements. See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-package org.apache.commons.geometry.enclosing.euclidean.twod;
-
-import java.util.Arrays;
-import java.util.Collections;
-import java.util.List;
-
-import org.apache.commons.geometry.enclosing.EnclosingBall;
-import org.apache.commons.geometry.enclosing.SupportBallGenerator;
-import org.apache.commons.geometry.euclidean.twod.Vector2D;
-import org.apache.commons.numbers.fraction.BigFraction;
-
-/** Class generating a disk from its support points.
- */
-public class DiskGenerator implements SupportBallGenerator<Vector2D> {
-
- /** {@inheritDoc} */
- @Override
- public EnclosingBall<Vector2D> ballOnSupport(final List<Vector2D> support) {
- if (support.isEmpty()) {
- return new EnclosingBall<>(Vector2D.ZERO, Double.NEGATIVE_INFINITY, Collections.emptyList());
- }
- final Vector2D vA = support.get(0);
- if (support.size() < 2) {
- return new EnclosingBall<>(vA, 0, Collections.singletonList(vA));
- }
- final Vector2D vB = support.get(1);
- if (support.size() < 3) {
- return new EnclosingBall<>(vA.lerp(vB, 0.5),
- 0.5 * vA.distance(vB),
- Arrays.asList(vA, vB));
- }
- final Vector2D vC = support.get(2);
- // a disk is 2D can be defined as:
- // (1) (x - x_0)^2 + (y - y_0)^2 = r^2
- // which can be written:
- // (2) (x^2 + y^2) - 2 x_0 x - 2 y_0 y + (x_0^2 + y_0^2 - r^2) = 0
- // or simply:
- // (3) (x^2 + y^2) + a x + b y + c = 0
- // with disk center coordinates -a/2, -b/2
- // If the disk exists, a, b and c are a non-zero solution to
- // [ (x^2 + y^2 ) x y 1 ] [ 1 ] [ 0 ]
- // [ (xA^2 + yA^2) xA yA 1 ] [ a ] [ 0 ]
- // [ (xB^2 + yB^2) xB yB 1 ] * [ b ] = [ 0 ]
- // [ (xC^2 + yC^2) xC yC 1 ] [ c ] [ 0 ]
- // So the determinant of the matrix is zero. Computing this determinant
- // by expanding it using the minors m_ij of first row leads to
- // (4) m_11 (x^2 + y^2) - m_12 x + m_13 y - m_14 = 0
- // So by identifying equations (2) and (4) we get the coordinates
- // of center as:
- // x_0 = +m_12 / (2 m_11)
- // y_0 = -m_13 / (2 m_11)
- // Note that the minors m_11, m_12 and m_13 all have the last column
- // filled with 1.0, hence simplifying the computation
- final BigFraction[] c2 = {
- BigFraction.from(vA.getX()), BigFraction.from(vB.getX()), BigFraction.from(vC.getX())
- };
- final BigFraction[] c3 = {
- BigFraction.from(vA.getY()), BigFraction.from(vB.getY()), BigFraction.from(vC.getY())
- };
- final BigFraction[] c1 = {
- c2[0].multiply(c2[0]).add(c3[0].multiply(c3[0])),
- c2[1].multiply(c2[1]).add(c3[1].multiply(c3[1])),
- c2[2].multiply(c2[2]).add(c3[2].multiply(c3[2]))
- };
- final BigFraction twoM11 = minor(c2, c3).multiply(2);
- final BigFraction m12 = minor(c1, c3);
- final BigFraction m13 = minor(c1, c2);
- final BigFraction centerX = m12.divide(twoM11);
- final BigFraction centerY = m13.divide(twoM11).negate();
- final BigFraction dx = c2[0].subtract(centerX);
- final BigFraction dy = c3[0].subtract(centerY);
- final BigFraction r2 = dx.multiply(dx).add(dy.multiply(dy));
- return new EnclosingBall<>(Vector2D.of(centerX.doubleValue(),
- centerY.doubleValue()),
- Math.sqrt(r2.doubleValue()),
- Arrays.asList(vA, vB, vC));
- }
-
- /** Compute a dimension 3 minor, when 3<sup>d</sup> column is known to be filled with 1.0.
- * @param c1 first column
- * @param c2 second column
- * @return value of the minor computed has an exact fraction
- */
- private BigFraction minor(final BigFraction[] c1, final BigFraction[] c2) {
- return c2[0].multiply(c1[2].subtract(c1[1])).
- add(c2[1].multiply(c1[0].subtract(c1[2]))).
- add(c2[2].multiply(c1[1].subtract(c1[0])));
- }
-}
diff --git a/commons-geometry-enclosing/src/main/java/org/apache/commons/geometry/enclosing/euclidean/twod/WelzlEncloser2D.java b/commons-geometry-enclosing/src/main/java/org/apache/commons/geometry/enclosing/euclidean/twod/WelzlEncloser2D.java
deleted file mode 100644
index 0a733d1..0000000
--- a/commons-geometry-enclosing/src/main/java/org/apache/commons/geometry/enclosing/euclidean/twod/WelzlEncloser2D.java
+++ /dev/null
@@ -1,35 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements. See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-package org.apache.commons.geometry.enclosing.euclidean.twod;
-
-import org.apache.commons.geometry.enclosing.WelzlEncloser;
-import org.apache.commons.geometry.euclidean.twod.Vector2D;
-import org.apache.commons.numbers.core.Precision;
-
-/** Extension of the {@link WelzlEncloser} class for Euclidean 2D space. This is
- * primarily a convenience class to simplify instantiation.
- */
-public class WelzlEncloser2D extends WelzlEncloser<Vector2D> {
-
- /** Construct a new instance with the given precision context. A new {@link DiskGenerator}
- * instance is used as the support ball generator.
- * @param precision precision context to use for floating point comparisons.
- */
- public WelzlEncloser2D(final Precision.DoubleEquivalence precision) {
- super(new DiskGenerator(), precision);
- }
-}
diff --git a/commons-geometry-enclosing/src/main/java/org/apache/commons/geometry/enclosing/euclidean/twod/package-info.java b/commons-geometry-enclosing/src/main/java/org/apache/commons/geometry/enclosing/euclidean/twod/package-info.java
deleted file mode 100644
index b9a2ede..0000000
--- a/commons-geometry-enclosing/src/main/java/org/apache/commons/geometry/enclosing/euclidean/twod/package-info.java
+++ /dev/null
@@ -1,24 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements. See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-/**
- *
- * <p>
- * This package provides classes related to the smallest enclosing ball problem in two dimensions.
- * </p>
- *
- */
-package org.apache.commons.geometry.enclosing.euclidean.twod;
diff --git a/commons-geometry-enclosing/src/main/java/org/apache/commons/geometry/enclosing/package-info.java b/commons-geometry-enclosing/src/main/java/org/apache/commons/geometry/enclosing/package-info.java
deleted file mode 100644
index 7338211..0000000
--- a/commons-geometry-enclosing/src/main/java/org/apache/commons/geometry/enclosing/package-info.java
+++ /dev/null
@@ -1,24 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements. See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-/**
- *
- * <p>
- * This package provides interfaces and classes related to the smallest enclosing ball problem.
- * </p>
- *
- */
-package org.apache.commons.geometry.enclosing;
diff --git a/commons-geometry-enclosing/src/site/site.xml b/commons-geometry-enclosing/src/site/site.xml
deleted file mode 100644
index 88dc5cc..0000000
--- a/commons-geometry-enclosing/src/site/site.xml
+++ /dev/null
@@ -1,41 +0,0 @@
-<?xml version="1.0" encoding="ISO-8859-1"?>
-<!--
- Licensed to the Apache Software Foundation (ASF) under one or more
- contributor license agreements. See the NOTICE file distributed with
- this work for additional information regarding copyright ownership.
- The ASF licenses this file to You under the Apache License, Version 2.0
- (the "License"); you may not use this file except in compliance with
- the License. You may obtain a copy of the License at
-
- http://www.apache.org/licenses/LICENSE-2.0
-
- Unless required by applicable law or agreed to in writing, software
- distributed under the License is distributed on an "AS IS" BASIS,
- WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- See the License for the specific language governing permissions and
- limitations under the License.
--->
-<project name="Geometry">
- <bannerRight>
- <name>Apache Commons Geometry</name>
- <!-- Use a full URL allows a correct banner for the modules. -->
- <src>https://commons.apache.org/proper/commons-geometry/images/commons_geometry.small.png</src>
- <href>https://commons.apache.org/proper/commons-geometry/index.html</href>
- </bannerRight>
-
- <body>
- <menu name="Geometry">
- <item name="Overview" href="/index.html"/>
- <item name="Latest API docs (development)"
- href="apidocs/index.html"/>
- <!-- <item name="Javadoc (1.0 release)"
- href="https://commons.apache.org/geometry/commons-geometry-enclosing/javadocs/api-1.0/index.html"/> -->
- </menu>
-
- <head>
- <![CDATA[<script type="text/javascript" src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
- </script>]]>
- </head>
-
- </body>
-</project>
diff --git a/commons-geometry-enclosing/src/test/java/org/apache/commons/geometry/enclosing/DocumentationExamplesTest.java b/commons-geometry-enclosing/src/test/java/org/apache/commons/geometry/enclosing/DocumentationExamplesTest.java
deleted file mode 100644
index 8af5b4b..0000000
--- a/commons-geometry-enclosing/src/test/java/org/apache/commons/geometry/enclosing/DocumentationExamplesTest.java
+++ /dev/null
@@ -1,64 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements. See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-package org.apache.commons.geometry.enclosing;
-
-import java.util.Arrays;
-import java.util.List;
-
-import org.apache.commons.geometry.enclosing.euclidean.threed.WelzlEncloser3D;
-import org.apache.commons.geometry.euclidean.EuclideanTestUtils;
-import org.apache.commons.geometry.euclidean.threed.Vector3D;
-import org.apache.commons.numbers.core.Precision;
-import org.junit.jupiter.api.Assertions;
-import org.junit.jupiter.api.Test;
-
-/** This class contains code listed as examples in the user guide and other documentation.
- * If any portion of this code changes, the corresponding examples in the documentation <em>must</em> be updated.
- */
-class DocumentationExamplesTest {
-
- private static final double TEST_EPS = 1e-10;
-
- @Test
- void testWelzlEncloser3DExample() {
- final Precision.DoubleEquivalence precision = Precision.doubleEquivalenceOfEpsilon(1e-10);
-
- final List<Vector3D> points = Arrays.asList(
- Vector3D.of(0, 0, 1),
- Vector3D.of(0.75, 0, 1),
- Vector3D.of(2, 0, 1),
- Vector3D.of(1, 0, 2)
- );
-
- // compute the enclosing ball
- final WelzlEncloser3D encloser = new WelzlEncloser3D(precision);
-
- final EnclosingBall<Vector3D> sphere = encloser.enclose(points);
-
- // check the generated ball
- final Vector3D center = sphere.getCenter(); // (1, 0, 1)
- final double radius = sphere.getRadius(); // 1.0
- final boolean containsCenter = sphere.contains(center); // true
- final boolean containsOrigin = sphere.contains(Vector3D.ZERO); // false
-
- // ----------
- EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(1, 0, 1), center, TEST_EPS);
- Assertions.assertEquals(1.0, radius, TEST_EPS);
- Assertions.assertTrue(containsCenter);
- Assertions.assertFalse(containsOrigin);
- }
-}
diff --git a/commons-geometry-enclosing/src/test/java/org/apache/commons/geometry/enclosing/EnclosingBallTest.java b/commons-geometry-enclosing/src/test/java/org/apache/commons/geometry/enclosing/EnclosingBallTest.java
deleted file mode 100644
index 96b5f3b..0000000
--- a/commons-geometry-enclosing/src/test/java/org/apache/commons/geometry/enclosing/EnclosingBallTest.java
+++ /dev/null
@@ -1,153 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements. See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-package org.apache.commons.geometry.enclosing;
-
-import java.util.ArrayList;
-import java.util.Arrays;
-import java.util.Collections;
-import java.util.List;
-
-import org.apache.commons.geometry.euclidean.twod.Vector2D;
-import org.apache.commons.numbers.core.Precision;
-import org.junit.jupiter.api.Assertions;
-import org.junit.jupiter.api.Test;
-
-class EnclosingBallTest {
-
- private static final double TEST_EPS = 1e-10;
-
- @Test
- void testProperties_emptySupport() {
- // arrange
- final Vector2D center = Vector2D.of(1.2, 3.4);
- final double radius = 10;
- final List<Vector2D> support = new ArrayList<>();
-
- // act
- final EnclosingBall<Vector2D> ball = new EnclosingBall<>(center, radius, support);
-
- // assert
- Assertions.assertSame(center, ball.getCenter());
- Assertions.assertEquals(radius, ball.getRadius(), TEST_EPS);
- Assertions.assertEquals(0, ball.getSupportSize());
-
- final List<Vector2D> resultSupport = ball.getSupport();
- Assertions.assertEquals(0, resultSupport.size());
- }
-
- @Test
- void testProperties_nonEmptySupport() {
- // arrange
- final Vector2D center = Vector2D.of(1.2, 3.4);
- final double radius = 10;
- final List<Vector2D> support = new ArrayList<>(Arrays.asList(
- Vector2D.ZERO, Vector2D.Unit.PLUS_X, Vector2D.Unit.PLUS_Y));
-
- // act
- final EnclosingBall<Vector2D> ball = new EnclosingBall<>(center, radius, support);
-
- // assert
- Assertions.assertSame(center, ball.getCenter());
- Assertions.assertEquals(radius, ball.getRadius(), TEST_EPS);
- Assertions.assertEquals(3, ball.getSupportSize());
-
- final List<Vector2D> resultSupport = ball.getSupport();
- Assertions.assertNotSame(support, resultSupport);
- Assertions.assertEquals(support, resultSupport);
- }
-
- @Test
- void testGetSupport_listCannotBeModified() {
- // arrange
- final List<Vector2D> support = new ArrayList<>(Collections.singletonList(Vector2D.ZERO));
-
- final EnclosingBall<Vector2D> ball = new EnclosingBall<>(Vector2D.of(1, 1), 4, support);
- final List<Vector2D> ballSupport = ball.getSupport();
-
- // act/assert
- Assertions.assertThrows(UnsupportedOperationException.class, () -> ballSupport.add(Vector2D.Unit.PLUS_X));
- }
-
- @Test
- void testContains_strict() {
- // arrange
- final Vector2D center = Vector2D.of(1, 2);
- final double radius = 2;
- final EnclosingBall<Vector2D> ball = new EnclosingBall<>(center, radius, Collections.emptyList());
-
- // act/assert
- Assertions.assertTrue(ball.contains(center));
-
- Assertions.assertTrue(ball.contains(Vector2D.of(2, 3)));
- Assertions.assertTrue(ball.contains(Vector2D.of(0, 1)));
-
- Assertions.assertTrue(ball.contains(Vector2D.of(0, 2)));
- Assertions.assertTrue(ball.contains(Vector2D.of(1, 4)));
-
- Assertions.assertFalse(ball.contains(Vector2D.of(3.00001, 2)));
- Assertions.assertFalse(ball.contains(Vector2D.of(1, -1e-12)));
-
- Assertions.assertFalse(ball.contains(Vector2D.of(1, 5)));
- Assertions.assertFalse(ball.contains(Vector2D.of(1, -1)));
- Assertions.assertFalse(ball.contains(Vector2D.of(-2, 2)));
- Assertions.assertFalse(ball.contains(Vector2D.of(4, 2)));
- }
-
- @Test
- void testContains_precision() {
- // arrange
- final Precision.DoubleEquivalence lowerPrecision = Precision.doubleEquivalenceOfEpsilon(1e-4);
- final Precision.DoubleEquivalence higherPrecision = Precision.doubleEquivalenceOfEpsilon(1e-10);
-
- final Vector2D center = Vector2D.of(1, 2);
- final double radius = 2;
- final EnclosingBall<Vector2D> ball = new EnclosingBall<>(center, radius, Collections.emptyList());
-
- // act/assert
- Assertions.assertTrue(ball.contains(center, higherPrecision));
-
- Assertions.assertTrue(ball.contains(Vector2D.of(2, 3), higherPrecision));
- Assertions.assertTrue(ball.contains(Vector2D.of(0, 1), higherPrecision));
-
- Assertions.assertTrue(ball.contains(Vector2D.of(0, 2), higherPrecision));
- Assertions.assertTrue(ball.contains(Vector2D.of(1, 4), higherPrecision));
-
- Assertions.assertFalse(ball.contains(Vector2D.of(3.00001, 2), higherPrecision));
- Assertions.assertTrue(ball.contains(Vector2D.of(1, -1e-12), higherPrecision));
-
- Assertions.assertTrue(ball.contains(Vector2D.of(3.00001, 2), lowerPrecision));
- Assertions.assertTrue(ball.contains(Vector2D.of(1, -1e-12), lowerPrecision));
-
- Assertions.assertFalse(ball.contains(Vector2D.of(1, 5), higherPrecision));
- Assertions.assertFalse(ball.contains(Vector2D.of(1, -1), higherPrecision));
- Assertions.assertFalse(ball.contains(Vector2D.of(-2, 2), higherPrecision));
- Assertions.assertFalse(ball.contains(Vector2D.of(4, 2), higherPrecision));
- }
-
- @Test
- void testToString() {
- // arrange
- final EnclosingBall<Vector2D> ball = new EnclosingBall<>(Vector2D.ZERO, 1, Collections.singletonList(Vector2D.Unit.PLUS_X));
-
- // act
- final String str = ball.toString();
-
- // assert
- Assertions.assertTrue(str.startsWith("EnclosingBall[center= (0"));
- Assertions.assertTrue(str.contains("radius= 1"));
- }
-}
diff --git a/commons-geometry-enclosing/src/test/java/org/apache/commons/geometry/enclosing/euclidean/threed/SphereGeneratorTest.java b/commons-geometry-enclosing/src/test/java/org/apache/commons/geometry/enclosing/euclidean/threed/SphereGeneratorTest.java
deleted file mode 100644
index df8fb86..0000000
--- a/commons-geometry-enclosing/src/test/java/org/apache/commons/geometry/enclosing/euclidean/threed/SphereGeneratorTest.java
+++ /dev/null
@@ -1,238 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements. See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-package org.apache.commons.geometry.enclosing.euclidean.threed;
-
-import java.util.ArrayList;
-import java.util.Arrays;
-import java.util.Collections;
-import java.util.List;
-
-import org.apache.commons.geometry.enclosing.EnclosingBall;
-import org.apache.commons.geometry.euclidean.threed.Vector3D;
-import org.apache.commons.numbers.core.Precision;
-import org.apache.commons.rng.UniformRandomProvider;
-import org.apache.commons.rng.sampling.UnitSphereSampler;
-import org.apache.commons.rng.simple.RandomSource;
-import org.junit.jupiter.api.Assertions;
-import org.junit.jupiter.api.Test;
-
-class SphereGeneratorTest {
-
- private static final double TEST_EPS = 1e-10;
-
- private static final Precision.DoubleEquivalence TEST_PRECISION =
- Precision.doubleEquivalenceOfEpsilon(TEST_EPS);
-
- private final SphereGenerator generator = new SphereGenerator(TEST_PRECISION);
-
- @Test
- void testSupport0Point() {
- // arrange
- final List<Vector3D> support = Collections.emptyList();
-
- // act
- final EnclosingBall<Vector3D> sphere = generator.ballOnSupport(support);
-
- // assert
- Assertions.assertTrue(sphere.getRadius() < 0);
- Assertions.assertEquals(0, sphere.getSupportSize());
- Assertions.assertEquals(0, sphere.getSupport().size());
- }
-
- @Test
- void testSupport1Point() {
- // arrange
- final Precision.DoubleEquivalence lowPrecision = Precision.doubleEquivalenceOfEpsilon(0.5);
- final Precision.DoubleEquivalence highPrecision = Precision.doubleEquivalenceOfEpsilon(0.001);
- final List<Vector3D> support = Collections.singletonList(Vector3D.of(1, 2, 3));
-
- // act
- final EnclosingBall<Vector3D> sphere = generator.ballOnSupport(support);
-
- // assert
- Assertions.assertEquals(0.0, sphere.getRadius(), TEST_EPS);
-
- Assertions.assertTrue(sphere.contains(support.get(0)));
- Assertions.assertTrue(sphere.contains(support.get(0), lowPrecision));
- Assertions.assertFalse(sphere.contains(Vector3D.of(support.get(0).getX() + 0.1,
- support.get(0).getY() + 0.1,
- support.get(0).getZ() + 0.1),
- highPrecision));
- Assertions.assertTrue(sphere.contains(Vector3D.of(support.get(0).getX() + 0.1,
- support.get(0).getY() + 0.1,
- support.get(0).getZ() + 0.1),
- lowPrecision));
-
- Assertions.assertEquals(0, support.get(0).distance(sphere.getCenter()), 1.0e-10);
- Assertions.assertEquals(1, sphere.getSupportSize());
- Assertions.assertEquals(support.get(0), sphere.getSupport().get(0));
- }
-
- @Test
- void testSupport2Points() {
- // arrange
- final List<Vector3D> support = Arrays.asList(Vector3D.of(1, 0, 0),
- Vector3D.of(3, 0, 0));
-
- // act
- final EnclosingBall<Vector3D> sphere = generator.ballOnSupport(support);
-
- // assert
- Assertions.assertEquals(1.0, sphere.getRadius(), TEST_EPS);
-
- int i = 0;
- for (final Vector3D v : support) {
- Assertions.assertTrue(sphere.contains(v));
- Assertions.assertEquals(1.0, v.distance(sphere.getCenter()), TEST_EPS);
- Assertions.assertSame(v, sphere.getSupport().get(i++));
- }
-
- Assertions.assertTrue(sphere.contains(Vector3D.of(2, 0.9, 0)));
- Assertions.assertFalse(sphere.contains(Vector3D.ZERO));
- Assertions.assertEquals(0.0, Vector3D.of(2, 0, 0).distance(sphere.getCenter()), TEST_EPS);
- Assertions.assertEquals(2, sphere.getSupportSize());
- }
-
- @Test
- void testSupport3Points() {
- // arrange
- final List<Vector3D> support = Arrays.asList(Vector3D.of(1, 0, 0),
- Vector3D.of(3, 0, 0),
- Vector3D.of(2, 2, 0));
-
- // act
- final EnclosingBall<Vector3D> sphere = generator.ballOnSupport(support);
-
- // assert
- Assertions.assertEquals(5.0 / 4.0, sphere.getRadius(), TEST_EPS);
-
- int i = 0;
- for (final Vector3D v : support) {
- Assertions.assertTrue(sphere.contains(v));
- Assertions.assertEquals(5.0 / 4.0, v.distance(sphere.getCenter()), TEST_EPS);
- Assertions.assertEquals(v, sphere.getSupport().get(i++));
- }
-
- Assertions.assertTrue(sphere.contains(Vector3D.of(2, 0.9, 0)));
- Assertions.assertFalse(sphere.contains(Vector3D.of(0.9, 0, 0)));
- Assertions.assertFalse(sphere.contains(Vector3D.of(3.1, 0, 0)));
- Assertions.assertTrue(sphere.contains(Vector3D.of(2.0, -0.499, 0)));
- Assertions.assertFalse(sphere.contains(Vector3D.of(2.0, -0.501, 0)));
- Assertions.assertTrue(sphere.contains(Vector3D.of(2.0, 3.0 / 4.0, -1.249)));
- Assertions.assertFalse(sphere.contains(Vector3D.of(2.0, 3.0 / 4.0, -1.251)));
- Assertions.assertEquals(0.0, Vector3D.of(2.0, 3.0 / 4.0, 0).distance(sphere.getCenter()), TEST_EPS);
- Assertions.assertEquals(3, sphere.getSupportSize());
- }
-
- @Test
- void testSupport4Points() {
- // arrange
- final List<Vector3D> support = Arrays.asList(Vector3D.of(17, 14, 18),
- Vector3D.of(11, 14, 22),
- Vector3D.of(2, 22, 17),
- Vector3D.of(22, 11, -10));
-
- // act
- final EnclosingBall<Vector3D> sphere = generator.ballOnSupport(support);
-
- // assert
- Assertions.assertEquals(25.0, sphere.getRadius(), TEST_EPS);
-
- int i = 0;
- for (final Vector3D v : support) {
- Assertions.assertTrue(sphere.contains(v));
- Assertions.assertEquals(25.0, v.distance(sphere.getCenter()), 1.0e-10);
- Assertions.assertEquals(v, sphere.getSupport().get(i++));
- }
-
- Assertions.assertTrue(sphere.contains(Vector3D.of(-22.999, 2, 2)));
- Assertions.assertFalse(sphere.contains(Vector3D.of(-23.001, 2, 2)));
- Assertions.assertTrue(sphere.contains(Vector3D.of(26.999, 2, 2)));
- Assertions.assertFalse(sphere.contains(Vector3D.of(27.001, 2, 2)));
- Assertions.assertTrue(sphere.contains(Vector3D.of(2, -22.999, 2)));
- Assertions.assertFalse(sphere.contains(Vector3D.of(2, -23.001, 2)));
- Assertions.assertTrue(sphere.contains(Vector3D.of(2, 26.999, 2)));
- Assertions.assertFalse(sphere.contains(Vector3D.of(2, 27.001, 2)));
- Assertions.assertTrue(sphere.contains(Vector3D.of(2, 2, -22.999)));
- Assertions.assertFalse(sphere.contains(Vector3D.of(2, 2, -23.001)));
- Assertions.assertTrue(sphere.contains(Vector3D.of(2, 2, 26.999)));
- Assertions.assertFalse(sphere.contains(Vector3D.of(2, 2, 27.001)));
- Assertions.assertEquals(0.0, Vector3D.of(2.0, 2.0, 2.0).distance(sphere.getCenter()), TEST_EPS);
- Assertions.assertEquals(4, sphere.getSupportSize());
- }
-
- @Test
- void testRandom() {
- // arrange
- final UniformRandomProvider random = RandomSource.create(RandomSource.WELL_1024_A,
- 0xd015982e9f31ee04L);
- final UnitSphereSampler sr = new UnitSphereSampler(3, random);
- for (int i = 0; i < 100; ++i) {
- final double d = 25 * random.nextDouble();
- final double refRadius = 10 * random.nextDouble();
- final Vector3D refCenter = Vector3D.of(sr.nextVector()).multiply(d);
- final List<Vector3D> support = new ArrayList<>();
- for (int j = 0; j < 5; ++j) {
- support.add(Vector3D.Sum.of(refCenter).addScaled(refRadius, Vector3D.of(sr.nextVector())).get());
- }
-
- // act
- final EnclosingBall<Vector3D> sphere = generator.ballOnSupport(support);
-
- // assert
- Assertions.assertEquals(0.0, refCenter.distance(sphere.getCenter()), 4e-7 * refRadius);
- Assertions.assertEquals(refRadius, sphere.getRadius(), 1e-7 * refRadius);
- }
- }
-
- @Test
- void testDegeneratedCase() {
- // --- arrange
- final List<Vector3D> support =
- Arrays.asList(Vector3D.of(Math.scalb(-8039905610797991.0, -50), // -7.140870659936730
- Math.scalb(-4663475464714142.0, -48), // -16.567993074240455
- Math.scalb(6592658872616184.0, -49)), // 11.710914678204503
- Vector3D.of(Math.scalb(-8036658568968473.0, -50), // -7.137986707455888
- Math.scalb(-4664256346424880.0, -48), // -16.570767323375720
- Math.scalb(6591357011730307.0, -49)), // 11.708602108715928)
- Vector3D.of(Math.scalb(-8037820142977230.0, -50), // -7.139018392423351
- Math.scalb(-4665280434237813.0, -48), // -16.574405614157020
- Math.scalb(6592435966112099.0, -49)), // 11.710518716711425
- Vector3D.of(Math.scalb(-8038007803611611.0, -50), // -7.139185068549035
- Math.scalb(-4664291215918380.0, -48), // -16.570891204702250
- Math.scalb(6595270610894208.0, -49))); // 11.715554057357394
-
- // --- act
- final EnclosingBall<Vector3D> sphere = generator.ballOnSupport(support);
-
- // --- assert
- // the following values have been computed using Emacs calc with exact arithmetic from the
- // rational representation corresponding to the scalb calls (i.e. -8039905610797991/2^50, ...)
- // The results were converted to decimal representation rounded to 1.0e-30 when writing the reference
- // values in this test
- final double eps = 1e-20;
- Assertions.assertEquals(0.003616820213530053297575846168, sphere.getRadius(), eps);
- Assertions.assertEquals(-7.139325643360503322823511839511, sphere.getCenter().getX(), eps);
- Assertions.assertEquals(-16.571096474251747245361467833760, sphere.getCenter().getY(), eps);
- Assertions.assertEquals(11.711945804096960876521111630800, sphere.getCenter().getZ(), eps);
-
- final Precision.DoubleEquivalence supportPrecision = Precision.doubleEquivalenceOfEpsilon(1e-14);
- for (final Vector3D v : support) {
- Assertions.assertTrue(sphere.contains(v, supportPrecision));
- }
- }
-}
diff --git a/commons-geometry-enclosing/src/test/java/org/apache/commons/geometry/enclosing/euclidean/threed/WelzlEncloser3DTest.java b/commons-geometry-enclosing/src/test/java/org/apache/commons/geometry/enclosing/euclidean/threed/WelzlEncloser3DTest.java
deleted file mode 100644
index 9561982..0000000
--- a/commons-geometry-enclosing/src/test/java/org/apache/commons/geometry/enclosing/euclidean/threed/WelzlEncloser3DTest.java
+++ /dev/null
@@ -1,185 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements. See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-package org.apache.commons.geometry.enclosing.euclidean.threed;
-
-import java.util.ArrayList;
-import java.util.Arrays;
-import java.util.List;
-
-import org.apache.commons.geometry.core.GeometryTestUtils;
-import org.apache.commons.geometry.enclosing.EnclosingBall;
-import org.apache.commons.geometry.euclidean.threed.Vector3D;
-import org.apache.commons.numbers.core.Precision;
-import org.apache.commons.rng.UniformRandomProvider;
-import org.apache.commons.rng.sampling.UnitSphereSampler;
-import org.apache.commons.rng.simple.RandomSource;
-import org.junit.jupiter.api.Assertions;
-import org.junit.jupiter.api.Test;
-
-class WelzlEncloser3DTest {
-
- private static final double TEST_EPS = 1e-10;
-
- private static final Precision.DoubleEquivalence TEST_PRECISION =
- Precision.doubleEquivalenceOfEpsilon(TEST_EPS);
-
- private final WelzlEncloser3D encloser = new WelzlEncloser3D(TEST_PRECISION);
-
- @Test
- void testNoPoints() {
- // arrange
- final String msg = "Unable to generate enclosing ball: no points given";
-
- // act/assert
- GeometryTestUtils.assertThrowsWithMessage(() -> {
- encloser.enclose(null);
- }, IllegalArgumentException.class, msg);
-
- GeometryTestUtils.assertThrowsWithMessage(() -> {
- encloser.enclose(new ArrayList<Vector3D>());
- }, IllegalArgumentException.class, msg);
- }
-
- @Test
- void testReducingBall() {
- // arrange
- final List<Vector3D> list =
- Arrays.asList(Vector3D.of(-7.140397329568118, -16.571661242582177, 11.714458961735405),
- Vector3D.of(-7.137986707455888, -16.570767323375720, 11.708602108715928),
- Vector3D.of(-7.139185068549035, -16.570891204702250, 11.715554057357394),
- Vector3D.of(-7.142682716997507, -16.571609818234290, 11.710787934580328),
- Vector3D.of(-7.139018392423351, -16.574405614157020, 11.710518716711425),
- Vector3D.of(-7.140870659936730, -16.567993074240455, 11.710914678204503),
- Vector3D.of(-7.136350173659562, -16.570498228820930, 11.713965225900928),
- Vector3D.of(-7.141675762759172, -16.572852471407028, 11.714033471449508),
- Vector3D.of(-7.140453077221105, -16.570212820780647, 11.708624578004980),
- Vector3D.of(-7.140322188726825, -16.574152894557717, 11.710305611121410),
- Vector3D.of(-7.141116131477088, -16.574061164624560, 11.712938509321699));
-
- // act
- final EnclosingBall<Vector3D> ball = encloser.enclose(list);
-
- // assert
- Assertions.assertTrue(ball.getRadius() > 0);
- }
-
- @Test
- void testInfiniteLoop() {
- // arrange
- // this test used to generate an infinite loop
- final List<Vector3D> list =
- Arrays.asList(Vector3D.of(-0.89227075512164380, -2.89317694645713900, 14.84572323743355500),
- Vector3D.of(-0.92099498940693580, -2.31086108263908940, 12.92071026467688300),
- Vector3D.of(-0.85227999411005200, -3.06314731441320730, 15.40163831651287000),
- Vector3D.of(-1.77399413020785970, -3.65630391378114260, 14.13190097751873400),
- Vector3D.of(0.33157833272465354, -2.22813591757792160, 14.21225234159008200),
- Vector3D.of(-1.53065579165484400, -1.65692084770139570, 14.61483055714788500),
- Vector3D.of(-1.08457093941217140, -1.96100325935602980, 13.09265170575555000),
- Vector3D.of(0.30029469589708850, -3.05470831395667370, 14.56352400426342600),
- Vector3D.of(-0.95007443938638460, -1.86810946486118360, 15.14491234340057000),
- Vector3D.of(-1.89661503804130830, -2.17004080885185860, 14.81235128513927000),
- Vector3D.of(-0.72193328761607530, -1.44513142833618270, 14.52355724218561800),
- Vector3D.of(-0.26895980939606550, -3.69512371522084140, 14.72272846327652000),
- Vector3D.of(-1.53501693431786170, -3.25055166611021900, 15.15509062584274800),
- Vector3D.of(-0.71727553535519410, -3.62284279460799100, 13.26256700929380700),
- Vector3D.of(-0.30220950676137365, -3.25410412500779070, 13.13682612771606000),
- Vector3D.of(-0.04543996608267075, -1.93081853923797750, 14.79497997883171400),
- Vector3D.of(-1.53348892951571640, -3.66688919703524900, 14.73095600812074200),
- Vector3D.of(-0.98034899533935820, -3.34004481162763960, 13.03245014017556800));
-
- // act
- final EnclosingBall<Vector3D> ball = encloser.enclose(list);
-
- // assert
- Assertions.assertTrue(ball.getRadius() > 0);
- }
-
- @Test
- void testLargeSamples() {
- // arrange
- final UniformRandomProvider random = RandomSource.create(RandomSource.WELL_1024_A,
- 0x35ddecfc78131e1dL);
- final UnitSphereSampler sr = new UnitSphereSampler(3, random);
- for (int k = 0; k < 50; ++k) {
-
- // define the reference sphere we want to compute
- final double d = 25 * random.nextDouble();
- final double refRadius = 10 * random.nextDouble();
- final Vector3D refCenter = Vector3D.of(sr.nextVector()).multiply(d);
- // set up a large sample inside the reference sphere
- final int nbPoints = random.nextInt(1000);
-
- final List<Vector3D> points = new ArrayList<>();
- for (int i = 0; i < nbPoints; ++i) {
- final double r = refRadius * random.nextDouble();
- points.add(Vector3D.Sum.of(refCenter).addScaled(r, Vector3D.of(sr.nextVector())).get());
- }
-
- // act/assert
- // test we find a sphere at most as large as the one used for random drawings
- checkSphere(points, refRadius);
- }
- }
-
- private void checkSphere(final List<Vector3D> points, final double refRadius) {
-
- final EnclosingBall<Vector3D> sphere = checkSphere(points);
-
- // compare computed sphere with bounding sphere
- Assertions.assertTrue(sphere.getRadius() <= refRadius);
-
- // check removing any point of the support Sphere fails to enclose the point
- for (int i = 0; i < sphere.getSupportSize(); ++i) {
- final List<Vector3D> reducedSupport = new ArrayList<>();
- int count = 0;
- for (final Vector3D s : sphere.getSupport()) {
- if (count++ != i) {
- reducedSupport.add(s);
- }
- }
- final EnclosingBall<Vector3D> reducedSphere = new SphereGenerator(TEST_PRECISION)
- .ballOnSupport(reducedSupport);
- boolean foundOutside = false;
- for (int j = 0; j < points.size() && !foundOutside; ++j) {
- if (!reducedSphere.contains(points.get(j), TEST_PRECISION)) {
- foundOutside = true;
- }
- }
- Assertions.assertTrue(foundOutside);
- }
- }
-
- private EnclosingBall<Vector3D> checkSphere(final List<Vector3D> points) {
-
- final EnclosingBall<Vector3D> sphere = encloser.enclose(points);
-
- // all points are enclosed
- for (final Vector3D v : points) {
- Assertions.assertTrue(sphere.contains(v, TEST_PRECISION));
- }
-
- // all support points are on the boundary
- final Vector3D center = sphere.getCenter();
- final double radius = sphere.getRadius();
-
- for (final Vector3D s : sphere.getSupport()) {
- Assertions.assertTrue(TEST_PRECISION.eqZero(center.distance(s) - radius));
- }
-
- return sphere;
- }
-}
diff --git a/commons-geometry-enclosing/src/test/java/org/apache/commons/geometry/enclosing/euclidean/twod/DiskGeneratorTest.java b/commons-geometry-enclosing/src/test/java/org/apache/commons/geometry/enclosing/euclidean/twod/DiskGeneratorTest.java
deleted file mode 100644
index c3428d9..0000000
--- a/commons-geometry-enclosing/src/test/java/org/apache/commons/geometry/enclosing/euclidean/twod/DiskGeneratorTest.java
+++ /dev/null
@@ -1,155 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements. See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-package org.apache.commons.geometry.enclosing.euclidean.twod;
-
-import java.util.ArrayList;
-import java.util.Arrays;
-import java.util.Collections;
-import java.util.List;
-
-import org.apache.commons.geometry.enclosing.EnclosingBall;
-import org.apache.commons.geometry.euclidean.twod.Vector2D;
-import org.apache.commons.numbers.core.Precision;
-import org.apache.commons.rng.UniformRandomProvider;
-import org.apache.commons.rng.sampling.UnitSphereSampler;
-import org.apache.commons.rng.simple.RandomSource;
-import org.junit.jupiter.api.Assertions;
-import org.junit.jupiter.api.Test;
-
-class DiskGeneratorTest {
-
- private static final double TEST_EPS = 1e-10;
-
- private final DiskGenerator generator = new DiskGenerator();
-
- @Test
- void testSupport0Point() {
- // arrange
- final List<Vector2D> support = Collections.emptyList();
-
- // act
- final EnclosingBall<Vector2D> disk = generator.ballOnSupport(support);
-
- // assert
- Assertions.assertTrue(disk.getRadius() < 0);
- Assertions.assertEquals(0, disk.getSupportSize());
- Assertions.assertEquals(0, disk.getSupport().size());
- }
-
- @Test
- void testSupport1Point() {
- // arrange
- final Precision.DoubleEquivalence lowPrecision = Precision.doubleEquivalenceOfEpsilon(0.5);
- final Precision.DoubleEquivalence highPrecision = Precision.doubleEquivalenceOfEpsilon(0.001);
- final List<Vector2D> support = Collections.singletonList(Vector2D.of(1, 2));
-
- // act
- final EnclosingBall<Vector2D> disk = generator.ballOnSupport(support);
-
- // assert
- Assertions.assertEquals(0.0, disk.getRadius(), TEST_EPS);
- Assertions.assertTrue(disk.contains(support.get(0)));
- Assertions.assertTrue(disk.contains(support.get(0), lowPrecision));
- Assertions.assertFalse(disk.contains(Vector2D.of(support.get(0).getX() + 0.1,
- support.get(0).getY() - 0.1),
- highPrecision));
- Assertions.assertTrue(disk.contains(Vector2D.of(support.get(0).getX() + 0.1,
- support.get(0).getY() - 0.1),
- lowPrecision));
- Assertions.assertEquals(0, support.get(0).distance(disk.getCenter()), TEST_EPS);
- Assertions.assertEquals(1, disk.getSupportSize());
- Assertions.assertEquals(support.get(0), disk.getSupport().get(0));
- }
-
- @Test
- void testSupport2Points() {
- // arrange
- final List<Vector2D> support = Arrays.asList(Vector2D.of(1, 0),
- Vector2D.of(3, 0));
-
- // act
- final EnclosingBall<Vector2D> disk = generator.ballOnSupport(support);
-
- // assert
- Assertions.assertEquals(1.0, disk.getRadius(), TEST_EPS);
-
- int i = 0;
- for (final Vector2D v : support) {
- Assertions.assertTrue(disk.contains(v));
- Assertions.assertEquals(1.0, v.distance(disk.getCenter()), TEST_EPS);
- Assertions.assertEquals(v, disk.getSupport().get(i++));
- }
-
- Assertions.assertTrue(disk.contains(Vector2D.of(2, 0.9)));
- Assertions.assertFalse(disk.contains(Vector2D.ZERO));
- Assertions.assertEquals(0.0, Vector2D.of(2, 0).distance(disk.getCenter()), TEST_EPS);
- Assertions.assertEquals(2, disk.getSupportSize());
- }
-
- @Test
- void testSupport3Points() {
- // arrange
- final List<Vector2D> support = Arrays.asList(Vector2D.of(1, 0),
- Vector2D.of(3, 0),
- Vector2D.of(2, 2));
-
- // act
- final EnclosingBall<Vector2D> disk = generator.ballOnSupport(support);
-
- // assert
- Assertions.assertEquals(5.0 / 4.0, disk.getRadius(), TEST_EPS);
-
- int i = 0;
- for (final Vector2D v : support) {
- Assertions.assertTrue(disk.contains(v));
- Assertions.assertEquals(5.0 / 4.0, v.distance(disk.getCenter()), TEST_EPS);
- Assertions.assertEquals(v, disk.getSupport().get(i++));
- }
-
- Assertions.assertTrue(disk.contains(Vector2D.of(2, 0.9)));
- Assertions.assertFalse(disk.contains(Vector2D.of(0.9, 0)));
- Assertions.assertFalse(disk.contains(Vector2D.of(3.1, 0)));
- Assertions.assertTrue(disk.contains(Vector2D.of(2.0, -0.499)));
- Assertions.assertFalse(disk.contains(Vector2D.of(2.0, -0.501)));
- Assertions.assertEquals(0.0, Vector2D.of(2.0, 3.0 / 4.0).distance(disk.getCenter()), TEST_EPS);
- Assertions.assertEquals(3, disk.getSupportSize());
- }
-
- @Test
- void testRandom() {
- // arrange
- final UniformRandomProvider random = RandomSource.create(RandomSource.WELL_1024_A,
- 0x12faa818373ffe90L);
- final UnitSphereSampler sr = new UnitSphereSampler(2, random);
- for (int i = 0; i < 500; ++i) {
- final double d = 25 * random.nextDouble();
- final double refRadius = 10 * random.nextDouble();
- final Vector2D refCenter = Vector2D.of(sr.nextVector()).multiply(d);
- final List<Vector2D> support = new ArrayList<>();
- for (int j = 0; j < 3; ++j) {
- support.add(Vector2D.Sum.of(refCenter).addScaled(refRadius, Vector2D.of(sr.nextVector())).get());
- }
-
- // act
- final EnclosingBall<Vector2D> disk = generator.ballOnSupport(support);
-
- // assert
- Assertions.assertEquals(0.0, refCenter.distance(disk.getCenter()), 3e-9 * refRadius);
- Assertions.assertEquals(refRadius, disk.getRadius(), 7e-10 * refRadius);
- }
- }
-}
diff --git a/commons-geometry-enclosing/src/test/java/org/apache/commons/geometry/enclosing/euclidean/twod/WelzlEncloser2DTest.java b/commons-geometry-enclosing/src/test/java/org/apache/commons/geometry/enclosing/euclidean/twod/WelzlEncloser2DTest.java
deleted file mode 100755
index 8bbb9cb..0000000
--- a/commons-geometry-enclosing/src/test/java/org/apache/commons/geometry/enclosing/euclidean/twod/WelzlEncloser2DTest.java
+++ /dev/null
@@ -1,210 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements. See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-package org.apache.commons.geometry.enclosing.euclidean.twod;
-
-import java.util.ArrayList;
-import java.util.Arrays;
-import java.util.List;
-
-import org.apache.commons.geometry.core.GeometryTestUtils;
-import org.apache.commons.geometry.enclosing.EnclosingBall;
-import org.apache.commons.geometry.euclidean.EuclideanTestUtils;
-import org.apache.commons.geometry.euclidean.twod.Vector2D;
-import org.apache.commons.numbers.core.Precision;
-import org.apache.commons.rng.UniformRandomProvider;
-import org.apache.commons.rng.simple.RandomSource;
-import org.junit.jupiter.api.Assertions;
-import org.junit.jupiter.api.Test;
-
-class WelzlEncloser2DTest {
-
- private static final double TEST_EPS = 1e-10;
-
- private static final Precision.DoubleEquivalence TEST_PRECISION =
- Precision.doubleEquivalenceOfEpsilon(TEST_EPS);
-
- private final WelzlEncloser2D encloser = new WelzlEncloser2D(TEST_PRECISION);
-
- @Test
- void testNoPoints() {
- // arrange
- final String msg = "Unable to generate enclosing ball: no points given";
-
- // act/assert
- GeometryTestUtils.assertThrowsWithMessage(() -> {
- encloser.enclose(null);
- }, IllegalArgumentException.class, msg);
-
- GeometryTestUtils.assertThrowsWithMessage(() -> {
- encloser.enclose(new ArrayList<Vector2D>());
- }, IllegalArgumentException.class, msg);
- }
-
- @Test
- void testRegularPoints() {
- // arrange
- final List<Vector2D> list = buildList(22, 26, 30, 38, 64, 28, 8, 54, 11, 15);
-
- // act/assert
- checkDisk(list, Arrays.asList(list.get(2), list.get(3), list.get(4)));
- }
-
- @Test
- void testSolutionOnDiameter() {
- // arrange
- final List<Vector2D> list = buildList(22, 26, 30, 38, 64, 28, 8, 54);
-
- // act/assert
- checkDisk(list, Arrays.asList(list.get(2), list.get(3)));
- }
-
- @Test
- void testReducingBall1() {
- // arrange
- final List<Vector2D> list = buildList(0.05380958511396061, 0.57332359658700000,
- 0.99348810731127870, 0.02056421361521466,
- 0.01203950647796437, 0.99779675042261860,
- 0.00810189987706078, 0.00589246003827815,
- 0.00465180821202149, 0.99219972923046940);
-
- // act/assert
- checkDisk(list, Arrays.asList(list.get(1), list.get(3), list.get(4)));
- }
-
- @Test
- void testReducingBall2() {
- // arrange
- final List<Vector2D> list = buildList(0.016930586154703, 0.333955448537779,
- 0.987189104892331, 0.969778855274507,
- 0.983696889599935, 0.012904580013266,
- 0.013114499572905, 0.034740156356895);
-
- // act/assert
- checkDisk(list, Arrays.asList(list.get(1), list.get(2), list.get(3)));
- }
-
- @Test
- void testLargeSamples() {
- // arrange
- final UniformRandomProvider random = RandomSource.create(RandomSource.WELL_1024_A, 0xa2a63cad12c01fb2L);
- for (int k = 0; k < 100; ++k) {
- final int nbPoints = random.nextInt(10000);
- final List<Vector2D> points = new ArrayList<>();
- for (int i = 0; i < nbPoints; ++i) {
- final double x = random.nextDouble();
- final double y = random.nextDouble();
- points.add(Vector2D.of(x, y));
- }
-
- // act/assert
- checkDisk(points);
- }
- }
-
- @Test
- void testEnclosingWithPrecision() {
- // arrange
- final List<Vector2D> points = Arrays.asList(
- Vector2D.of(271.59, 57.282),
- Vector2D.of(269.145, 57.063),
- Vector2D.of(309.117, 77.187),
- Vector2D.of(316.989, 34.835),
- Vector2D.of(323.101, 53.972)
- );
- final double precision = 1;
- final Precision.DoubleEquivalence precisionContext = Precision.doubleEquivalenceOfEpsilon(precision);
- final WelzlEncloser2D customPrecisionEncloser = new WelzlEncloser2D(precisionContext);
-
- // act
- final EnclosingBall<Vector2D> result = customPrecisionEncloser.enclose(points);
-
- // assert
- Assertions.assertEquals(27.099954200964234, result.getRadius(), TEST_EPS);
- EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(296.0056977503686, 53.469890753441945),
- result.getCenter(), TEST_EPS);
- }
-
- private List<Vector2D> buildList(final double... coordinates) {
- final List<Vector2D> list = new ArrayList<>(coordinates.length / 2);
- for (int i = 0; i < coordinates.length; i += 2) {
- list.add(Vector2D.of(coordinates[i], coordinates[i + 1]));
- }
- return list;
- }
-
- private void checkDisk(final List<Vector2D> points, final List<Vector2D> refSupport) {
-
- final EnclosingBall<Vector2D> disk = checkDisk(points);
-
- // compare computed disk with expected disk
- final EnclosingBall<Vector2D> expected = new DiskGenerator().ballOnSupport(refSupport);
- Assertions.assertEquals(refSupport.size(), disk.getSupportSize());
- Assertions.assertEquals(expected.getRadius(), disk.getRadius(), 1.0e-10);
- Assertions.assertEquals(expected.getCenter().getX(), disk.getCenter().getX(), 1.0e-10);
- Assertions.assertEquals(expected.getCenter().getY(), disk.getCenter().getY(), 1.0e-10);
-
- for (final Vector2D s : disk.getSupport()) {
- boolean found = false;
- for (final Vector2D rs : refSupport) {
- if (s == rs) {
- found = true;
- break;
- }
- }
- Assertions.assertTrue(found);
- }
-
- // check removing any point of the support disk fails to enclose the point
- for (int i = 0; i < disk.getSupportSize(); ++i) {
- final List<Vector2D> reducedSupport = new ArrayList<>();
- int count = 0;
- for (final Vector2D s : disk.getSupport()) {
- if (count++ != i) {
- reducedSupport.add(s);
- }
- }
- final EnclosingBall<Vector2D> reducedDisk = new DiskGenerator().ballOnSupport(reducedSupport);
- boolean foundOutside = false;
- for (int j = 0; j < points.size() && !foundOutside; ++j) {
- if (!reducedDisk.contains(points.get(j), TEST_PRECISION)) {
- foundOutside = true;
- }
- }
- Assertions.assertTrue(foundOutside);
- }
- }
-
- private EnclosingBall<Vector2D> checkDisk(final List<Vector2D> points) {
-
- final EnclosingBall<Vector2D> disk = encloser.enclose(points);
-
- // all points are enclosed
- for (final Vector2D v : points) {
- Assertions.assertTrue(disk.contains(v, TEST_PRECISION));
- }
-
- // all support points are on the boundary
- final Vector2D center = disk.getCenter();
- final double radius = disk.getRadius();
-
- for (final Vector2D s : disk.getSupport()) {
- Assertions.assertTrue(TEST_PRECISION.eqZero(center.distance(s) - radius));
- }
-
- return disk;
- }
-}
diff --git a/commons-geometry-euclidean/pom.xml b/commons-geometry-euclidean/pom.xml
index 63cf2f6..9527b6d 100644
--- a/commons-geometry-euclidean/pom.xml
+++ b/commons-geometry-euclidean/pom.xml
@@ -23,7 +23,7 @@
<parent>
<groupId>org.apache.commons</groupId>
<artifactId>commons-geometry-parent</artifactId>
- <version>1.0-SNAPSHOT</version>
+ <version>1.0</version>
</parent>
<artifactId>commons-geometry-euclidean</artifactId>
diff --git a/commons-geometry-euclidean/src/site/site.xml b/commons-geometry-euclidean/src/site/site.xml
index 8915e07..9bac4dd 100644
--- a/commons-geometry-euclidean/src/site/site.xml
+++ b/commons-geometry-euclidean/src/site/site.xml
@@ -28,8 +28,8 @@
<item name="Overview" href="/index.html"/>
<item name="Latest API docs (development)"
href="apidocs/index.html"/>
- <!-- <item name="Javadoc (1.0 release)"
- href="https://commons.apache.org/geometry/commons-geometry-euclidean/javadocs/api-1.0/index.html"/> -->
+ <item name="Javadoc (1.0 release)"
+ href="https://commons.apache.org/geometry/commons-geometry-euclidean/javadocs/api-1.0/index.html"/>
</menu>
diff --git a/commons-geometry-examples/examples-jmh/pom.xml b/commons-geometry-examples/examples-jmh/pom.xml
index 19778bf..6da6b92 100644
--- a/commons-geometry-examples/examples-jmh/pom.xml
+++ b/commons-geometry-examples/examples-jmh/pom.xml
@@ -21,7 +21,7 @@
<parent>
<groupId>org.apache.commons</groupId>
<artifactId>commons-geometry-examples</artifactId>
- <version>1.0-SNAPSHOT</version>
+ <version>1.0</version>
</parent>
<artifactId>commons-geometry-examples-jmh</artifactId>
diff --git a/commons-geometry-examples/examples-tutorials/pom.xml b/commons-geometry-examples/examples-tutorials/pom.xml
index 2772034..85e8c56 100644
--- a/commons-geometry-examples/examples-tutorials/pom.xml
+++ b/commons-geometry-examples/examples-tutorials/pom.xml
@@ -21,7 +21,7 @@
<parent>
<groupId>org.apache.commons</groupId>
<artifactId>commons-geometry-examples</artifactId>
- <version>1.0-SNAPSHOT</version>
+ <version>1.0</version>
</parent>
<artifactId>commons-geometry-examples-tutorials</artifactId>
diff --git a/commons-geometry-examples/pom.xml b/commons-geometry-examples/pom.xml
index 7ebe6d8..53e3884 100644
--- a/commons-geometry-examples/pom.xml
+++ b/commons-geometry-examples/pom.xml
@@ -21,7 +21,7 @@
<parent>
<groupId>org.apache.commons</groupId>
<artifactId>commons-geometry-parent</artifactId>
- <version>1.0-SNAPSHOT</version>
+ <version>1.0</version>
</parent>
<artifactId>commons-geometry-examples</artifactId>
diff --git a/commons-geometry-hull/CONTRIBUTING.md b/commons-geometry-hull/CONTRIBUTING.md
deleted file mode 100644
index 457bbfc..0000000
--- a/commons-geometry-hull/CONTRIBUTING.md
+++ /dev/null
@@ -1,115 +0,0 @@
-<!---
- Licensed to the Apache Software Foundation (ASF) under one or more
- contributor license agreements. See the NOTICE file distributed with
- this work for additional information regarding copyright ownership.
- The ASF licenses this file to You under the Apache License, Version 2.0
- (the "License"); you may not use this file except in compliance with
- the License. You may obtain a copy of the License at
-
- http://www.apache.org/licenses/LICENSE-2.0
-
- Unless required by applicable law or agreed to in writing, software
- distributed under the License is distributed on an "AS IS" BASIS,
- WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- See the License for the specific language governing permissions and
- limitations under the License.
--->
-<!---
- +======================================================================+
- |**** ****|
- |**** THIS FILE IS GENERATED BY THE COMMONS BUILD PLUGIN ****|
- |**** DO NOT EDIT DIRECTLY ****|
- |**** ****|
- +======================================================================+
- | TEMPLATE FILE: contributing-md-template.md |
- | commons-build-plugin/trunk/src/main/resources/commons-xdoc-templates |
- +======================================================================+
- | |
- | 1) Re-generate using: mvn commons-build:contributing-md |
- | |
- | 2) Set the following properties in the component's pom: |
- | - commons.jira.id (required, alphabetic, upper case) |
- | |
- | 3) Example Properties |
- | |
- | <properties> |
- | <commons.jira.id>MATH</commons.jira.id> |
- | </properties> |
- | |
- +======================================================================+
---->
-Contributing to Apache Commons Geometry Hull
-======================
-
-You have found a bug or you have an idea for a cool new feature? Contributing code is a great way to give something back to
-the open source community. Before you dig right into the code there are a few guidelines that we need contributors to
-follow so that we can have a chance of keeping on top of things.
-
-Getting Started
----------------
-
-+ Make sure you have a [JIRA account](https://issues.apache.org/jira/).
-+ Make sure you have a [GitHub account](https://github.com/signup/free).
-+ If you're planning to implement a new feature it makes sense to discuss your changes on the [dev list](https://commons.apache.org/mail-lists.html) first. This way you can make sure you're not wasting your time on something that isn't considered to be in Apache Commons Geometry Hull's scope.
-+ Submit a [Jira Ticket][jira] for your issue, assuming one does not already exist.
- + Clearly describe the issue including steps to reproduce when it is a bug.
- + Make sure you fill in the earliest version that you know has the issue.
-+ Find the corresponding [repository on GitHub](https://github.com/apache/?query=commons-),
-[fork](https://help.github.com/articles/fork-a-repo/) and check out your forked repository.
-
-Making Changes
---------------
-
-+ Create a _topic branch_ for your isolated work.
- * Usually you should base your branch on the `master` or `trunk` branch.
- * A good topic branch name can be the JIRA bug id plus a keyword, e.g. `GEOMETRY-123-InputStream`.
- * If you have submitted multiple JIRA issues, try to maintain separate branches and pull requests.
-+ Make commits of logical units.
- * Make sure your commit messages are meaningful and in the proper format. Your commit message should contain the key of the JIRA issue.
- * e.g. `GEOMETRY-123: Close input stream earlier`
-+ Respect the original code style:
- + Only use spaces for indentation.
- + Create minimal diffs - disable _On Save_ actions like _Reformat Source Code_ or _Organize Imports_. If you feel the source code should be reformatted create a separate PR for this change first.
- + Check for unnecessary whitespace with `git diff` -- check before committing.
-+ Make sure you have added the necessary tests for your changes, typically in `src/test/java`.
-+ Run all the tests with `mvn clean verify` to assure nothing else was accidentally broken.
-
-Making Trivial Changes
-----------------------
-
-The JIRA tickets are used to generate the changelog for the next release.
-
-For changes of a trivial nature to comments and documentation, it is not always necessary to create a new ticket in JIRA.
-In this case, it is appropriate to start the first line of a commit with '(doc)' instead of a ticket number.
-
-
-Submitting Changes
-------------------
-
-+ Sign and submit the Apache [Contributor License Agreement][cla] if you haven't already.
- * Note that small patches & typical bug fixes do not require a CLA as
- clause 5 of the [Apache License](https://www.apache.org/licenses/LICENSE-2.0.html#contributions)
- covers them.
-+ Push your changes to a topic branch in your fork of the repository.
-+ Submit a _Pull Request_ to the corresponding repository in the `apache` organization.
- * Verify _Files Changed_ shows only your intended changes and does not
- include additional files like `target/*.class`
-+ Update your JIRA ticket and include a link to the pull request in the ticket.
-
-If you prefer to not use GitHub, then you can instead use
-`git format-patch` (or `svn diff`) and attach the patch file to the JIRA issue.
-
-
-Additional Resources
---------------------
-
-+ [Contributing patches](https://commons.apache.org/patches.html)
-+ [Apache Commons Geometry Hull JIRA project page][jira]
-+ [Contributor License Agreement][cla]
-+ [General GitHub documentation](https://help.github.com/)
-+ [GitHub pull request documentation](https://help.github.com/articles/creating-a-pull-request/)
-+ [Apache Commons Twitter Account](https://twitter.com/ApacheCommons)
-+ `#apache-commons` IRC channel on `irc.freenode.net`
-
-[cla]:https://www.apache.org/licenses/#clas
-[jira]:https://issues.apache.org/jira/browse/GEOMETRY
diff --git a/commons-geometry-hull/LICENSE.txt b/commons-geometry-hull/LICENSE.txt
deleted file mode 100644
index 261eeb9..0000000
--- a/commons-geometry-hull/LICENSE.txt
+++ /dev/null
@@ -1,201 +0,0 @@
- Apache License
- Version 2.0, January 2004
- http://www.apache.org/licenses/
-
- TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION
-
- 1. Definitions.
-
- "License" shall mean the terms and conditions for use, reproduction,
- and distribution as defined by Sections 1 through 9 of this document.
-
- "Licensor" shall mean the copyright owner or entity authorized by
- the copyright owner that is granting the License.
-
- "Legal Entity" shall mean the union of the acting entity and all
- other entities that control, are controlled by, or are under common
- control with that entity. For the purposes of this definition,
- "control" means (i) the power, direct or indirect, to cause the
- direction or management of such entity, whether by contract or
- otherwise, or (ii) ownership of fifty percent (50%) or more of the
- outstanding shares, or (iii) beneficial ownership of such entity.
-
- "You" (or "Your") shall mean an individual or Legal Entity
- exercising permissions granted by this License.
-
- "Source" form shall mean the preferred form for making modifications,
- including but not limited to software source code, documentation
- source, and configuration files.
-
- "Object" form shall mean any form resulting from mechanical
- transformation or translation of a Source form, including but
- not limited to compiled object code, generated documentation,
- and conversions to other media types.
-
- "Work" shall mean the work of authorship, whether in Source or
- Object form, made available under the License, as indicated by a
- copyright notice that is included in or attached to the work
- (an example is provided in the Appendix below).
-
- "Derivative Works" shall mean any work, whether in Source or Object
- form, that is based on (or derived from) the Work and for which the
- editorial revisions, annotations, elaborations, or other modifications
- represent, as a whole, an original work of authorship. For the purposes
- of this License, Derivative Works shall not include works that remain
- separable from, or merely link (or bind by name) to the interfaces of,
- the Work and Derivative Works thereof.
-
- "Contribution" shall mean any work of authorship, including
- the original version of the Work and any modifications or additions
- to that Work or Derivative Works thereof, that is intentionally
- submitted to Licensor for inclusion in the Work by the copyright owner
- or by an individual or Legal Entity authorized to submit on behalf of
- the copyright owner. For the purposes of this definition, "submitted"
- means any form of electronic, verbal, or written communication sent
- to the Licensor or its representatives, including but not limited to
- communication on electronic mailing lists, source code control systems,
- and issue tracking systems that are managed by, or on behalf of, the
- Licensor for the purpose of discussing and improving the Work, but
- excluding communication that is conspicuously marked or otherwise
- designated in writing by the copyright owner as "Not a Contribution."
-
- "Contributor" shall mean Licensor and any individual or Legal Entity
- on behalf of whom a Contribution has been received by Licensor and
- subsequently incorporated within the Work.
-
- 2. Grant of Copyright License. Subject to the terms and conditions of
- this License, each Contributor hereby grants to You a perpetual,
- worldwide, non-exclusive, no-charge, royalty-free, irrevocable
- copyright license to reproduce, prepare Derivative Works of,
- publicly display, publicly perform, sublicense, and distribute the
- Work and such Derivative Works in Source or Object form.
-
- 3. Grant of Patent License. Subject to the terms and conditions of
- this License, each Contributor hereby grants to You a perpetual,
- worldwide, non-exclusive, no-charge, royalty-free, irrevocable
- (except as stated in this section) patent license to make, have made,
- use, offer to sell, sell, import, and otherwise transfer the Work,
- where such license applies only to those patent claims licensable
- by such Contributor that are necessarily infringed by their
- Contribution(s) alone or by combination of their Contribution(s)
- with the Work to which such Contribution(s) was submitted. If You
- institute patent litigation against any entity (including a
- cross-claim or counterclaim in a lawsuit) alleging that the Work
- or a Contribution incorporated within the Work constitutes direct
- or contributory patent infringement, then any patent licenses
- granted to You under this License for that Work shall terminate
- as of the date such litigation is filed.
-
- 4. Redistribution. You may reproduce and distribute copies of the
- Work or Derivative Works thereof in any medium, with or without
- modifications, and in Source or Object form, provided that You
- meet the following conditions:
-
- (a) You must give any other recipients of the Work or
- Derivative Works a copy of this License; and
-
- (b) You must cause any modified files to carry prominent notices
- stating that You changed the files; and
-
- (c) You must retain, in the Source form of any Derivative Works
- that You distribute, all copyright, patent, trademark, and
- attribution notices from the Source form of the Work,
- excluding those notices that do not pertain to any part of
- the Derivative Works; and
-
- (d) If the Work includes a "NOTICE" text file as part of its
- distribution, then any Derivative Works that You distribute must
- include a readable copy of the attribution notices contained
- within such NOTICE file, excluding those notices that do not
- pertain to any part of the Derivative Works, in at least one
- of the following places: within a NOTICE text file distributed
- as part of the Derivative Works; within the Source form or
- documentation, if provided along with the Derivative Works; or,
- within a display generated by the Derivative Works, if and
- wherever such third-party notices normally appear. The contents
- of the NOTICE file are for informational purposes only and
- do not modify the License. You may add Your own attribution
- notices within Derivative Works that You distribute, alongside
- or as an addendum to the NOTICE text from the Work, provided
- that such additional attribution notices cannot be construed
- as modifying the License.
-
- You may add Your own copyright statement to Your modifications and
- may provide additional or different license terms and conditions
- for use, reproduction, or distribution of Your modifications, or
- for any such Derivative Works as a whole, provided Your use,
- reproduction, and distribution of the Work otherwise complies with
- the conditions stated in this License.
-
- 5. Submission of Contributions. Unless You explicitly state otherwise,
- any Contribution intentionally submitted for inclusion in the Work
- by You to the Licensor shall be under the terms and conditions of
- this License, without any additional terms or conditions.
- Notwithstanding the above, nothing herein shall supersede or modify
- the terms of any separate license agreement you may have executed
- with Licensor regarding such Contributions.
-
- 6. Trademarks. This License does not grant permission to use the trade
- names, trademarks, service marks, or product names of the Licensor,
- except as required for reasonable and customary use in describing the
- origin of the Work and reproducing the content of the NOTICE file.
-
- 7. Disclaimer of Warranty. Unless required by applicable law or
- agreed to in writing, Licensor provides the Work (and each
- Contributor provides its Contributions) on an "AS IS" BASIS,
- WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
- implied, including, without limitation, any warranties or conditions
- of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A
- PARTICULAR PURPOSE. You are solely responsible for determining the
- appropriateness of using or redistributing the Work and assume any
- risks associated with Your exercise of permissions under this License.
-
- 8. Limitation of Liability. In no event and under no legal theory,
- whether in tort (including negligence), contract, or otherwise,
- unless required by applicable law (such as deliberate and grossly
- negligent acts) or agreed to in writing, shall any Contributor be
- liable to You for damages, including any direct, indirect, special,
- incidental, or consequential damages of any character arising as a
- result of this License or out of the use or inability to use the
- Work (including but not limited to damages for loss of goodwill,
- work stoppage, computer failure or malfunction, or any and all
- other commercial damages or losses), even if such Contributor
- has been advised of the possibility of such damages.
-
- 9. Accepting Warranty or Additional Liability. While redistributing
- the Work or Derivative Works thereof, You may choose to offer,
- and charge a fee for, acceptance of support, warranty, indemnity,
- or other liability obligations and/or rights consistent with this
- License. However, in accepting such obligations, You may act only
- on Your own behalf and on Your sole responsibility, not on behalf
- of any other Contributor, and only if You agree to indemnify,
- defend, and hold each Contributor harmless for any liability
- incurred by, or claims asserted against, such Contributor by reason
- of your accepting any such warranty or additional liability.
-
- END OF TERMS AND CONDITIONS
-
- APPENDIX: How to apply the Apache License to your work.
-
- To apply the Apache License to your work, attach the following
- boilerplate notice, with the fields enclosed by brackets "[]"
- replaced with your own identifying information. (Don't include
- the brackets!) The text should be enclosed in the appropriate
- comment syntax for the file format. We also recommend that a
- file or class name and description of purpose be included on the
- same "printed page" as the copyright notice for easier
- identification within third-party archives.
-
- Copyright [yyyy] [name of copyright owner]
-
- Licensed under the Apache License, Version 2.0 (the "License");
- you may not use this file except in compliance with the License.
- You may obtain a copy of the License at
-
- http://www.apache.org/licenses/LICENSE-2.0
-
- Unless required by applicable law or agreed to in writing, software
- distributed under the License is distributed on an "AS IS" BASIS,
- WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- See the License for the specific language governing permissions and
- limitations under the License.
diff --git a/commons-geometry-hull/NOTICE.txt b/commons-geometry-hull/NOTICE.txt
deleted file mode 100644
index 8d9849f..0000000
--- a/commons-geometry-hull/NOTICE.txt
+++ /dev/null
@@ -1,6 +0,0 @@
-Apache Commons Geometry
-Copyright 2020 The Apache Software Foundation
-
-This product includes software developed at
-The Apache Software Foundation (http://www.apache.org/).
-
diff --git a/commons-geometry-hull/README.md b/commons-geometry-hull/README.md
deleted file mode 100644
index 8ab4e1f..0000000
--- a/commons-geometry-hull/README.md
+++ /dev/null
@@ -1,105 +0,0 @@
-<!---
- Licensed to the Apache Software Foundation (ASF) under one or more
- contributor license agreements. See the NOTICE file distributed with
- this work for additional information regarding copyright ownership.
- The ASF licenses this file to You under the Apache License, Version 2.0
- (the "License"); you may not use this file except in compliance with
- the License. You may obtain a copy of the License at
-
- http://www.apache.org/licenses/LICENSE-2.0
-
- Unless required by applicable law or agreed to in writing, software
- distributed under the License is distributed on an "AS IS" BASIS,
- WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- See the License for the specific language governing permissions and
- limitations under the License.
--->
-<!---
- +======================================================================+
- |**** ****|
- |**** THIS FILE IS GENERATED BY THE COMMONS BUILD PLUGIN ****|
- |**** DO NOT EDIT DIRECTLY ****|
- |**** ****|
- +======================================================================+
- | TEMPLATE FILE: readme-md-template.md |
- | commons-build-plugin/trunk/src/main/resources/commons-xdoc-templates |
- +======================================================================+
- | |
- | 1) Re-generate using: mvn commons:readme-md |
- | |
- | 2) Set the following properties in the component's pom: |
- | - commons.componentid (required, alphabetic, lower case) |
- | - commons.release.version (required) |
- | |
- | 3) Example Properties |
- | |
- | <properties> |
- | <commons.componentid>math</commons.componentid> |
- | <commons.release.version>1.2</commons.release.version> |
- | </properties> |
- | |
- +======================================================================+
---->
-Apache Commons Geometry Hull
-===================
-
-[](https://travis-ci.org/apache/commons-geometry-hull)
-[](https://coveralls.io/r/apache/commons-geometry-hull)
-[](https://maven-badges.herokuapp.com/maven-central/org.apache.commons/commons-geometry-hull/)
-[](http://www.apache.org/licenses/LICENSE-2.0.html)
-
-Algorithms for computing convex hulls.
-
-Documentation
--------------
-
-More information can be found on the [Apache Commons Geometry Hull homepage](https://commons.apache.org/proper/commons-geometry).
-The [JavaDoc](https://commons.apache.org/proper/commons-geometry/javadocs/api-release) can be browsed.
-Questions related to the usage of Apache Commons Geometry Hull should be posted to the [user mailing list][ml].
-
-Where can I get the latest release?
------------------------------------
-You can download source and binaries from our [download page](https://commons.apache.org/proper/commons-geometry/download_geometry.cgi).
-
-Alternatively you can pull it from the central Maven repositories:
-
-```xml
-<dependency>
- <groupId>org.apache.commons</groupId>
- <artifactId>commons-geometry-hull</artifactId>
- <version>1.0-beta1</version>
-</dependency>
-```
-
-Contributing
-------------
-
-We accept Pull Requests via GitHub. The [developer mailing list][ml] is the main channel of communication for contributors.
-There are some guidelines which will make applying PRs easier for us:
-+ No tabs! Please use spaces for indentation.
-+ Respect the code style.
-+ Create minimal diffs - disable on save actions like reformat source code or organize imports. If you feel the source code should be reformatted create a separate PR for this change.
-+ Provide JUnit tests for your changes and make sure your changes don't break any existing tests by running ```mvn clean test```.
-
-If you plan to contribute on a regular basis, please consider filing a [contributor license agreement](https://www.apache.org/licenses/#clas).
-You can learn more about contributing via GitHub in our [contribution guidelines](CONTRIBUTING.md).
-
-License
--------
-This code is under the [Apache Licence v2](https://www.apache.org/licenses/LICENSE-2.0).
-
-See the `NOTICE.txt` file for required notices and attributions.
-
-Donations
----------
-You like Apache Commons Geometry Hull? Then [donate back to the ASF](https://www.apache.org/foundation/contributing.html) to support the development.
-
-Additional Resources
---------------------
-
-+ [Apache Commons Homepage](https://commons.apache.org/)
-+ [Apache Issue Tracker (JIRA)](https://issues.apache.org/jira/browse/GEOMETRY)
-+ [Apache Commons Twitter Account](https://twitter.com/ApacheCommons)
-+ `#apache-commons` IRC channel on `irc.freenode.org`
-
-[ml]:https://commons.apache.org/mail-lists.html
diff --git a/commons-geometry-hull/pom.xml b/commons-geometry-hull/pom.xml
deleted file mode 100644
index d12b4e4..0000000
--- a/commons-geometry-hull/pom.xml
+++ /dev/null
@@ -1,96 +0,0 @@
-<?xml version="1.0"?>
-<!--
- Licensed to the Apache Software Foundation (ASF) under one or more
- contributor license agreements. See the NOTICE file distributed with
- this work for additional information regarding copyright ownership.
- The ASF licenses this file to You under the Apache License, Version 2.0
- (the "License"); you may not use this file except in compliance with
- the License. You may obtain a copy of the License at
-
- http://www.apache.org/licenses/LICENSE-2.0
-
- Unless required by applicable law or agreed to in writing, software
- distributed under the License is distributed on an "AS IS" BASIS,
- WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- See the License for the specific language governing permissions and
- limitations under the License.
--->
-<project xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd"
- xmlns="http://maven.apache.org/POM/4.0.0"
- xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance">
- <modelVersion>4.0.0</modelVersion>
-
- <parent>
- <groupId>org.apache.commons</groupId>
- <artifactId>commons-geometry-parent</artifactId>
- <version>1.0-SNAPSHOT</version>
- </parent>
-
- <artifactId>commons-geometry-hull</artifactId>
- <name>Apache Commons Geometry Hull</name>
-
- <description>Algorithms for computing convex hulls.</description>
-
- <properties>
- <!-- OSGi -->
- <commons.osgi.symbolicName>org.apache.commons.geometry.hull</commons.osgi.symbolicName>
- <commons.osgi.export>org.apache.commons.geometry.hull.*</commons.osgi.export>
- <!-- Java 9+ -->
- <commons.automatic.module.name>org.apache.commons.geometry.hull</commons.automatic.module.name>
- <!-- Workaround to avoid duplicating config files. -->
- <geometry.parent.dir>${basedir}/..</geometry.parent.dir>
- </properties>
-
- <dependencies>
- <dependency>
- <groupId>org.apache.commons</groupId>
- <artifactId>commons-geometry-core</artifactId>
- <version>${project.version}</version>
- </dependency>
- <dependency>
- <groupId>org.apache.commons</groupId>
- <artifactId>commons-geometry-euclidean</artifactId>
- <version>${project.version}</version>
- </dependency>
-
- <dependency>
- <groupId>org.apache.commons</groupId>
- <artifactId>commons-geometry-core</artifactId>
- <version>${project.version}</version>
- <classifier>tests</classifier>
- <type>test-jar</type>
- <scope>test</scope>
- </dependency>
- <dependency>
- <groupId>org.apache.commons</groupId>
- <artifactId>commons-geometry-euclidean</artifactId>
- <version>${project.version}</version>
- <classifier>tests</classifier>
- <type>test-jar</type>
- <scope>test</scope>
- </dependency>
-
- <dependency>
- <groupId>org.apache.commons</groupId>
- <artifactId>commons-rng-client-api</artifactId>
- <scope>test</scope>
- </dependency>
- <dependency>
- <groupId>org.apache.commons</groupId>
- <artifactId>commons-rng-simple</artifactId>
- <scope>test</scope>
- </dependency>
- <dependency>
- <groupId>org.apache.commons</groupId>
- <artifactId>commons-rng-sampling</artifactId>
- <scope>test</scope>
- </dependency>
- <!-- testing -->
- <dependency>
- <groupId>org.junit.jupiter</groupId>
- <artifactId>junit-jupiter</artifactId>
- <scope>test</scope>
- </dependency>
- </dependencies>
-
-</project>
diff --git a/commons-geometry-hull/src/main/java/org/apache/commons/geometry/hull/ConvexHull.java b/commons-geometry-hull/src/main/java/org/apache/commons/geometry/hull/ConvexHull.java
deleted file mode 100644
index 09a7477..0000000
--- a/commons-geometry-hull/src/main/java/org/apache/commons/geometry/hull/ConvexHull.java
+++ /dev/null
@@ -1,44 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements. See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-package org.apache.commons.geometry.hull;
-
-import java.util.List;
-
-import org.apache.commons.geometry.core.Point;
-import org.apache.commons.geometry.core.Region;
-
-/**
- * This class represents a convex hull.
- *
- * @param <P> Point implementation type.
- */
-public interface ConvexHull<P extends Point<P>> {
-
- /** Get the vertices of the convex hull.
- * @return vertices of the convex hull
- */
- List<P> getVertices();
-
- /** Return the region representing the convex hull. This will return
- * null in cases where the hull does not define a region with non-zero
- * size, such as when only a single unique point exists or when all points
- * are collinear.
- * @return the region representing by the convex hull or null if the
- * convex hull does not define a region of non-zero size
- */
- Region<P> getRegion();
-}
diff --git a/commons-geometry-hull/src/main/java/org/apache/commons/geometry/hull/ConvexHullGenerator.java b/commons-geometry-hull/src/main/java/org/apache/commons/geometry/hull/ConvexHullGenerator.java
deleted file mode 100644
index 3db030b..0000000
--- a/commons-geometry-hull/src/main/java/org/apache/commons/geometry/hull/ConvexHullGenerator.java
+++ /dev/null
@@ -1,41 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements. See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-package org.apache.commons.geometry.hull;
-
-import java.util.Collection;
-
-import org.apache.commons.geometry.core.Point;
-
-/**
- * Interface for convex hull generators.
- *
- * @param <P> Type of the {@link Point}
- *
- * @see <a href="http://en.wikipedia.org/wiki/Convex_hull">Convex Hull (Wikipedia)</a>
- * @see <a href="http://mathworld.wolfram.com/ConvexHull.html">Convex Hull (MathWorld)</a>
- */
-public interface ConvexHullGenerator<P extends Point<P>> {
- /**
- * Build a convex hull from the set of input points.
- *
- * @param points the set of input points
- * @return the convex hull
- * @throws IllegalStateException if generator fails to generate a convex hull for
- * the given set of input points
- */
- ConvexHull<P> generate(Collection<P> points);
-}
diff --git a/commons-geometry-hull/src/main/java/org/apache/commons/geometry/hull/euclidean/twod/AbstractConvexHullGenerator2D.java b/commons-geometry-hull/src/main/java/org/apache/commons/geometry/hull/euclidean/twod/AbstractConvexHullGenerator2D.java
deleted file mode 100644
index 45649d9..0000000
--- a/commons-geometry-hull/src/main/java/org/apache/commons/geometry/hull/euclidean/twod/AbstractConvexHullGenerator2D.java
+++ /dev/null
@@ -1,130 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements. See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-package org.apache.commons.geometry.hull.euclidean.twod;
-
-import java.util.Collection;
-import java.util.Iterator;
-
-import org.apache.commons.geometry.euclidean.twod.Vector2D;
-import org.apache.commons.numbers.core.Precision;
-
-/**
- * Abstract base class for convex hull generators in the two-dimensional Euclidean space.
- */
-abstract class AbstractConvexHullGenerator2D implements ConvexHullGenerator2D {
-
- /** Precision context used to compare floating point numbers. */
- private final Precision.DoubleEquivalence precision;
-
- /**
- * Indicates if collinear points on the hull shall be present in the output.
- * If {@code false}, only the extreme points are added to the hull.
- */
- private final boolean includeCollinearPoints;
-
- /**
- * Simple constructor.
- *
- * @param includeCollinearPoints indicates if collinear points on the hull shall be
- * added as hull vertices
- * @param precision precision context used to compare floating point numbers
- */
- protected AbstractConvexHullGenerator2D(final boolean includeCollinearPoints,
- final Precision.DoubleEquivalence precision) {
- this.includeCollinearPoints = includeCollinearPoints;
- this.precision = precision;
- }
-
- /** Get the object used to determine floating point equality for this region.
- * @return the floating point precision context for the instance
- */
- public Precision.DoubleEquivalence getPrecision() {
- return precision;
- }
-
- /**
- * Returns if collinear points on the hull will be added as hull vertices.
- * @return {@code true} if collinear points are added as hull vertices, or {@code false}
- * if only extreme points are present.
- */
- public boolean isIncludeCollinearPoints() {
- return includeCollinearPoints;
- }
-
- /** {@inheritDoc} */
- @Override
- public ConvexHull2D generate(final Collection<Vector2D> points) {
- Collection<Vector2D> hullVertices;
- if (points.size() < 2) {
- hullVertices = points;
- } else {
- hullVertices = findHullVertices(points);
- }
-
- if (!isConvex(hullVertices)) {
- throw new IllegalStateException("Convex hull algorithm failed to generate solution");
- }
-
- return new ConvexHull2D(hullVertices, precision);
- }
-
- /**
- * Find the convex hull vertices from the set of input points.
- * @param points the set of input points
- * @return the convex hull vertices in CCW winding
- */
- protected abstract Collection<Vector2D> findHullVertices(Collection<Vector2D> points);
-
- /** Return true if the given vertices define a convex hull.
- * @param vertices the hull vertices
- * @return {@code true} if the vertices form a convex hull, {@code false} otherwise
- */
- private boolean isConvex(final Collection<Vector2D> vertices) {
- final int size = vertices.size();
-
- if (size < 3) {
- // 1 or 2 points always define a convex set
- return true;
- }
-
- final Iterator<Vector2D> it = vertices.iterator();
-
- Vector2D p1 = it.next();
- Vector2D p2 = it.next();
- Vector2D p3;
-
- Vector2D v1;
- Vector2D v2;
-
- while (it.hasNext()) {
- p3 = it.next();
-
- v1 = p1.vectorTo(p2);
- v2 = p2.vectorTo(p3);
-
- // negative signed areas mean a clockwise winding
- if (precision.compare(v1.signedArea(v2), 0.0) < 0) {
- return false;
- }
-
- p1 = p2;
- p2 = p3;
- }
-
- return true;
- }
-}
diff --git a/commons-geometry-hull/src/main/java/org/apache/commons/geometry/hull/euclidean/twod/AklToussaintHeuristic.java b/commons-geometry-hull/src/main/java/org/apache/commons/geometry/hull/euclidean/twod/AklToussaintHeuristic.java
deleted file mode 100644
index 15be662..0000000
--- a/commons-geometry-hull/src/main/java/org/apache/commons/geometry/hull/euclidean/twod/AklToussaintHeuristic.java
+++ /dev/null
@@ -1,163 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements. See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-package org.apache.commons.geometry.hull.euclidean.twod;
-
-import java.util.ArrayList;
-import java.util.Collection;
-import java.util.List;
-
-import org.apache.commons.geometry.euclidean.twod.Vector2D;
-
-/**
- * A simple heuristic to improve the performance of convex hull algorithms.
- * <p>
- * The heuristic is based on the idea of a convex quadrilateral, which is formed by
- * four points with the lowest and highest x / y coordinates. Any point that lies inside
- * this quadrilateral can not be part of the convex hull and can thus be safely discarded
- * before generating the convex hull itself.
- * <p>
- * The complexity of the operation is O(n), and may greatly improve the time it takes to
- * construct the convex hull afterwards, depending on the point distribution.
- *
- * @see <a href="http://en.wikipedia.org/wiki/Convex_hull_algorithms#Akl-Toussaint_heuristic">
- * Akl-Toussaint heuristic (Wikipedia)</a>
- */
-public final class AklToussaintHeuristic {
-
- /** Hide utility constructor. */
- private AklToussaintHeuristic() {
- }
-
- /**
- * Returns a point set that is reduced by all points for which it is safe to assume
- * that they are not part of the convex hull.
- *
- * @param points the original point set
- * @return a reduced point set, useful as input for convex hull algorithms
- */
- public static Collection<Vector2D> reducePoints(final Collection<Vector2D> points) {
-
- // find the leftmost point
- int size = 0;
- Vector2D minX = null;
- Vector2D maxX = null;
- Vector2D minY = null;
- Vector2D maxY = null;
- for (final Vector2D p : points) {
- if (minX == null || p.getX() < minX.getX()) {
- minX = p;
- }
- if (maxX == null || p.getX() > maxX.getX()) {
- maxX = p;
- }
- if (minY == null || p.getY() < minY.getY()) {
- minY = p;
- }
- if (maxY == null || p.getY() > maxY.getY()) {
- maxY = p;
- }
- size++;
- }
-
- if (size < 4) {
- return points;
- }
-
- final List<Vector2D> quadrilateral = buildQuadrilateral(minY, maxX, maxY, minX);
- // if the quadrilateral is not well formed, e.g. only 2 points, do not attempt to reduce
- if (quadrilateral.size() < 3) {
- return points;
- }
-
- final List<Vector2D> reducedPoints = new ArrayList<>(quadrilateral);
- for (final Vector2D p : points) {
- // check all points if they are within the quadrilateral
- // in which case they can not be part of the convex hull
- if (!insideQuadrilateral(p, quadrilateral)) {
- reducedPoints.add(p);
- }
- }
-
- return reducedPoints;
- }
-
- /**
- * Build the convex quadrilateral with the found corner points (with min/max x/y coordinates).
- *
- * @param points the respective points with min/max x/y coordinate
- * @return the quadrilateral
- */
- private static List<Vector2D> buildQuadrilateral(final Vector2D... points) {
- final List<Vector2D> quadrilateral = new ArrayList<>();
- for (final Vector2D p : points) {
- if (!quadrilateral.contains(p)) {
- quadrilateral.add(p);
- }
- }
- return quadrilateral;
- }
-
- /**
- * Checks if the given point is located within the convex quadrilateral.
- * @param point the point to check
- * @param quadrilateralPoints the convex quadrilateral, represented by 4 points
- * @return {@code true} if the point is inside the quadrilateral, {@code false} otherwise
- */
- private static boolean insideQuadrilateral(final Vector2D point,
- final List<? extends Vector2D> quadrilateralPoints) {
-
- Vector2D v1 = quadrilateralPoints.get(0);
- Vector2D v2 = quadrilateralPoints.get(1);
-
- if (point.equals(v1) || point.equals(v2)) {
- return true;
- }
-
- // get the location of the point relative to the first two vertices
- final double last = signedAreaPoints(v1, v2, point);
- final int size = quadrilateralPoints.size();
- // loop through the rest of the vertices
- for (int i = 1; i < size; i++) {
- v1 = v2;
- v2 = quadrilateralPoints.get((i + 1) == size ? 0 : i + 1);
-
- if (point.equals(v2)) {
- return true;
- }
-
- // do side of line test: multiply the last location with this location
- // if they are the same sign then the operation will yield a positive result
- // -x * -y = +xy, x * y = +xy, -x * y = -xy, x * -y = -xy
- if (last * signedAreaPoints(v1, v2, point) < 0) {
- return false;
- }
- }
- return true;
- }
-
- /** Compute the signed area of the parallelogram formed by vectors between the given points. The first
- * vector points from {@code p0} to {@code p1} and the second from {@code p0} to {@code p3}.
- * @param p0 first point
- * @param p1 second point
- * @param p2 third point
- * @return signed area of parallelogram formed by vectors between the given points
- */
- private static double signedAreaPoints(final Vector2D p0, final Vector2D p1, final Vector2D p2) {
- return p0.vectorTo(p1).signedArea(p0.vectorTo(p2));
- }
-
-}
diff --git a/commons-geometry-hull/src/main/java/org/apache/commons/geometry/hull/euclidean/twod/ConvexHull2D.java b/commons-geometry-hull/src/main/java/org/apache/commons/geometry/hull/euclidean/twod/ConvexHull2D.java
deleted file mode 100644
index cf6cf50..0000000
--- a/commons-geometry-hull/src/main/java/org/apache/commons/geometry/hull/euclidean/twod/ConvexHull2D.java
+++ /dev/null
@@ -1,107 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements. See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-package org.apache.commons.geometry.hull.euclidean.twod;
-
-import java.util.ArrayList;
-import java.util.Collection;
-import java.util.Collections;
-import java.util.List;
-
-import org.apache.commons.geometry.euclidean.twod.ConvexArea;
-import org.apache.commons.geometry.euclidean.twod.Vector2D;
-import org.apache.commons.geometry.euclidean.twod.path.LinePath;
-import org.apache.commons.geometry.hull.ConvexHull;
-import org.apache.commons.numbers.core.Precision;
-
-/**
- * This class represents a convex hull in two-dimensional Euclidean space.
- */
-public final class ConvexHull2D implements ConvexHull<Vector2D> {
-
- /** Vertices for the convex hull, in order. */
- private final List<Vector2D> vertices;
-
- /** Polyline path for the convex hull. */
- private final LinePath path;
-
- /** Simple constructor; no validation is performed.
- * @param vertices the vertices of the convex hull; callers are responsible for ensuring that
- * the given vertices are in order, unique, and define a convex hull.
- * @param precision precision context used to compare floating point numbers
- */
- ConvexHull2D(final Collection<Vector2D> vertices, final Precision.DoubleEquivalence precision) {
- this.vertices = Collections.unmodifiableList(new ArrayList<>(vertices));
- this.path = buildHullPath(vertices, precision);
- }
-
- /** {@inheritDoc} */
- @Override
- public List<Vector2D> getVertices() {
- return vertices;
- }
-
- /** Get a path defining the convex hull. The path will contain
- * <ul>
- * <li>zero segments if the hull consists of only a single point,</li>
- * <li>one segment if the hull consists of two points,</li>
- * <li>three or more segments defining a closed loop if the hull consists of more than
- * two non-collinear points.</li>
- * </ul>
- * @return polyline path defining the convex hull
- */
- public LinePath getPath() {
- return path;
- }
-
- /** {@inheritDoc} */
- @Override
- public ConvexArea getRegion() {
- return path.isClosed() ?
- ConvexArea.convexPolygonFromPath(path) :
- null;
- }
-
- /** {@inheritDoc} */
- @Override
- public String toString() {
- final StringBuilder sb = new StringBuilder();
- sb.append(getClass().getSimpleName())
- .append("[vertices= ")
- .append(getVertices())
- .append(']');
-
- return sb.toString();
- }
-
- /** Build a polyline representing the path for a convex hull.
- * @param vertices convex hull vertices
- * @param precision precision context used to compare floating point values
- * @return path for the convex hull defined by the given vertices
- */
- private static LinePath buildHullPath(final Collection<Vector2D> vertices,
- final Precision.DoubleEquivalence precision) {
- if (vertices.size() < 2) {
- return LinePath.empty();
- }
-
- final boolean closeLoop = vertices.size() > 2;
-
- return LinePath.builder(precision)
- .appendVertices(vertices)
- .build(closeLoop);
- }
-}
diff --git a/commons-geometry-hull/src/main/java/org/apache/commons/geometry/hull/euclidean/twod/ConvexHullGenerator2D.java b/commons-geometry-hull/src/main/java/org/apache/commons/geometry/hull/euclidean/twod/ConvexHullGenerator2D.java
deleted file mode 100644
index bd8caa7..0000000
--- a/commons-geometry-hull/src/main/java/org/apache/commons/geometry/hull/euclidean/twod/ConvexHullGenerator2D.java
+++ /dev/null
@@ -1,32 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements. See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-package org.apache.commons.geometry.hull.euclidean.twod;
-
-import java.util.Collection;
-
-import org.apache.commons.geometry.euclidean.twod.Vector2D;
-import org.apache.commons.geometry.hull.ConvexHullGenerator;
-
-/**
- * Interface for convex hull generators in the two-dimensional Euclidean space.
- */
-public interface ConvexHullGenerator2D extends ConvexHullGenerator<Vector2D> {
-
- /** {@inheritDoc} */
- @Override
- ConvexHull2D generate(Collection<Vector2D> points);
-}
diff --git a/commons-geometry-hull/src/main/java/org/apache/commons/geometry/hull/euclidean/twod/MonotoneChain.java b/commons-geometry-hull/src/main/java/org/apache/commons/geometry/hull/euclidean/twod/MonotoneChain.java
deleted file mode 100644
index b521727..0000000
--- a/commons-geometry-hull/src/main/java/org/apache/commons/geometry/hull/euclidean/twod/MonotoneChain.java
+++ /dev/null
@@ -1,162 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements. See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-package org.apache.commons.geometry.hull.euclidean.twod;
-
-import java.util.ArrayList;
-import java.util.Collection;
-import java.util.List;
-
-import org.apache.commons.geometry.euclidean.twod.Lines;
-import org.apache.commons.geometry.euclidean.twod.Vector2D;
-import org.apache.commons.numbers.core.Precision;
-
-/**
- * Implements Andrew's monotone chain method to generate the convex hull of a finite set of
- * points in the two-dimensional Euclidean space.
- * <p>
- * The runtime complexity is O(n log n), with n being the number of input points. If the
- * point set is already sorted (by x-coordinate), the runtime complexity is O(n).
- * <p>
- * The implementation is not sensitive to collinear points on the hull. The parameter
- * {@code includeCollinearPoints} allows to control the behavior with regard to collinear points.
- * If {@code true}, all points on the boundary of the hull will be added to the hull vertices,
- * otherwise only the extreme points will be present. By default, collinear points are not added
- * as hull vertices.
- * <p>
- *
- * @see <a href="http://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain">
- * Andrew's monotone chain algorithm (Wikibooks)</a>
- */
-public class MonotoneChain extends AbstractConvexHullGenerator2D {
-
- /** Create a new instance that only includes extreme points as hull vertices.
- * @param precision precision context used to compare floating point numbers
- */
- public MonotoneChain(final Precision.DoubleEquivalence precision) {
- this(false, precision);
- }
-
- /** Create a new instance with the given parameters.
- * @param includeCollinearPoints whether collinear points shall be added as hull vertices
- * @param precision precision context used to compare floating point numbers
- */
- public MonotoneChain(final boolean includeCollinearPoints, final Precision.DoubleEquivalence precision) {
- super(includeCollinearPoints, precision);
- }
-
- /** {@inheritDoc} */
- @Override
- public Collection<Vector2D> findHullVertices(final Collection<Vector2D> points) {
-
- final List<Vector2D> pointsSortedByXAxis = new ArrayList<>(points);
-
- // sort the points in increasing order on the x-axis
- pointsSortedByXAxis.sort((o1, o2) -> {
- final Precision.DoubleEquivalence precision = getPrecision();
- // need to take the tolerance value into account, otherwise collinear points
- // will not be handled correctly when building the upper/lower hull
- final int cmp = precision.compare(o1.getX(), o2.getX());
- if (cmp == 0) {
- return precision.compare(o1.getY(), o2.getY());
- } else {
- return cmp;
- }
- });
-
- // build lower hull
- final List<Vector2D> lowerHull = new ArrayList<>();
- for (final Vector2D p : pointsSortedByXAxis) {
- updateHull(p, lowerHull);
- }
-
- // build upper hull
- final List<Vector2D> upperHull = new ArrayList<>();
- for (int idx = pointsSortedByXAxis.size() - 1; idx >= 0; idx--) {
- final Vector2D p = pointsSortedByXAxis.get(idx);
- updateHull(p, upperHull);
- }
-
- // concatenate the lower and upper hulls
- // the last point of each list is omitted as it is repeated at the beginning of the other list
- final List<Vector2D> hullVertices = new ArrayList<>(lowerHull.size() + upperHull.size() - 2);
- for (int idx = 0; idx < lowerHull.size() - 1; idx++) {
- hullVertices.add(lowerHull.get(idx));
- }
- for (int idx = 0; idx < upperHull.size() - 1; idx++) {
- hullVertices.add(upperHull.get(idx));
- }
-
- // special case: if the lower and upper hull may contain only 1 point if all are identical
- if (hullVertices.isEmpty() && !lowerHull.isEmpty()) {
- hullVertices.add(lowerHull.get(0));
- }
-
- return hullVertices;
- }
-
- /**
- * Update the partial hull with the current point.
- *
- * @param point the current point
- * @param hull the partial hull
- */
- private void updateHull(final Vector2D point, final List<Vector2D> hull) {
- final Precision.DoubleEquivalence precision = getPrecision();
-
- if (hull.size() == 1) {
- // ensure that we do not add an identical point
- final Vector2D p1 = hull.get(0);
- if (p1.eq(point, precision)) {
- return;
- }
- }
-
- while (hull.size() >= 2) {
- final int size = hull.size();
- final Vector2D p1 = hull.get(size - 2);
- final Vector2D p2 = hull.get(size - 1);
-
- final double offset = Lines.fromPoints(p1, p2, precision).offset(point);
- if (precision.eqZero(offset)) {
- // the point is collinear to the line (p1, p2)
-
- final double distanceToCurrent = p1.distance(point);
- if (precision.eqZero(distanceToCurrent) || precision.eqZero(p2.distance(point))) {
- // the point is assumed to be identical to either p1 or p2
- return;
- }
-
- final double distanceToLast = p1.distance(p2);
- if (isIncludeCollinearPoints()) {
- final int index = distanceToCurrent < distanceToLast ? size - 1 : size;
- hull.add(index, point);
- } else {
- if (distanceToCurrent > distanceToLast) {
- hull.remove(size - 1);
- hull.add(point);
- }
- }
- return;
- } else if (offset > 0) {
- hull.remove(size - 1);
- } else {
- break;
- }
- }
- hull.add(point);
- }
-}
diff --git a/commons-geometry-hull/src/main/java/org/apache/commons/geometry/hull/euclidean/twod/package-info.java b/commons-geometry-hull/src/main/java/org/apache/commons/geometry/hull/euclidean/twod/package-info.java
deleted file mode 100644
index ca9ae62..0000000
--- a/commons-geometry-hull/src/main/java/org/apache/commons/geometry/hull/euclidean/twod/package-info.java
+++ /dev/null
@@ -1,25 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements. See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-/**
- *
- * <p>
- * This package provides algorithms to generate the convex hull
- * for a set of points in an two-dimensional Euclidean space.
- * </p>
- *
- */
-package org.apache.commons.geometry.hull.euclidean.twod;
diff --git a/commons-geometry-hull/src/main/java/org/apache/commons/geometry/hull/package-info.java b/commons-geometry-hull/src/main/java/org/apache/commons/geometry/hull/package-info.java
deleted file mode 100644
index c52c08c..0000000
--- a/commons-geometry-hull/src/main/java/org/apache/commons/geometry/hull/package-info.java
+++ /dev/null
@@ -1,24 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements. See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-/**
- *
- * <p>
- * This package provides interfaces and classes related to the convex hull problem.
- * </p>
- *
- */
-package org.apache.commons.geometry.hull;
diff --git a/commons-geometry-hull/src/test/java/org/apache/commons/geometry/hull/DocumentationExamplesTest.java b/commons-geometry-hull/src/test/java/org/apache/commons/geometry/hull/DocumentationExamplesTest.java
deleted file mode 100644
index 6a00f91..0000000
--- a/commons-geometry-hull/src/test/java/org/apache/commons/geometry/hull/DocumentationExamplesTest.java
+++ /dev/null
@@ -1,76 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements. See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-package org.apache.commons.geometry.hull;
-
-import java.util.Arrays;
-import java.util.List;
-
-import org.apache.commons.geometry.euclidean.EuclideanTestUtils;
-import org.apache.commons.geometry.euclidean.twod.ConvexArea;
-import org.apache.commons.geometry.euclidean.twod.Vector2D;
-import org.apache.commons.geometry.hull.euclidean.twod.ConvexHull2D;
-import org.apache.commons.geometry.hull.euclidean.twod.MonotoneChain;
-import org.apache.commons.numbers.core.Precision;
-import org.junit.jupiter.api.Assertions;
-import org.junit.jupiter.api.Test;
-
-/** This class contains code listed as examples in the user guide and other documentation.
- * If any portion of this code changes, the corresponding examples in the documentation <em>must</em> be updated.
- */
-class DocumentationExamplesTest {
-
- private static final double TEST_EPS = 1e-15;
-
- @Test
- void testMonotoneChainExample() {
- final Precision.DoubleEquivalence precision = Precision.doubleEquivalenceOfEpsilon(1e-10);
-
- // create a list of input points for the algorithm
- final List<Vector2D> pts = Arrays.asList(
- Vector2D.ZERO,
- Vector2D.of(0.5, 0.5),
- Vector2D.of(0, 0.5),
- Vector2D.of(0, 1),
- Vector2D.of(0.25, 0.1),
- Vector2D.of(1, 0),
- Vector2D.of(1, 1),
- Vector2D.of(0.75, 0.9)
- );
-
- // create an instance of the monotone chain convex hull generator
- final MonotoneChain mc = new MonotoneChain(precision);
-
- // compute the convex hull
- final ConvexHull2D hull = mc.generate(pts);
-
- // list the vertices from the input that were used in the hull
- final List<Vector2D> vertices = hull.getVertices(); // [(0.0, 0.0), (1.0, 0.0), (1.0, 1.0), (0.0, 1.0)]
-
- // get the hull as a region
- final ConvexArea region = hull.getRegion();
- final boolean containsAll = pts.stream().allMatch(region::contains); // true - region contains all input points
-
- // ---
- Assertions.assertEquals(4, vertices.size());
- EuclideanTestUtils.assertCoordinatesEqual(Vector2D.ZERO, vertices.get(0), TEST_EPS);
- EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(1, 0), vertices.get(1), TEST_EPS);
- EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(1, 1), vertices.get(2), TEST_EPS);
- EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(0, 1), vertices.get(3), TEST_EPS);
-
- Assertions.assertTrue(containsAll);
- }
-}
diff --git a/commons-geometry-hull/src/test/java/org/apache/commons/geometry/hull/euclidean/twod/AklToussaintHeuristicTest.java b/commons-geometry-hull/src/test/java/org/apache/commons/geometry/hull/euclidean/twod/AklToussaintHeuristicTest.java
deleted file mode 100644
index 0f08c8d..0000000
--- a/commons-geometry-hull/src/test/java/org/apache/commons/geometry/hull/euclidean/twod/AklToussaintHeuristicTest.java
+++ /dev/null
@@ -1,38 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements. See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-package org.apache.commons.geometry.hull.euclidean.twod;
-
-import java.util.Collection;
-
-import org.apache.commons.geometry.euclidean.twod.Vector2D;
-
-/**
- * Test class for AklToussaintHeuristic.
- */
-class AklToussaintHeuristicTest extends ConvexHullGenerator2DAbstractTest {
-
- @Override
- protected ConvexHullGenerator2D createConvexHullGenerator(final boolean includeCollinearPoints) {
- return new MonotoneChain(includeCollinearPoints, TEST_PRECISION);
- }
-
- @Override
- protected Collection<Vector2D> reducePoints(final Collection<Vector2D> points) {
- return AklToussaintHeuristic.reducePoints(points);
- }
-
-}
diff --git a/commons-geometry-hull/src/test/java/org/apache/commons/geometry/hull/euclidean/twod/ConvexHull2DTest.java b/commons-geometry-hull/src/test/java/org/apache/commons/geometry/hull/euclidean/twod/ConvexHull2DTest.java
deleted file mode 100644
index 85ad53c..0000000
--- a/commons-geometry-hull/src/test/java/org/apache/commons/geometry/hull/euclidean/twod/ConvexHull2DTest.java
+++ /dev/null
@@ -1,177 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements. See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-package org.apache.commons.geometry.hull.euclidean.twod;
-
-import java.util.ArrayList;
-import java.util.Arrays;
-import java.util.Collections;
-import java.util.List;
-
-import org.apache.commons.geometry.core.GeometryTestUtils;
-import org.apache.commons.geometry.euclidean.EuclideanTestUtils;
-import org.apache.commons.geometry.euclidean.twod.Vector2D;
-import org.apache.commons.geometry.euclidean.twod.path.LinePath;
-import org.apache.commons.numbers.core.Precision;
-import org.junit.jupiter.api.Assertions;
-import org.junit.jupiter.api.Test;
-
-class ConvexHull2DTest {
-
- private static final double TEST_EPS = 1e-10;
-
- private static final Precision.DoubleEquivalence TEST_PRECISION =
- Precision.doubleEquivalenceOfEpsilon(TEST_EPS);
-
- @Test
- void testProperties_noPoints() {
- // act
- final ConvexHull2D hull = new ConvexHull2D(Collections.emptyList(), TEST_PRECISION);
-
- // assert
- Assertions.assertEquals(0, hull.getVertices().size());
-
- final LinePath path = hull.getPath();
- Assertions.assertEquals(0, path.getElements().size());
-
- final List<Vector2D> pathVertices = path.getVertexSequence();
- Assertions.assertEquals(0, pathVertices.size());
-
- Assertions.assertNull(hull.getRegion());
- }
-
- @Test
- void testProperties_singlePoint() {
- // arrange
- final List<Vector2D> vertices = Collections.singletonList(Vector2D.Unit.PLUS_X);
-
- // act
- final ConvexHull2D hull = new ConvexHull2D(vertices, TEST_PRECISION);
-
- // assert
- Assertions.assertEquals(vertices, hull.getVertices());
-
- final LinePath path = hull.getPath();
- Assertions.assertEquals(0, path.getElements().size());
-
- final List<Vector2D> pathVertices = path.getVertexSequence();
- Assertions.assertEquals(0, pathVertices.size());
-
- Assertions.assertNull(hull.getRegion());
- }
-
- @Test
- void testProperties_twoPoints() {
- // arrange
- final List<Vector2D> vertices = Arrays.asList(Vector2D.Unit.PLUS_X, Vector2D.Unit.PLUS_Y);
-
- // act
- final ConvexHull2D hull = new ConvexHull2D(vertices, TEST_PRECISION);
-
- // assert
- Assertions.assertEquals(vertices, hull.getVertices());
-
- final LinePath path = hull.getPath();
- Assertions.assertEquals(1, path.getElements().size());
-
- final List<Vector2D> pathVertices = path.getVertexSequence();
- Assertions.assertEquals(2, pathVertices.size());
- EuclideanTestUtils.assertCoordinatesEqual(Vector2D.Unit.PLUS_X, pathVertices.get(0), TEST_EPS);
- EuclideanTestUtils.assertCoordinatesEqual(Vector2D.Unit.PLUS_Y, pathVertices.get(1), TEST_EPS);
-
- Assertions.assertNull(hull.getRegion());
- }
-
- @Test
- void testProperties_threePoints() {
- // arrange
- final List<Vector2D> vertices = Arrays.asList(Vector2D.ZERO, Vector2D.Unit.PLUS_X, Vector2D.Unit.PLUS_Y);
-
- // act
- final ConvexHull2D hull = new ConvexHull2D(vertices, TEST_PRECISION);
-
- // assert
- Assertions.assertEquals(vertices, hull.getVertices());
-
- final LinePath path = hull.getPath();
- Assertions.assertEquals(3, path.getElements().size());
-
- final List<Vector2D> pathVertices = path.getVertexSequence();
- Assertions.assertEquals(4, pathVertices.size());
- EuclideanTestUtils.assertCoordinatesEqual(Vector2D.ZERO, pathVertices.get(0), TEST_EPS);
- EuclideanTestUtils.assertCoordinatesEqual(Vector2D.Unit.PLUS_X, pathVertices.get(1), TEST_EPS);
- EuclideanTestUtils.assertCoordinatesEqual(Vector2D.Unit.PLUS_Y, pathVertices.get(2), TEST_EPS);
- EuclideanTestUtils.assertCoordinatesEqual(Vector2D.ZERO, pathVertices.get(3), TEST_EPS);
-
- Assertions.assertEquals(0.5, hull.getRegion().getSize(), TEST_EPS);
- }
-
- @Test
- void testProperties_fourPoints() {
- // arrange
- final List<Vector2D> vertices = Arrays.asList(Vector2D.ZERO, Vector2D.Unit.PLUS_X,
- Vector2D.of(1, 1), Vector2D.Unit.PLUS_Y);
-
- // act
- final ConvexHull2D hull = new ConvexHull2D(vertices, TEST_PRECISION);
-
- // assert
- Assertions.assertEquals(vertices, hull.getVertices());
-
- final LinePath path = hull.getPath();
- Assertions.assertEquals(4, path.getElements().size());
-
- final List<Vector2D> pathVertices = path.getVertexSequence();
- Assertions.assertEquals(5, pathVertices.size());
- EuclideanTestUtils.assertCoordinatesEqual(Vector2D.ZERO, pathVertices.get(0), TEST_EPS);
- EuclideanTestUtils.assertCoordinatesEqual(Vector2D.Unit.PLUS_X, pathVertices.get(1), TEST_EPS);
- EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(1, 1), pathVertices.get(2), TEST_EPS);
- EuclideanTestUtils.assertCoordinatesEqual(Vector2D.Unit.PLUS_Y, pathVertices.get(3), TEST_EPS);
- EuclideanTestUtils.assertCoordinatesEqual(Vector2D.ZERO, pathVertices.get(4), TEST_EPS);
-
- Assertions.assertEquals(1.0, hull.getRegion().getSize(), TEST_EPS);
- }
-
- @Test
- void testVertexListCannotBeModified() {
- // arrange
- final List<Vector2D> vertices = new ArrayList<>();
- vertices.add(Vector2D.Unit.PLUS_X);
-
- final ConvexHull2D hull = new ConvexHull2D(vertices, TEST_PRECISION);
-
- // act
- final List<Vector2D> hullVertices = hull.getVertices();
-
- // assert
- Assertions.assertNotSame(vertices, hullVertices);
-
- Assertions.assertThrows(UnsupportedOperationException.class, () -> hullVertices.add(Vector2D.Unit.PLUS_Y));
- }
-
- @Test
- void testToString() {
- // arrange
- final List<Vector2D> vertices = Collections.singletonList(Vector2D.Unit.PLUS_X);
- final ConvexHull2D hull = new ConvexHull2D(vertices, TEST_PRECISION);
-
- // act
- final String str = hull.toString();
-
- // assert
- GeometryTestUtils.assertContains("ConvexHull2D[vertices= [(1", str);
- }
-}
diff --git a/commons-geometry-hull/src/test/java/org/apache/commons/geometry/hull/euclidean/twod/ConvexHullGenerator2DAbstractTest.java b/commons-geometry-hull/src/test/java/org/apache/commons/geometry/hull/euclidean/twod/ConvexHullGenerator2DAbstractTest.java
deleted file mode 100644
index e30d5cc..0000000
--- a/commons-geometry-hull/src/test/java/org/apache/commons/geometry/hull/euclidean/twod/ConvexHullGenerator2DAbstractTest.java
+++ /dev/null
@@ -1,506 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements. See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-package org.apache.commons.geometry.hull.euclidean.twod;
-
-import java.util.ArrayList;
-import java.util.Collection;
-import java.util.Collections;
-import java.util.List;
-
-import org.apache.commons.geometry.core.Region;
-import org.apache.commons.geometry.core.RegionLocation;
-import org.apache.commons.geometry.euclidean.twod.ConvexArea;
-import org.apache.commons.geometry.euclidean.twod.Vector2D;
-import org.apache.commons.numbers.core.Precision;
-import org.apache.commons.numbers.core.Sum;
-import org.apache.commons.rng.UniformRandomProvider;
-import org.apache.commons.rng.simple.RandomSource;
-import org.junit.jupiter.api.Assertions;
-import org.junit.jupiter.api.BeforeEach;
-import org.junit.jupiter.api.Test;
-
-/**
- * Abstract base test class for 2D convex hull generators.
- */
-public abstract class ConvexHullGenerator2DAbstractTest {
-
- protected static final double TEST_EPS = 1e-10;
-
- protected static final Precision.DoubleEquivalence TEST_PRECISION =
- Precision.doubleEquivalenceOfEpsilon(TEST_EPS);
-
- protected ConvexHullGenerator2D generator;
-
- protected UniformRandomProvider random;
-
- protected abstract ConvexHullGenerator2D createConvexHullGenerator(boolean includeCollinearPoints);
-
- protected Collection<Vector2D> reducePoints(final Collection<Vector2D> points) {
- // do nothing by default, may be overridden by other tests
- return points;
- }
-
- @BeforeEach
- public void setUp() {
- // by default, do not include collinear points
- generator = createConvexHullGenerator(false);
- random = RandomSource.create(RandomSource.MT, 10);
- }
-
- // ------------------------------------------------------------------------------
-
- @Test
- void testEmpty() {
- // act
- final ConvexHull2D hull = generator.generate(Collections.emptyList());
-
- // assert
- Assertions.assertEquals(0, hull.getVertices().size());
- Assertions.assertEquals(0, hull.getPath().getElements().size());
- Assertions.assertNull(hull.getRegion());
- }
-
- @Test
- void testOnePoint() {
- // arrange
- final List<Vector2D> points = createRandomPoints(1);
-
- // act
- final ConvexHull2D hull = generator.generate(points);
-
- // assert
- Assertions.assertEquals(1, hull.getVertices().size());
- Assertions.assertEquals(0, hull.getPath().getElements().size());
- Assertions.assertNull(hull.getRegion());
- }
-
- @Test
- void testTwoPoints() {
- // arrange
- final List<Vector2D> points = createRandomPoints(2);
-
- // act
- final ConvexHull2D hull = generator.generate(points);
-
- // assert
- Assertions.assertEquals(2, hull.getVertices().size());
- Assertions.assertEquals(1, hull.getPath().getElements().size());
- Assertions.assertNull(hull.getRegion());
- }
-
- @Test
- void testAllIdentical() {
- // arrange
- final Collection<Vector2D> points = new ArrayList<>();
- points.add(Vector2D.of(1, 1));
- points.add(Vector2D.of(1, 1));
- points.add(Vector2D.of(1, 1));
- points.add(Vector2D.of(1, 1));
-
- // act
- final ConvexHull2D hull = generator.generate(points);
-
- // assert
- Assertions.assertEquals(1, hull.getVertices().size());
- Assertions.assertEquals(0, hull.getPath().getElements().size());
- Assertions.assertNull(hull.getRegion());
- }
-
- @Test
- void testConvexHull() {
- // execute 100 random variations
- for (int i = 0; i < 100; i++) {
- // randomize the size from 4 to 100
- final int size = (int) Math.floor(random.nextDouble() * 96.0 + 4.0);
-
- final List<Vector2D> points = createRandomPoints(size);
-
- // act
- final ConvexHull2D hull = generator.generate(reducePoints(points));
-
- // assert
- checkConvexHull(points, hull);
- }
- }
-
- @Test
- void testCollinearPoints() {
- // arrange
- final Collection<Vector2D> points = new ArrayList<>();
- points.add(Vector2D.of(1, 1));
- points.add(Vector2D.of(2, 2));
- points.add(Vector2D.of(2, 4));
- points.add(Vector2D.of(4, 1));
- points.add(Vector2D.of(10, 1));
-
- // act
- final ConvexHull2D hull = generator.generate(points);
-
- // assert
- checkConvexHull(points, hull);
- }
-
- @Test
- void testCollinearPointsReverse() {
- // arrange
- final Collection<Vector2D> points = new ArrayList<>();
- points.add(Vector2D.of(1, 1));
- points.add(Vector2D.of(2, 2));
- points.add(Vector2D.of(2, 4));
- points.add(Vector2D.of(10, 1));
- points.add(Vector2D.of(4, 1));
-
- // act
- final ConvexHull2D hull = generator.generate(points);
-
- // assert
- checkConvexHull(points, hull);
- }
-
- @Test
- void testCollinearPointsIncluded() {
- // arrange
- final Collection<Vector2D> points = new ArrayList<>();
- points.add(Vector2D.of(1, 1));
- points.add(Vector2D.of(2, 2));
- points.add(Vector2D.of(2, 4));
- points.add(Vector2D.of(4, 1));
- points.add(Vector2D.of(10, 1));
-
- // act
- final ConvexHull2D hull = createConvexHullGenerator(true).generate(points);
-
- // assert
- checkConvexHull(points, hull, true);
- }
-
- @Test
- void testCollinearPointsIncludedReverse() {
- // arrange
- final Collection<Vector2D> points = new ArrayList<>();
- points.add(Vector2D.of(1, 1));
- points.add(Vector2D.of(2, 2));
- points.add(Vector2D.of(2, 4));
- points.add(Vector2D.of(10, 1));
- points.add(Vector2D.of(4, 1));
-
- // act
- final ConvexHull2D hull = createConvexHullGenerator(true).generate(points);
-
- // assert
- checkConvexHull(points, hull, true);
- }
-
- @Test
- void testIdenticalPoints() {
- // arrange
- final Collection<Vector2D> points = new ArrayList<>();
- points.add(Vector2D.of(1, 1));
- points.add(Vector2D.of(2, 2));
- points.add(Vector2D.of(2, 4));
- points.add(Vector2D.of(4, 1));
- points.add(Vector2D.of(1, 1));
-
- // act
- final ConvexHull2D hull = generator.generate(points);
-
- // assert
- checkConvexHull(points, hull);
- }
-
- @Test
- void testIdenticalPoints2() {
- // arrange
- final Collection<Vector2D> points = new ArrayList<>();
- points.add(Vector2D.of(1, 1));
- points.add(Vector2D.of(2, 2));
- points.add(Vector2D.of(2, 4));
- points.add(Vector2D.of(4, 1));
- points.add(Vector2D.of(1, 1));
-
- // act
- final ConvexHull2D hull = createConvexHullGenerator(true).generate(points);
-
- // assert
- checkConvexHull(points, hull, true);
- }
-
- @Test
- void testClosePoints() {
- // arrange
- final Collection<Vector2D> points = new ArrayList<>();
- points.add(Vector2D.of(1, 1));
- points.add(Vector2D.of(2, 2));
- points.add(Vector2D.of(2, 4));
- points.add(Vector2D.of(4, 1));
- points.add(Vector2D.of(1.00001, 1));
-
- // act
- final ConvexHull2D hull = generator.generate(points);
-
- // assert
- checkConvexHull(points, hull);
- }
-
- @Test
- void testCollinearPointOnExistingBoundary() {
- // --- arrange
- // MATH-1135: check that collinear points on the hull are handled correctly
- // when only a minimal hull shall be constructed
- final Collection<Vector2D> points = new ArrayList<>();
- points.add(Vector2D.of(7.3152, 34.7472));
- points.add(Vector2D.of(6.400799999999997, 34.747199999999985));
- points.add(Vector2D.of(5.486399999999997, 34.7472));
- points.add(Vector2D.of(4.876799999999999, 34.7472));
- points.add(Vector2D.of(4.876799999999999, 34.1376));
- points.add(Vector2D.of(4.876799999999999, 30.48));
- points.add(Vector2D.of(6.0959999999999965, 30.48));
- points.add(Vector2D.of(6.0959999999999965, 34.1376));
- points.add(Vector2D.of(7.315199999999996, 34.1376));
- points.add(Vector2D.of(7.3152, 30.48));
-
- // --- act
- final ConvexHull2D hull = createConvexHullGenerator(false).generate(points);
-
- // --- assert
- checkConvexHull(points, hull);
- }
-
- @Test
- void testCollinearPointsInAnyOrder_threeCollinearPoints() {
- // --- arrange
- // MATH-1148: collinear points on the hull might be in any order
- // make sure that they are processed in the proper order
- // for each algorithm.
-
- final List<Vector2D> points = new ArrayList<>();
- points.add(Vector2D.of(16.078200000000184, -36.52519999989808));
- points.add(Vector2D.of(19.164300000000186, -36.52519999989808));
- points.add(Vector2D.of(19.1643, -25.28136477910407));
- points.add(Vector2D.of(19.1643, -17.678400000004157));
-
- // --- act/assert
- ConvexHull2D hull = createConvexHullGenerator(false).generate(points);
- checkConvexHull(points, hull);
-
- hull = createConvexHullGenerator(true).generate(points);
- checkConvexHull(points, hull, true);
- }
-
- @Test
- void testCollinearPointsInAnyOrder_multipleCollinearPoints() {
- // --- arrange
- // MATH-1148: collinear points on the hull might be in any order
- // make sure that they are processed in the proper order
- // for each algorithm.
-
- final List<Vector2D> points = new ArrayList<>();
- points.add(Vector2D.of(0, -29.959696875));
- points.add(Vector2D.of(0, -31.621809375));
- points.add(Vector2D.of(0, -28.435696875));
- points.add(Vector2D.of(0, -33.145809375));
- points.add(Vector2D.of(3.048, -33.145809375));
- points.add(Vector2D.of(3.048, -31.621809375));
- points.add(Vector2D.of(3.048, -29.959696875));
- points.add(Vector2D.of(4.572, -33.145809375));
- points.add(Vector2D.of(4.572, -28.435696875));
-
- // --- act/assert
- ConvexHull2D hull = createConvexHullGenerator(false).generate(points);
- checkConvexHull(points, hull);
-
- hull = createConvexHullGenerator(true).generate(points);
- checkConvexHull(points, hull, true);
- }
-
- @Test
- void testIssue1123() {
- // arrange
- final List<Vector2D> points = new ArrayList<>();
-
- final int[][] data = {
- {-11, -1}, {-11, 0}, {-11, 1},
- {-10, -3}, {-10, -2}, {-10, -1}, {-10, 0}, {-10, 1},
- {-10, 2}, {-10, 3}, {-9, -4}, {-9, -3}, {-9, -2},
- {-9, -1}, {-9, 0}, {-9, 1}, {-9, 2}, {-9, 3},
- {-9, 4}, {-8, -5}, {-8, -4}, {-8, -3}, {-8, -2},
- {-8, -1}, {-8, 0}, {-8, 1}, {-8, 2}, {-8, 3},
- {-8, 4}, {-8, 5}, {-7, -6}, {-7, -5}, {-7, -4},
- {-7, -3}, {-7, -2}, {-7, -1}, {-7, 0}, {-7, 1},
- {-7, 2}, {-7, 3}, {-7, 4}, {-7, 5}, {-7, 6},
- {-6, -7}, {-6, -6}, {-6, -5}, {-6, -4}, {-6, -3},
- {-6, -2}, {-6, -1}, {-6, 0}, {-6, 1}, {-6, 2},
- {-6, 3}, {-6, 4}, {-6, 5}, {-6, 6}, {-6, 7},
- {-5, -7}, {-5, -6}, {-5, -5}, {-5, -4}, {-5, -3},
- {-5, -2}, {-5, 4}, {-5, 5}, {-5, 6}, {-5, 7},
- {-4, -7}, {-4, -6}, {-4, -5}, {-4, -4}, {-4, -3},
- {-4, -2}, {-4, 4}, {-4, 5}, {-4, 6}, {-4, 7},
- {-3, -8}, {-3, -7}, {-3, -6}, {-3, -5}, {-3, -4},
- {-3, -3}, {-3, -2}, {-3, 4}, {-3, 5}, {-3, 6},
- {-3, 7}, {-3, 8}, {-2, -8}, {-2, -7}, {-2, -6},
- {-2, -5}, {-2, -4}, {-2, -3}, {-2, -2}, {-2, 4},
- {-2, 5}, {-2, 6}, {-2, 7}, {-2, 8}, {-1, -8},
- {-1, -7}, {-1, -6}, {-1, -5}, {-1, -4}, {-1, -3},
- {-1, -2}, {-1, 4}, {-1, 5}, {-1, 6}, {-1, 7},
- {-1, 8}, {0, -8}, {0, -7}, {0, -6}, {0, -5},
- {0, -4}, {0, -3}, {0, -2}, {0, 4}, {0, 5}, {0, 6},
- {0, 7}, {0, 8}, {1, -8}, {1, -7}, {1, -6}, {1, -5},
- {1, -4}, {1, -3}, {1, -2}, {1, -1}, {1, 0}, {1, 1},
- {1, 2}, {1, 3}, {1, 4}, {1, 5}, {1, 6}, {1, 7},
- {1, 8}, {2, -8}, {2, -7}, {2, -6}, {2, -5},
- {2, -4}, {2, -3}, {2, -2}, {2, -1}, {2, 0}, {2, 1},
- {2, 2}, {2, 3}, {2, 4}, {2, 5}, {2, 6}, {2, 7},
- {2, 8}, {3, -8}, {3, -7}, {3, -6}, {3, -5},
- {3, -4}, {3, -3}, {3, -2}, {3, -1}, {3, 0}, {3, 1},
- {3, 2}, {3, 3}, {3, 4}, {3, 5}, {3, 6}, {3, 7},
- {3, 8}, {4, -7}, {4, -6}, {4, -5}, {4, -4},
- {4, -3}, {4, -2}, {4, -1}, {4, 0}, {4, 1}, {4, 2},
- {4, 3}, {4, 4}, {4, 5}, {4, 6}, {4, 7}, {5, -7},
- {5, -6}, {5, -5}, {5, -4}, {5, -3}, {5, -2},
- {5, -1}, {5, 0}, {5, 1}, {5, 2}, {5, 3}, {5, 4},
- {5, 5}, {5, 6}, {5, 7}, {6, -7}, {6, -6}, {6, -5},
- {6, -4}, {6, -3}, {6, -2}, {6, -1}, {6, 0}, {6, 1},
- {6, 2}, {6, 3}, {6, 4}, {6, 5}, {6, 6}, {6, 7},
- {7, -6}, {7, -5}, {7, -4}, {7, -3}, {7, -2},
- {7, -1}, {7, 0}, {7, 1}, {7, 2}, {7, 3}, {7, 4},
- {7, 5}, {7, 6}, {8, -5}, {8, -4}, {8, -3}, {8, -2},
- {8, -1}, {8, 0}, {8, 1}, {8, 2}, {8, 3}, {8, 4},
- {8, 5}, {9, -4}, {9, -3}, {9, -2}, {9, -1}, {9, 0},
- {9, 1}, {9, 2}, {9, 3}, {9, 4}, {10, -3}, {10, -2},
- {10, -1}, {10, 0}, {10, 1}, {10, 2}, {10, 3},
- {11, -1}, {11, 0}, {11, 1}
- };
-
- for (final int[] line : data) {
- points.add(Vector2D.of(line[0], line[1]));
- }
-
- final Vector2D[] referenceHull = {
- Vector2D.of(-11.0, -1.0),
- Vector2D.of(-10.0, -3.0),
- Vector2D.of(-6.0, -7.0),
- Vector2D.of(-3.0, -8.0),
- Vector2D.of(3.0, -8.0),
- Vector2D.of(6.0, -7.0),
- Vector2D.of(10.0, -3.0),
- Vector2D.of(11.0, -1.0),
- Vector2D.of(11.0, 1.0),
- Vector2D.of(10.0, 3.0),
- Vector2D.of(6.0, 7.0),
- Vector2D.of(3.0, 8.0),
- Vector2D.of(-3.0, 8.0),
- Vector2D.of(-6.0, 7.0),
- Vector2D.of(-10.0, 3.0),
- Vector2D.of(-11.0, 1.0),
- };
-
- // act
- final ConvexHull2D convHull = generator.generate(points);
- final Region<Vector2D> hullRegion = convHull.getRegion();
-
- // assert
- Assertions.assertEquals(274.0, hullRegion.getSize(), 1.0e-12);
- double perimeter = 0;
- for (int i = 0; i < referenceHull.length; ++i) {
- perimeter += referenceHull[i].distance(
- referenceHull[(i + 1) % referenceHull.length]);
- }
- Assertions.assertEquals(perimeter, hullRegion.getBoundarySize(), 1.0e-12);
-
- for (final Vector2D vector2D : referenceHull) {
- Assertions.assertEquals(RegionLocation.BOUNDARY, hullRegion.classify(vector2D));
- }
-
- }
-
- // ------------------------------------------------------------------------------
-
- protected final List<Vector2D> createRandomPoints(final int size) {
- // create the cloud container
- final List<Vector2D> points = new ArrayList<>(size);
- // fill the cloud with a random distribution of points
- for (int i = 0; i < size; i++) {
- points.add(Vector2D.of(random.nextDouble() * 2.0 - 1.0, random.nextDouble() * 2.0 - 1.0));
- }
- return points;
- }
-
- protected final void checkConvexHull(final Collection<Vector2D> points, final ConvexHull2D hull) {
- checkConvexHull(points, hull, false);
- }
-
- protected final void checkConvexHull(final Collection<Vector2D> points, final ConvexHull2D hull,
- final boolean includesCollinearPoints) {
- Assertions.assertNotNull(hull);
- Assertions.assertTrue(isConvex(hull, includesCollinearPoints));
- checkPointsInsideHullRegion(points, hull, includesCollinearPoints);
- }
-
- // verify that the constructed hull is really convex
- protected final boolean isConvex(final ConvexHull2D hull, final boolean includesCollinearPoints) {
-
- final List<Vector2D> points = hull.getVertices();
- int sign = 0;
- final int size = points.size();
-
- for (int i = 0; i < size; i++) {
- final Vector2D p1 = points.get(i == 0 ? size - 1 : i - 1);
- final Vector2D p2 = points.get(i);
- final Vector2D p3 = points.get(i == size - 1 ? 0 : i + 1);
-
- final Vector2D d1 = p2.subtract(p1);
- final Vector2D d2 = p3.subtract(p2);
-
- Assertions.assertTrue(d1.norm() > 1e-10);
- Assertions.assertTrue(d2.norm() > 1e-10);
-
- final double cross = Sum.create()
- .addProduct(d1.getX(), d2.getY())
- .addProduct(-d1.getY(), d2.getX()).getAsDouble();
- final int cmp = Precision.compareTo(cross, 0.0, TEST_EPS);
-
- if (sign != 0 && cmp != sign) {
- if (!includesCollinearPoints || cmp != 0) {
- // in case of collinear points the cross product will be zero
- return false;
- }
- }
-
- sign = cmp;
- }
-
- return true;
- }
-
- // verify that all points are inside the convex hull region
- protected final void checkPointsInsideHullRegion(final Collection<? extends Vector2D> points,
- final ConvexHull2D hull,
- final boolean includesCollinearPoints) {
-
- final Collection<Vector2D> hullVertices = hull.getVertices();
- final ConvexArea region = hull.getRegion();
-
- for (final Vector2D p : points) {
- final RegionLocation location = region.classify(p);
- Assertions.assertNotEquals(RegionLocation.OUTSIDE, location);
-
- if (location == RegionLocation.BOUNDARY && includesCollinearPoints) {
- Assertions.assertTrue(hullVertices.contains(p));
- }
- }
- }
-}
diff --git a/commons-geometry-hull/src/test/java/org/apache/commons/geometry/hull/euclidean/twod/MonotoneChainTest.java b/commons-geometry-hull/src/test/java/org/apache/commons/geometry/hull/euclidean/twod/MonotoneChainTest.java
deleted file mode 100644
index 004a57f..0000000
--- a/commons-geometry-hull/src/test/java/org/apache/commons/geometry/hull/euclidean/twod/MonotoneChainTest.java
+++ /dev/null
@@ -1,57 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements. See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-package org.apache.commons.geometry.hull.euclidean.twod;
-
-import java.util.ArrayList;
-import java.util.Collection;
-
-import org.apache.commons.geometry.euclidean.twod.Vector2D;
-import org.apache.commons.numbers.core.Precision;
-import org.junit.jupiter.api.Assertions;
-import org.junit.jupiter.api.Test;
-
-/**
- * Test class for MonotoneChain.
- */
-class MonotoneChainTest extends ConvexHullGenerator2DAbstractTest {
-
- @Override
- protected ConvexHullGenerator2D createConvexHullGenerator(final boolean includeCollinearPoints) {
- return new MonotoneChain(includeCollinearPoints, TEST_PRECISION);
- }
-
- // ------------------------------------------------------------------------------
-
- @Test
- void testConvergenceException() {
- // arrange
- final Collection<Vector2D> points = new ArrayList<>();
-
- points.add(Vector2D.of(1, 1));
- points.add(Vector2D.of(1, 5));
- points.add(Vector2D.of(0, 7));
- points.add(Vector2D.of(1, 10));
- points.add(Vector2D.of(1, 20));
- points.add(Vector2D.of(20, 20));
- points.add(Vector2D.of(20, 40));
- points.add(Vector2D.of(40, 1));
-
- // act/assert
- Assertions.assertThrows(IllegalStateException.class,
- () -> new MonotoneChain(true, Precision.doubleEquivalenceOfEpsilon(1)).generate(points));
- }
-}
diff --git a/commons-geometry-io-core/pom.xml b/commons-geometry-io-core/pom.xml
index e21f30d..c2f3abb 100644
--- a/commons-geometry-io-core/pom.xml
+++ b/commons-geometry-io-core/pom.xml
@@ -23,7 +23,7 @@
<parent>
<groupId>org.apache.commons</groupId>
<artifactId>commons-geometry-parent</artifactId>
- <version>1.0-SNAPSHOT</version>
+ <version>1.0</version>
</parent>
<artifactId>commons-geometry-io-core</artifactId>
diff --git a/commons-geometry-hull/src/site/resources/profile.jacoco b/commons-geometry-io-core/src/site/resources/profile.jacoco
similarity index 100%
rename from commons-geometry-hull/src/site/resources/profile.jacoco
rename to commons-geometry-io-core/src/site/resources/profile.jacoco
diff --git a/commons-geometry-hull/src/site/site.xml b/commons-geometry-io-core/src/site/site.xml
similarity index 90%
rename from commons-geometry-hull/src/site/site.xml
rename to commons-geometry-io-core/src/site/site.xml
index 54b485f..3974ae8 100644
--- a/commons-geometry-hull/src/site/site.xml
+++ b/commons-geometry-io-core/src/site/site.xml
@@ -28,10 +28,11 @@
<item name="Overview" href="/index.html"/>
<item name="Latest API docs (development)"
href="apidocs/index.html"/>
- <!-- <item name="Javadoc (1.0 release)"
- href="https://commons.apache.org/geometry/commons-geometry-hull/javadocs/api-1.0/index.html"/> -->
+ <item name="Javadoc (1.0 release)"
+ href="https://commons.apache.org/geometry/commons-geometry-io-core/javadocs/api-1.0/index.html"/>
</menu>
+
<head>
<![CDATA[<script type="text/javascript" src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>]]>
diff --git a/commons-geometry-io-euclidean/pom.xml b/commons-geometry-io-euclidean/pom.xml
index f915f2f..d4db59b 100644
--- a/commons-geometry-io-euclidean/pom.xml
+++ b/commons-geometry-io-euclidean/pom.xml
@@ -23,7 +23,7 @@
<parent>
<groupId>org.apache.commons</groupId>
<artifactId>commons-geometry-parent</artifactId>
- <version>1.0-SNAPSHOT</version>
+ <version>1.0</version>
</parent>
<artifactId>commons-geometry-io-euclidean</artifactId>
diff --git a/commons-geometry-enclosing/src/site/resources/profile.jacoco b/commons-geometry-io-euclidean/src/site/resources/profile.jacoco
similarity index 100%
rename from commons-geometry-enclosing/src/site/resources/profile.jacoco
rename to commons-geometry-io-euclidean/src/site/resources/profile.jacoco
diff --git a/commons-geometry-hull/src/site/site.xml b/commons-geometry-io-euclidean/src/site/site.xml
similarity index 90%
copy from commons-geometry-hull/src/site/site.xml
copy to commons-geometry-io-euclidean/src/site/site.xml
index 54b485f..3758451 100644
--- a/commons-geometry-hull/src/site/site.xml
+++ b/commons-geometry-io-euclidean/src/site/site.xml
@@ -28,10 +28,11 @@
<item name="Overview" href="/index.html"/>
<item name="Latest API docs (development)"
href="apidocs/index.html"/>
- <!-- <item name="Javadoc (1.0 release)"
- href="https://commons.apache.org/geometry/commons-geometry-hull/javadocs/api-1.0/index.html"/> -->
+ <item name="Javadoc (1.0 release)"
+ href="https://commons.apache.org/geometry/commons-geometry-io-euclidean/javadocs/api-1.0/index.html"/>
</menu>
+
<head>
<![CDATA[<script type="text/javascript" src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>]]>
diff --git a/commons-geometry-spherical/pom.xml b/commons-geometry-spherical/pom.xml
index a299ada..a61fa51 100644
--- a/commons-geometry-spherical/pom.xml
+++ b/commons-geometry-spherical/pom.xml
@@ -23,7 +23,7 @@
<parent>
<groupId>org.apache.commons</groupId>
<artifactId>commons-geometry-parent</artifactId>
- <version>1.0-SNAPSHOT</version>
+ <version>1.0</version>
</parent>
<artifactId>commons-geometry-spherical</artifactId>
@@ -52,11 +52,6 @@
<artifactId>commons-geometry-euclidean</artifactId>
<version>${project.version}</version>
</dependency>
- <dependency>
- <groupId>org.apache.commons</groupId>
- <artifactId>commons-geometry-enclosing</artifactId>
- <version>${project.version}</version>
- </dependency>
<dependency>
<groupId>org.apache.commons</groupId>
diff --git a/commons-geometry-spherical/src/site/site.xml b/commons-geometry-spherical/src/site/site.xml
index 523c589..9f8b54f 100644
--- a/commons-geometry-spherical/src/site/site.xml
+++ b/commons-geometry-spherical/src/site/site.xml
@@ -28,8 +28,8 @@
<item name="Overview" href="/index.html"/>
<item name="Latest API docs (development)"
href="apidocs/index.html"/>
- <!-- <item name="Javadoc (1.0 release)"
- href="https://commons.apache.org/geometry/commons-geometry-spherical/javadocs/api-1.0/index.html"/> -->
+ <item name="Javadoc (1.0 release)"
+ href="https://commons.apache.org/geometry/commons-geometry-spherical/javadocs/api-1.0/index.html"/>
</menu>
<head>
diff --git a/dist-archive/pom.xml b/dist-archive/pom.xml
index 0fd1da1..bcf46f3 100644
--- a/dist-archive/pom.xml
+++ b/dist-archive/pom.xml
@@ -23,7 +23,7 @@
<parent>
<groupId>org.apache.commons</groupId>
<artifactId>commons-geometry-parent</artifactId>
- <version>1.0-SNAPSHOT</version>
+ <version>1.0</version>
</parent>
<artifactId>commons-geometry</artifactId>
@@ -117,44 +117,6 @@
<classifier>javadoc</classifier>
</dependency>
- <!-- Module: Enclosing -->
- <dependency>
- <groupId>org.apache.commons</groupId>
- <artifactId>commons-geometry-enclosing</artifactId>
- <version>${project.version}</version>
- </dependency>
- <dependency>
- <groupId>org.apache.commons</groupId>
- <artifactId>commons-geometry-enclosing</artifactId>
- <version>${project.version}</version>
- <classifier>sources</classifier>
- </dependency>
- <dependency>
- <groupId>org.apache.commons</groupId>
- <artifactId>commons-geometry-enclosing</artifactId>
- <version>${project.version}</version>
- <classifier>javadoc</classifier>
- </dependency>
-
- <!-- Module: Hull -->
- <dependency>
- <groupId>org.apache.commons</groupId>
- <artifactId>commons-geometry-hull</artifactId>
- <version>${project.version}</version>
- </dependency>
- <dependency>
- <groupId>org.apache.commons</groupId>
- <artifactId>commons-geometry-hull</artifactId>
- <version>${project.version}</version>
- <classifier>sources</classifier>
- </dependency>
- <dependency>
- <groupId>org.apache.commons</groupId>
- <artifactId>commons-geometry-hull</artifactId>
- <version>${project.version}</version>
- <classifier>javadoc</classifier>
- </dependency>
-
<!-- Module: IO Core -->
<dependency>
<groupId>org.apache.commons</groupId>
diff --git a/pom.xml b/pom.xml
index 340639f..22b30aa 100644
--- a/pom.xml
+++ b/pom.xml
@@ -24,7 +24,7 @@
</parent>
<artifactId>commons-geometry-parent</artifactId>
- <version>1.0-SNAPSHOT</version>
+ <version>1.0</version>
<packaging>pom</packaging>
<name>Apache Commons Geometry</name>
<description>The Apache Commons Geometry project provides geometric types and utilities.</description>
@@ -44,7 +44,7 @@
<!-- do not use snapshot suffix here -->
<commons.release.version>1.0</commons.release.version>
<commons.release.desc>(requires Java 8+)</commons.release.desc>
- <!-- <commons.rc.version>RC1</commons.rc.version> -->
+ <commons.rc.version>RC1</commons.rc.version>
<commons.binary.suffix>-bin</commons.binary.suffix>
<commons.jira.id>GEOMETRY</commons.jira.id>
@@ -105,8 +105,6 @@
<module>commons-geometry-core</module>
<module>commons-geometry-euclidean</module>
<module>commons-geometry-spherical</module>
- <module>commons-geometry-hull</module>
- <module>commons-geometry-enclosing</module>
<module>commons-geometry-io-core</module>
<module>commons-geometry-io-euclidean</module>
</modules>
diff --git a/src/changes/changes.xml b/src/changes/changes.xml
index e1c3805..261a7dc 100644
--- a/src/changes/changes.xml
+++ b/src/changes/changes.xml
@@ -53,7 +53,7 @@
</properties>
<body>
- <release version="1.0" date="TBD" description="
+ <release version="1.0" date="2021-08-15" description="
This is the first major release of Apache Commons Geometry.
Apache Commons Geometry 1.0 contains the following library modules:
diff --git a/src/changes/release-notes.vm b/src/changes/release-notes.vm
new file mode 100644
index 0000000..cc1b18c
--- /dev/null
+++ b/src/changes/release-notes.vm
@@ -0,0 +1,140 @@
+## Licensed to the Apache Software Foundation (ASF) under one
+## or more contributor license agreements. See the NOTICE file
+## distributed with this work for additional information
+## regarding copyright ownership. The ASF licenses this file
+## to you under the Apache License, Version 2.0 (the
+## "License"); you may not use this file except in compliance
+## with the License. You may obtain a copy of the License at
+##
+## http://www.apache.org/licenses/LICENSE-2.0
+##
+## Unless required by applicable law or agreed to in writing,
+## software distributed under the License is distributed on an
+## "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+## KIND, either express or implied. See the License for the
+## specific language governing permissions and limitations
+## under the License.
+
+ ${project.name} ${version} RELEASE NOTES
+
+The ${developmentTeam} is pleased to announce the release of ${finalName}
+
+$introduction.replaceAll("(?<!\015)\012", "
+")
+
+## N.B. the available variables are described here:
+## http://maven.apache.org/plugins/maven-changes-plugin/examples/using-a-custom-announcement-template.html
+##
+## Hack to improve layout: replace all pairs of spaces with a single new-line
+$release.description.replaceAll(" ", "
+")
+
+#if ($release.getActions().size() == 0)
+No changes defined in this version.
+#else
+Changes in this version include:
+
+## indent to be used if there is no issue attribute.
+## should be the same as the indent in the changes.xml file
+## less 2 spaces for the 'o' and trailing space
+#set($indent=' ')
+#if ($release.getActions('add').size() !=0)
+New features:
+#foreach($actionItem in $release.getActions('add'))
+## Use replaceAll to fix up LF-only line ends on Windows.
+#set($action=$actionItem.getAction().replaceAll("\n","
+"))
+#if ($actionItem.getIssue())
+#set($issue=$actionItem.getIssue())
+#else
+#set($issue="")
+#end
+#if ($actionItem.getDueTo())
+#set($dueto=$actionItem.getDueTo())
+#else
+#set($dueto="")
+#end
+o#if($!issue != "") $issue: #else$indent#end ${action} #if($!dueto != "")Thanks to $dueto. #end
+
+#set($issue="")
+#set($dueto="")
+#end
+#end
+
+#if ($release.getActions('fix').size() !=0)
+Fixed Bugs:
+#foreach($actionItem in $release.getActions('fix'))
+## Use replaceAll to fix up LF-only line ends on Windows.
+#set($action=$actionItem.getAction().replaceAll("\n","
+"))
+#if ($actionItem.getIssue())
+#set($issue=$actionItem.getIssue())
+#else
+#set($issue="")
+#end
+#if ($actionItem.getDueTo())
+#set($dueto=$actionItem.getDueTo())
+#else
+#set($dueto="")
+#end
+o#if($!issue != "") $issue: #else$indent#end ${action} #if($!dueto != "")Thanks to $dueto. #end
+
+#set($issue="")
+#set($dueto="")
+#end
+#end
+
+#if ($release.getActions('update').size() !=0)
+Changes:
+#foreach($actionItem in $release.getActions('update'))
+## Use replaceAll to fix up LF-only line ends on Windows.
+#set($action=$actionItem.getAction().replaceAll("\n","
+"))
+#if ($actionItem.getIssue())
+#set($issue=$actionItem.getIssue())
+#else
+#set($issue="")
+#end
+#if ($actionItem.getDueTo())
+#set($dueto=$actionItem.getDueTo())
+#else
+#set($dueto="")
+#end
+o#if($!issue != "") $issue: #else$indent#end ${action} #if($!dueto != "")Thanks to $dueto. #end
+
+#set($issue="")
+#set($dueto="")
+#end
+#end
+
+#if ($release.getActions('remove').size() !=0)
+Removed:
+#foreach($actionItem in $release.getActions('remove'))
+## Use replaceAll to fix up LF-only line ends on Windows.
+#set($action=$actionItem.getAction().replaceAll("\n","
+"))
+#if ($actionItem.getIssue())
+#set($issue=$actionItem.getIssue())
+#else
+#set($issue="")
+#end
+#if ($actionItem.getDueTo())
+#set($dueto=$actionItem.getDueTo())
+#else
+#set($dueto="")
+#end
+o#if($!issue != "") $issue: #else$indent#end ${action} #if($!dueto != "")Thanks to $dueto. #end
+
+#set($issue="")
+#set($dueto="")
+#end
+#end
+## End of main loop
+#end
+
+For complete information on ${project.name}, including instructions on how to submit bug reports,
+patches, or suggestions for improvement, see the ${project.name} website:
+
+${project.url}
+
+
diff --git a/src/main/resources/spotbugs/spotbugs-exclude-filter.xml b/src/main/resources/spotbugs/spotbugs-exclude-filter.xml
index a3d2782..06a8333 100644
--- a/src/main/resources/spotbugs/spotbugs-exclude-filter.xml
+++ b/src/main/resources/spotbugs/spotbugs-exclude-filter.xml
@@ -65,14 +65,10 @@
<Class name="org.apache.commons.geometry.euclidean.twod.path.LinePath"/>
<Class name="org.apache.commons.geometry.euclidean.twod.EmbeddedTreeLineSubset"/>
- <Class name="org.apache.commons.geometry.enclosing.EnclosingBall"/>
-
<Class name="org.apache.commons.geometry.spherical.twod.EmbeddedTreeGreatCircleSubset"/>
<Class name="org.apache.commons.geometry.spherical.twod.RegionBSPTree2S"/>
<Class name="org.apache.commons.geometry.spherical.twod.GreatArcPath"/>
- <Class name="org.apache.commons.geometry.hull.euclidean.twod.ConvexHull2D"/>
-
<Class name="org.apache.commons.geometry.io.core.internal.SimpleTextParser"/>
<Class name="org.apache.commons.geometry.io.core.output.StreamGeometryOutput"/>
diff --git a/src/site/resources/release-notes/RELEASE-NOTES-1.0.txt b/src/site/resources/release-notes/RELEASE-NOTES-1.0.txt
new file mode 100644
index 0000000..ba2e707
--- /dev/null
+++ b/src/site/resources/release-notes/RELEASE-NOTES-1.0.txt
@@ -0,0 +1,78 @@
+
+ Apache Commons Geometry 1.0 RELEASE NOTES
+
+The Apache Commons Geometry team is pleased to announce the release of
+commons-geometry-parent-1.0
+
+The Apache Commons Geometry project provides geometric types and utilities.
+
+This is the first major release of Apache Commons Geometry.
+Apache Commons Geometry 1.0 contains the following library modules:
+ commons-geometry-core (requires Java 8+)
+ commons-geometry-euclidean (requires Java 8+)
+ commons-geometry-spherical (requires Java 8+)
+ commons-geometry-io-core (requires Java 8+)
+ commons-geometry-io-euclidean (requires Java 8+)
+
+Changes in this version include:
+
+New features:
+o GEOMETRY-118: Add coordinate-specific transform methods to AffineTransformMatrixXD classes,
+ e.g. "applyX", "applyY", "applyZ".
+o GEOMETRY-95: Add solid geometry tutorial.
+o GEOMETRY-120: Add SimpleTriangleMeshBuilder.addFace(int[]) method as alternative to
+ addFace(int, int, int).
+o GEOMETRY-117: Add shear methods to AffineTransformMatrix2D. Thanks to Christoph Läubrich.
+o GEOMETRY-119: Add VectorXD.normalizeOrNull() methods so that callers can detect normalization
+ failures without needing to catch an exception.
+o GEOMETRY-115: Add modules for IO functionality: commons-geometry-io-core,
+ commons-geometry-io-euclidean.
+o GEOMETRY-108: Add BoundaryList interface and implementation classes.
+
+Fixed Bugs:
+o GEOMETRY-116: Fix incorrect OSGi headers. Reported by Christoph Läubrich.
+
+Changes:
+o GEOMETRY-138: Do not use checked exceptions in IO modules.
+o GEOMETRY-13: Use Norms.EUCLIDEAN from Commons Numbers to compute 3D Euclidean norm values.
+o GEOMETRY-126: Replace VectorXD.linearCombination methods with VectorXD.Sum classes. Use
+ Sum class from Commons Numbers for computing internal linear combinations.
+o GEOMETRY-124: Replace DoublePrecisionContext with Precision.DoubleEquivalence from
+ Commons Numbers.
+o GEOMETRY-109: Rename the BoundarySourceXX.from() static factory methods to "of" to better
+ match the JDK's Stream.of() method.
+o GEOMETRY-103: Migrate unit tests to JUnit 5. Thanks to Arturo Bernal.
+
+
+For complete information on Apache Commons Geometry, including instructions on how to submit
+ bug reports, patches, or suggestions for improvement, see the Apache Commons Geometry
+ website:
+
+https://commons.apache.org/proper/commons-geometry/
+
+
+=============================================================================
+
+ Apache Commons Geometry 1.0-beta1 RELEASE NOTES
+
+The Apache Commons Geometry team is pleased to announce the release of
+Apache Commons Geometry 1.0-beta1
+
+The Apache Commons Geometry project provides geometric types and utilities.
+
+This is a beta release of Apache Commons Geometry. No guarantees are made regarding the stability
+of the API or compatibility with future releases.
+
+Apache Commons Geometry 1.0-beta1 contains the following library modules:
+ commons-geometry-core (requires Java 8+)
+ commons-geometry-euclidean (requires Java 8+)
+ commons-geometry-spherical (requires Java 8+)
+ commons-geometry-hull (requires Java 8+)
+ commons-geometry-enclosing (requires Java 8+)
+
+No changes defined in this version.
+
+For complete information on Apache Commons Geometry, including instructions on how to submit bug
+reports, patches, or suggestions for improvement, see the Apache Commons Geometry website:
+
+https://commons.apache.org/proper/commons-geometry/
diff --git a/src/site/site.xml b/src/site/site.xml
index 2e99eff..1d8a9b0 100644
--- a/src/site/site.xml
+++ b/src/site/site.xml
@@ -76,8 +76,6 @@
<item name="Core Interfaces" href="/userguide/index.html#interfaces"/>
<item name="Euclidean Space" href="/userguide/index.html#euclidean"/>
<item name="Spherical Space" href="/userguide/index.html#spherical"/>
- <item name="Convex Hull" href="/userguide/index.html#hull"/>
- <item name="Enclosing" href="/userguide/index.html#enclosing"/>
</menu>
<menu name="Tutorials">
<item name="BSP Trees" href="/tutorials/bsp-tree.html" />
diff --git a/src/site/xdoc/download_geometry.xml b/src/site/xdoc/download_geometry.xml
index 5535862..0a6db06 100644
--- a/src/site/xdoc/download_geometry.xml
+++ b/src/site/xdoc/download_geometry.xml
@@ -113,32 +113,32 @@
</p>
</subsection>
</section>
- <section name="Apache Commons Geometry 1.0-beta1 (requires Java 8+)">
+ <section name="Apache Commons Geometry 1.0 (requires Java 8+)">
<subsection name="Binaries">
<table>
<tr>
- <td><a href="[preferred]/commons/geometry/binaries/commons-geometry-1.0-beta1-bin.tar.gz">commons-geometry-1.0-beta1-bin.tar.gz</a></td>
- <td><a href="https://www.apache.org/dist/commons/geometry/binaries/commons-geometry-1.0-beta1-bin.tar.gz.sha512">sha512</a></td>
- <td><a href="https://www.apache.org/dist/commons/geometry/binaries/commons-geometry-1.0-beta1-bin.tar.gz.asc">pgp</a></td>
+ <td><a href="[preferred]/commons/geometry/binaries/commons-geometry-1.0-bin.tar.gz">commons-geometry-1.0-bin.tar.gz</a></td>
+ <td><a href="https://www.apache.org/dist/commons/geometry/binaries/commons-geometry-1.0-bin.tar.gz.sha512">sha512</a></td>
+ <td><a href="https://www.apache.org/dist/commons/geometry/binaries/commons-geometry-1.0-bin.tar.gz.asc">pgp</a></td>
</tr>
<tr>
- <td><a href="[preferred]/commons/geometry/binaries/commons-geometry-1.0-beta1-bin.zip">commons-geometry-1.0-beta1-bin.zip</a></td>
- <td><a href="https://www.apache.org/dist/commons/geometry/binaries/commons-geometry-1.0-beta1-bin.zip.sha512">sha512</a></td>
- <td><a href="https://www.apache.org/dist/commons/geometry/binaries/commons-geometry-1.0-beta1-bin.zip.asc">pgp</a></td>
+ <td><a href="[preferred]/commons/geometry/binaries/commons-geometry-1.0-bin.zip">commons-geometry-1.0-bin.zip</a></td>
+ <td><a href="https://www.apache.org/dist/commons/geometry/binaries/commons-geometry-1.0-bin.zip.sha512">sha512</a></td>
+ <td><a href="https://www.apache.org/dist/commons/geometry/binaries/commons-geometry-1.0-bin.zip.asc">pgp</a></td>
</tr>
</table>
</subsection>
<subsection name="Source">
<table>
<tr>
- <td><a href="[preferred]/commons/geometry/source/commons-geometry-1.0-beta1-src.tar.gz">commons-geometry-1.0-beta1-src.tar.gz</a></td>
- <td><a href="https://www.apache.org/dist/commons/geometry/source/commons-geometry-1.0-beta1-src.tar.gz.sha512">sha512</a></td>
- <td><a href="https://www.apache.org/dist/commons/geometry/source/commons-geometry-1.0-beta1-src.tar.gz.asc">pgp</a></td>
+ <td><a href="[preferred]/commons/geometry/source/commons-geometry-1.0-src.tar.gz">commons-geometry-1.0-src.tar.gz</a></td>
+ <td><a href="https://www.apache.org/dist/commons/geometry/source/commons-geometry-1.0-src.tar.gz.sha512">sha512</a></td>
+ <td><a href="https://www.apache.org/dist/commons/geometry/source/commons-geometry-1.0-src.tar.gz.asc">pgp</a></td>
</tr>
<tr>
- <td><a href="[preferred]/commons/geometry/source/commons-geometry-1.0-beta1-src.zip">commons-geometry-1.0-beta1-src.zip</a></td>
- <td><a href="https://www.apache.org/dist/commons/geometry/source/commons-geometry-1.0-beta1-src.zip.sha512">sha512</a></td>
- <td><a href="https://www.apache.org/dist/commons/geometry/source/commons-geometry-1.0-beta1-src.zip.asc">pgp</a></td>
+ <td><a href="[preferred]/commons/geometry/source/commons-geometry-1.0-src.zip">commons-geometry-1.0-src.zip</a></td>
+ <td><a href="https://www.apache.org/dist/commons/geometry/source/commons-geometry-1.0-src.zip.sha512">sha512</a></td>
+ <td><a href="https://www.apache.org/dist/commons/geometry/source/commons-geometry-1.0-src.zip.asc">pgp</a></td>
</tr>
</table>
</subsection>
diff --git a/src/site/xdoc/release-history.xml b/src/site/xdoc/release-history.xml
index a8388f7..ec9d456 100644
--- a/src/site/xdoc/release-history.xml
+++ b/src/site/xdoc/release-history.xml
@@ -25,6 +25,9 @@
<table>
<tr><th>Version</th><th>Release date (YYYY-MM-DD)</th><th>Required Java Version</th><th>Release notes</th></tr>
<tr>
+ <td>1.0</td><td>2021-08-15</td><td>8+</td><td><a href="release-notes/RELEASE-NOTES-1.0.txt">release notes for 1.0</a></td>
+ </tr>
+ <tr>
<td>1.0-beta1</td><td>2020-07-20</td><td>8+</td><td><a href="release-notes/RELEASE-NOTES-1.0-beta1.txt">release notes for 1.0-beta1</a></td>
</tr>
</table>
diff --git a/src/site/xdoc/userguide/index.xml b/src/site/xdoc/userguide/index.xml
index fdfc9c7..eecd58f 100644
--- a/src/site/xdoc/userguide/index.xml
+++ b/src/site/xdoc/userguide/index.xml
@@ -79,17 +79,6 @@
</li>
</ul>
</li>
- <li>
- <a href="#hull">Convex Hull</a>
- <ul>
- <li>
- <a href="#hull_euclidean_2d">Euclidean 2D</a>
- </li>
- </ul>
- </li>
- <li>
- <a href="#enclosing">Enclosing</a>
- </li>
</ul>
</section>
@@ -126,14 +115,6 @@
<a class="code" href="../commons-geometry-io-euclidean/index.html">commons-geometry-io-euclidean</a> - Provides
classes for IO operations on Euclidean data formats, such STL and OBJ.
</li>
- <li>
- <a class="code" href="../commons-geometry-hull/index.html">commons-geometry-hull</a> - Provides implementations
- of convex hull algorithms.
- </li>
- <li>
- <a class="code" href="../commons-geometry-enclosing/index.html">commons-geometry-enclosing</a> - Provides implementations
- of enclosing ball algorithms.
- </li>
</ul>
</section>
@@ -1113,127 +1094,6 @@
</subsection>
</section>
-
- <section name="Convex Hull" id="hull">
- <p>
- A <a href="http://en.wikipedia.org/wiki/Convex_hull">convex hull</a> of a region or shape in the smallest convex
- set of points that completely contains the shape. For example, if a set of points in Euclidean 2D space are
- represented by nails in a flat piece of wood, then the convex hull of that shape would be the path made by a
- rubber band wrapped around all of the nails. Similarly, in Euclidean 3D space, the convex hull of a shape can be
- visualized as the result of "shrink-wrapping" the shape with a very tight, non-flexible material.
- </p>
- <p>
- A number of convex hull algorithms exist, for various spaces and dimensions, and it is the goal of the
- <span class="code">commons-geometry-hull</span> module to provide implementations of these algorithms.
- </p>
-
- <subsection name="Convex Hull - Euclidean 2D" id="hull_euclidean_2d">
- <h4>Primary Classes</h4>
- <ul>
- <li>
- <a class="code" href="../commons-geometry-hull/apidocs/org/apache/commons/geometry/hull/euclidean/twod/ConvexHullGenerator2D.html">ConvexHullGenerator2D</a> -
- Interface for classes that implement convex hull algorithms in Euclidean 2D space.
- </li>
- <li>
- <a class="code" href="../commons-geometry-hull/apidocs/org/apache/commons/geometry/hull/euclidean/twod/ConvexHull2D.html">ConvexHull2D</a> -
- Class representing output from convex hull operations.
- </li>
- <li>
- <a class="code" href="../commons-geometry-hull/apidocs/org/apache/commons/geometry/hull/euclidean/twod/MonotoneChain.html">MonotoneChain</a> -
- Class implementing
- <a href="http://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain">Andrew's monotone chain algorithm</a>
- for computing convex hulls.
- </li>
- </ul>
-
- <h4>Examples</h4>
-
- <h5>Monotone Chain</h5>
- <source>
-Precision.DoubleEquivalence precision = Precision.doubleEquivalenceOfEpsilon(1e-10);
-
-// create a list of input points for the algorithm
-List<Vector2D> pts = Arrays.asList(
- Vector2D.ZERO,
- Vector2D.of(0.5, 0.5),
- Vector2D.of(0, 0.5),
- Vector2D.of(0, 1),
- Vector2D.of(0.25, 0.1),
- Vector2D.of(1, 0),
- Vector2D.of(1, 1),
- Vector2D.of(0.75, 0.9)
- );
-
-// create an instance of the monotone chain convex hull generator
-MonotoneChain mc = new MonotoneChain(precision);
-
-// compute the convex hull
-ConvexHull2D hull = mc.generate(pts);
-
-// list the vertices from the input that were used in the hull
-List<Vector2D> vertices = hull.getVertices(); // [(0.0, 0.0), (1.0, 0.0), (1.0, 1.0), (0.0, 1.0)]
-
-// get the hull as a region
-ConvexArea region = hull.getRegion();
-boolean containsAll = pts.stream().allMatch(region::contains); // true - region contains all input points
- </source>
- </subsection>
- </section>
-
- <section name="Enclosing" id="enclosing">
- <p>
- The <a href="https://en.wikipedia.org/wiki/Bounding_sphere">smallest enclosing ball problem</a> is the
- mathematical problem of locating the n-sphere with the smallest radius that encloses a given set of points.
- This module contains implementations of algorithms for solving this problem.
- </p>
-
- <h4>Primary Classes</h4>
- <ul>
- <li>
- <a class="code" href="../commons-geometry-enclosing/apidocs/org/apache/commons/geometry/enclosing/Encloser.html">Encloser</a> -
- Interface for classes that solve the smallest enclosing ball problem.
- </li>
- <li>
- <a class="code" href="../commons-geometry-enclosing/apidocs/org/apache/commons/geometry/enclosing/EnclosingBall.html">EnclosingBall</a> -
- Class containing the result of smallest enclosing ball computation.
- </li>
- <li>
- <a class="code" href="../commons-geometry-enclosing/apidocs/org/apache/commons/geometry/enclosing/WelzlEncloser.html">WelzlEncloser</a> -
- Class implementing a space-independent version of
- <a href="http://www.inf.ethz.ch/personal/emo/PublFiles/SmallEnclDisk_LNCS555_91.pdf">Emo Welzl's algorithm</a>
- for computing the smallest enclosing ball of a set of points. Specialized classes exist for Euclidean 2D space
- (<a class="code" href="../commons-geometry-enclosing/apidocs/org/apache/commons/geometry/enclosing/euclidean/twod/WelzlEncloser2D.html">WelzlEncloser2D</a>)
- and Euclidean 3D space
- (<a class="code" href="../commons-geometry-enclosing/apidocs/org/apache/commons/geometry/enclosing/euclidean/threed/WelzlEncloser3D.html">WelzlEncloser3D</a>).
- </li>
- </ul>
-
- <h4>Examples</h4>
-
- <h5>WelzlEncloser3D</h5>
- <source>
-Precision.DoubleEquivalence precision = Precision.doubleEquivalenceOfEpsilon(1e-10);
-
-List<Vector3D> points = Arrays.asList(
- Vector3D.of(0, 0, 1),
- Vector3D.of(0.75, 0, 1),
- Vector3D.of(2, 0, 1),
- Vector3D.of(1, 0, 2)
- );
-
-// compute the enclosing ball
-WelzlEncloser3D encloser = new WelzlEncloser3D(precision);
-
-EnclosingBall<Vector3D> sphere = encloser.enclose(points);
-
-// check the generated ball
-Vector3D center = sphere.getCenter(); // (1, 0, 1)
-double radius = sphere.getRadius(); // 1.0
-boolean containsCenter = sphere.contains(center); // true
-boolean containsOrigin = sphere.contains(Vector3D.ZERO); // false
- </source>
- </section>
-
</body>
</document>
