You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by ma...@apache.org on 2021/08/08 20:38:47 UTC
[commons-geometry] branch 1.0-release created (now 8915213)
This is an automated email from the ASF dual-hosted git repository.
mattjuntunen pushed a change to branch 1.0-release
in repository https://gitbox.apache.org/repos/asf/commons-geometry.git.
at 8915213 remove modules not part of release
This branch includes the following new commits:
new 8915213 remove modules not part of release
The 1 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "add" were already present in the repository and have only
been added to this reference.
[commons-geometry] 01/01: remove modules not part of release
Posted by ma...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
mattjuntunen pushed a commit to branch 1.0-release
in repository https://gitbox.apache.org/repos/asf/commons-geometry.git
commit 891521390166e5154fca9df3498f60fdb6c7deed
Author: Matt Juntunen <ma...@apache.org>
AuthorDate: Sun Aug 8 16:38:26 2021 -0400
remove modules not part of release
---
commons-geometry-enclosing/CONTRIBUTING.md | 115 -----
commons-geometry-enclosing/LICENSE.txt | 201 --------
commons-geometry-enclosing/NOTICE.txt | 6 -
commons-geometry-enclosing/README.md | 105 -----
commons-geometry-enclosing/pom.xml | 102 -----
.../commons/geometry/enclosing/Encloser.java | 34 --
.../commons/geometry/enclosing/EnclosingBall.java | 118 -----
.../geometry/enclosing/SupportBallGenerator.java | 39 --
.../commons/geometry/enclosing/WelzlEncloser.java | 170 -------
.../euclidean/threed/SphereGenerator.java | 157 -------
.../euclidean/threed/WelzlEncloser3D.java | 35 --
.../enclosing/euclidean/threed/package-info.java | 24 -
.../enclosing/euclidean/twod/DiskGenerator.java | 105 -----
.../enclosing/euclidean/twod/WelzlEncloser2D.java | 35 --
.../enclosing/euclidean/twod/package-info.java | 24 -
.../commons/geometry/enclosing/package-info.java | 24 -
.../src/site/resources/profile.jacoco | 17 -
commons-geometry-enclosing/src/site/site.xml | 41 --
.../enclosing/DocumentationExamplesTest.java | 64 ---
.../geometry/enclosing/EnclosingBallTest.java | 153 -------
.../euclidean/threed/SphereGeneratorTest.java | 238 ----------
.../euclidean/threed/WelzlEncloser3DTest.java | 185 --------
.../euclidean/twod/DiskGeneratorTest.java | 155 -------
.../euclidean/twod/WelzlEncloser2DTest.java | 210 ---------
commons-geometry-hull/CONTRIBUTING.md | 115 -----
commons-geometry-hull/LICENSE.txt | 201 --------
commons-geometry-hull/NOTICE.txt | 6 -
commons-geometry-hull/README.md | 105 -----
commons-geometry-hull/pom.xml | 96 ----
.../apache/commons/geometry/hull/ConvexHull.java | 44 --
.../commons/geometry/hull/ConvexHullGenerator.java | 41 --
.../twod/AbstractConvexHullGenerator2D.java | 130 ------
.../hull/euclidean/twod/AklToussaintHeuristic.java | 163 -------
.../geometry/hull/euclidean/twod/ConvexHull2D.java | 107 -----
.../hull/euclidean/twod/ConvexHullGenerator2D.java | 32 --
.../hull/euclidean/twod/MonotoneChain.java | 162 -------
.../geometry/hull/euclidean/twod/package-info.java | 25 -
.../apache/commons/geometry/hull/package-info.java | 24 -
.../src/site/resources/profile.jacoco | 17 -
commons-geometry-hull/src/site/site.xml | 41 --
.../geometry/hull/DocumentationExamplesTest.java | 76 ----
.../euclidean/twod/AklToussaintHeuristicTest.java | 38 --
.../hull/euclidean/twod/ConvexHull2DTest.java | 177 -------
.../twod/ConvexHullGenerator2DAbstractTest.java | 506 ---------------------
.../hull/euclidean/twod/MonotoneChainTest.java | 57 ---
commons-geometry-spherical/pom.xml | 5 -
dist-archive/pom.xml | 38 --
pom.xml | 2 -
.../resources/spotbugs/spotbugs-exclude-filter.xml | 4 -
src/site/site.xml | 2 -
src/site/xdoc/userguide/index.xml | 140 ------
51 files changed, 4711 deletions(-)
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/resources/profile.jacoco b/commons-geometry-enclosing/src/site/resources/profile.jacoco
deleted file mode 100644
index a12755f..0000000
--- a/commons-geometry-enclosing/src/site/resources/profile.jacoco
+++ /dev/null
@@ -1,17 +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.
-# -----------------------------------------------------------------------------
-#
-# Empty file used to automatically trigger JaCoCo profile from commons parent pom
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-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/site/resources/profile.jacoco b/commons-geometry-hull/src/site/resources/profile.jacoco
deleted file mode 100644
index a12755f..0000000
--- a/commons-geometry-hull/src/site/resources/profile.jacoco
+++ /dev/null
@@ -1,17 +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.
-# -----------------------------------------------------------------------------
-#
-# Empty file used to automatically trigger JaCoCo profile from commons parent pom
diff --git a/commons-geometry-hull/src/site/site.xml b/commons-geometry-hull/src/site/site.xml
deleted file mode 100644
index 54b485f..0000000
--- a/commons-geometry-hull/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-hull/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-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-spherical/pom.xml b/commons-geometry-spherical/pom.xml
index a299ada..3f297d6 100644
--- a/commons-geometry-spherical/pom.xml
+++ b/commons-geometry-spherical/pom.xml
@@ -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/dist-archive/pom.xml b/dist-archive/pom.xml
index 0fd1da1..aecc12d 100644
--- a/dist-archive/pom.xml
+++ b/dist-archive/pom.xml
@@ -117,44 +117,6 @@ under the License.
<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..8147273 100644
--- a/pom.xml
+++ b/pom.xml
@@ -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/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/site.xml b/src/site/site.xml
index 1bb3df5..9b4673a 100644
--- a/src/site/site.xml
+++ b/src/site/site.xml
@@ -75,8 +75,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/userguide/index.xml b/src/site/xdoc/userguide/index.xml
index 4e2f93a..57afbbd 100644
--- a/src/site/xdoc/userguide/index.xml
+++ b/src/site/xdoc/userguide/index.xml
@@ -76,17 +76,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>
@@ -123,14 +112,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>
@@ -1099,127 +1080,6 @@ List<GreatArcPath> minusPaths = minus.getBoundaryPaths(); // size = 1
</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>