[
https://issues.apache.org/jira/browse/GEOMETRY-144?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17686090#comment-17686090
]
Andreas Goss commented on GEOMETRY-144:
---------------------------------------
[~mattjuntunen] i think that is a good proposition. At least in the
three-dimensional case the {{Mesh}} seems to be more fitting than
{{{}ConvexHull{}}}. What would we then do with two-dimensional algorithm is the
end product {{{}LinePath{}}}?
Also we should discuss if and how we would use the builder pattern as proposed
earlier. The pattern seems quite appealing in light of the incremental
construction of the hull. But it should be noted that depending on the
implementation such an approach might lead to undesired consequences. QuickHull
depend on a complete point set from the beginning to guarantee optimal
performance. For example lets assume we have a point the following point set:
{(0, 0, 0), (1, 0, 0), (0, 1, 0), (0, 0, 1), (0, 0, 2), (0, 0, 3), ... , (0, 0,
100)}. My current implementation would guarantee, that the initial simplex
constructed is actually already the end result. Even if all the points (0, 0,
2) ... (0, 0, 100) are added afterwards QuickHull would mean that in this case
at most 7 new cones are constructed and added to the initial simplex. For this
we need to distribute all points and associate them with facets, but none can
be discarded right away. If we add all points incrementally in random order we
could in theory discard points if it can be determined that they are in fact
located inside the hull. In this case the resulting algorithm would be a
randomized beneath-beyond algorithm and not in fact QuickHull. At worst 99 new
cones would be constructed before finding the end result. At least the original
paper of
[QuickHull|https://www.cise.ufl.edu/~ungor/courses/fall06/papers/QuickHull.pdf]
offers empirical evidence, that distributing all points first and then
performing construction algorithm is to be preferred.
In essence the order in which points are added and cones are constructed has a
big impact on the overall performance of the algorithm.
> Review API in "hull" module
> ---------------------------
>
> Key: GEOMETRY-144
> URL: https://issues.apache.org/jira/browse/GEOMETRY-144
> Project: Commons Geometry
> Issue Type: Task
> Reporter: Gilles Sadowski
> Assignee: Gilles Sadowski
> Priority: Minor
> Fix For: 1.1
>
>
> Review codes in the
> [{{commons-geometry-hull}}|https://gitbox.apache.org/repos/asf?p=commons-geometry.git;a=tree;f=commons-geometry-hull;hb=HEAD]
> module.
> (x) Minimize the public API
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
