Wikipedia:Articles for deletion/Concave hull

The following discussion is an archived debate of the proposed deletion of the article below. Please do not modify it. Subsequent comments should be made on the appropriate discussion page (such as the article's talk page or in a deletion review). No further edits should be made to this page.

The result was delete. Secret ^account 19:24, 18 October 2014 (UTC)[reply]

Concave hull

(Find sources: Google (books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL)

The content of the article is based on a single published paper [1], strangely not cited in the pages. The other references are either unpublished research reports, or a patent (apparently, algorithms may be patented in Portugal) by the same authors, or papers that do not contain the term "concave hull", and cite the paper of these authors as one item among several papers addressing the same problem. Thus this article reports only original research, with one primary source and no secondary source.

The term "concave hull" denotes here a notion that is not well defined (as quoted by the rare papers that use the terms) and is thus undoubtedly non-notable.

A redirect or a merge cannot be done, as the subject of the article is commonly called Shape reconstruction or Contour reconstruction in computational geometry, and the corresponding article does not exist. A move is also excluded, as the article mention only one particular algorithm among many, and thus breaks WP:NPOV policy. D.Lazard (talk) 17:31, 9 October 2014 (UTC)[reply]

Automated comment: This AfD was not correctly transcluded to the log (step 3). I have transcluded it to Wikipedia:Articles for deletion/Log/2014 October 9. —cyberbot I ^Notify_Online 17:40, 9 October 2014 (UTC)[reply]
Automated comment: This AfD cannot be processed correctly because of an issue with the header. Please make sure the header has only 1 article, and doesn't have any HTML encoded characters.—cyberbot I ^Notify_Online 17:40, 9 October 2014 (UTC)[reply]

Note: This debate has been included in the list of Computing-related deletion discussions. NorthAmerica¹⁰⁰⁰ 18:33, 9 October 2014 (UTC)[reply]

Note: This debate has been included in the list of Visual arts-related deletion discussions. NorthAmerica¹⁰⁰⁰ 18:33, 9 October 2014 (UTC)[reply]

Note: This debate has been included in the list of Science-related deletion discussions. NorthAmerica¹⁰⁰⁰ 18:33, 9 October 2014 (UTC)[reply]

Keep - this is a well understood concept with a large number of applications. The functionality has been implemented in: Oracle (SDO_GEOM.SDO_CONCAVEHULL and SDO_GEOM.SDO_CONCAVEHULL_BOUNDARY), PostGIS (ST_ConcaveHull), GRASS GIS (v.concave.hull), QGIS (core processing toolbox), OpenJUMP ([2]), LAStools (lasboundary). A recent paper not yet integrated in the article [3], which also describe alpha and chi shapes as they relate to the content of the article. +mt 22:37, 9 October 2014 (UTC)[reply]

Comment. I can't understand this concept. Having looked at the papers mentioned above, I can't seem to locate a definition. It seems like the authors assumed the notion was intuitive and set about calculating it, but of course there's not a unique smallest polygon bounding an arbitrary finite set of points, and in fact the lim inf of areas of non-convex polygons bounding a finite point set is zero, so it's not clear to me at all that the thing they are calculating even exists. This really looks like pseudoscience to me but somebody knowledgeable of computer science should take a look at it. --Sammy1339 (talk) 03:08, 10 October 2014 (UTC)[reply]

A reference by Moreira and Santos was added after you commented. Could you take a look at it? --50.53.57.116 (talk) 20:32, 10 October 2014 (UTC)[reply]
Here's one possible definition from Park and Oh (2014) "The term ‘convex hull’ indicates the boundary of the minimal convex set containing a given non-empty finite set of points in the plane" +mt 23:55, 12 October 2014 (UTC)[reply]

That's the definition of a convex hull, which is a real concept. A definition of a "concave hull" is still lacking, because there is no minimal non-convex set bounding a finite set of points in the plane. --Sammy1339 (talk) 23:06, 15 October 2014 (UTC)[reply]

The concave hull is not unique. There is a parameter that controls how refined the hull is. A simple definition of a concave hull of a set of points is a union of disks, with each disk centered on a point of the set. The radius of the disk is the parameter. See the "threshold" parameter here. --50.53.36.23 (talk) 22:39, 16 October 2014 (UTC)[reply]

No, the article and its sources describe the concave hull as a polygon, and a finite union of disks is never a polygon. D.Lazard (talk) 23:32, 16 October 2014 (UTC)[reply]

That is a simplified example to show how the parameter would be defined. Triangles or hexagons could be used instead of disks. The essential point is that there is a documented "threshold" parameter here. --50.53.36.23 (talk) 02:38, 17 October 2014 (UTC)[reply]

No, again, the link says only that this parameter is ~~an integer~~ a real number in the range 0–10. D.Lazard (talk) 13:02, 17 October 2014 (UTC)[reply]

The source says: "threshold=float", so the parameter is modeling a real number. Apparently, the parameter is confined to the interval $[0, 10]$ . The source doesn't say why, but the GRASS GIS software is open source. The source code can be downloaded here. --50.53.38.50 (talk) 14:07, 17 October 2014 (UTC)[reply]

v.concave.hull is written in Python, and the threshold is converted to a percentage by adding 90. --50.53.38.50 (talk) 16:56, 17 October 2014 (UTC)[reply]

Comment. What is the relationship between these objects and alpha shapes? Maybe this should just redirect to that article. (Last I looked, the article titled alpha shape lacked any good illustrations.) Michael Hardy (talk) 21:44, 10 October 2014 (UTC)[reply]

I was looking at this too, and from what I see α-shapes predate any other work that has been referred to as "concave hull". Oracle even has a different SDO_GEOM.SDO_ALPHA_SHAPE routine. Duckham et al. (2008) introduced $\chi$ -shapes as distinct from α-shapes from Edelsbrunner et al. (1993) and many other shapes, such as ${\mathcal {A}}$ -shapes, r-shapes, and s-shapes. $\chi$ -shapes are used as a basis for some of the Oracle algorithms, as described by Matt Duckam, and more here. There are several other algorithms developed over the past few years such as swing arm, KNN-based, etc. that appear to be group as "concave hull" algorithms. +mt 23:55, 12 October 2014 (UTC)[reply]

Keep - A pretty basic concept. With sources now located, this should be an easy keep. (Which is not to say the article as it stands doesn't need to be wrangled into shape; it's a hot mess as it currently stands.) Delete, per comments below ∴ ZX95 ^[discuss] 03:09, 14 October 2014 (UTC)[reply]
Delete. After reading through the algorithms I'm convinced this is basically garbage. The algorithm from the first source above will return a result dependent on an arbitrary ordering of the point set, and there is the rather strange property that adding points to the set will tend to make the "concave hull" smaller. I'm not impressed by the quality of the references, one of which cites this Wikipedia article. And @Michael Hardy: these are completely unrelated to alpha shapes. The supposed applications mentioned by Mwtoews above gave me some pause, but that's not the same as a reference explaining this concept. So, unless someone can show me something amazing (like a definition of what this even is), I'm saying delete per WP:FRINGE/PS. --Sammy1339 (talk) 22:58, 15 October 2014 (UTC)[reply]
Delete and/or redirect to concave set. The article makes it look like there is a consistent concept here, where there is none. Different authors have used the phrase "concave hull" to mean different inconsistent things; for instance, the two references with "concave hull" in their title are not about the same construction. None of these is widely accepted as a standard meaning of the phrase. There is room for articles on individual well-defined constructions that attempt to capture the shape of a non-convex point set (e.g. alpha-shapes) but "concave hull" is the wrong name and the article is entirely focused on the wrong notion that there is a common ideal that all these different constructions are trying to capture. —David Eppstein (talk) 04:11, 16 October 2014 (UTC)[reply]
Delete as poorly defined and non-notable concept, with few cites on Google Scholar. -- 120.23.241.114 (talk) 13:12, 16 October 2014 (UTC)[reply]
Comment. Here are two definitions from the sources provided by Mwtoews above:

"The concave hull of a geometry represents a possibly concave geometry that encloses all geometries within the set."[4]
"For a finite set of input points P, the algorithm produces a simple, possibly non-convex polygon that contains all the points in P and is contained within and possibly equal to the convex hull."[5]

The latter appears to be defining the term "“characteristic shapes” or simply χ (chi) shapes".

Would translating those into set notation constitute original research?

--50.53.36.23 (talk) 22:20, 16 October 2014 (UTC)[reply]

Neither of those defines the "concave hull." -- 120.23.23.27 (talk) 23:09, 16 October 2014 (UTC)[reply]

Concave hulls are not unique. There is a family of hulls indexed by a parameter. See the "threshold" parameter here. --50.53.36.23 (talk) 03:11, 17 October 2014 (UTC)[reply]

Comment. I have asked two editors who have recently worked on Concave hull to comment or vote: Kku, JohnBlackburne. --50.53.36.23 (talk) 05:42, 17 October 2014 (UTC)[reply]
Dear community members. Would it be in vain to humbly ask, why you should be believing in the relevance of a concept that is in everyday use in GISs and by GIS professionals worldwide while WP is ailing (and quite painfully, I might say) from dozens of one-liners, hundreds of articles poisoned with marketing and advertising lingo and garbled personal ideas. Suffice it to say that D.Lazard started his rally against the article while I was in the first minutes of article creation (you realize that the original complaint about only one reference (and the entirely void observation that "scholar google" wouldn't be capable of producing any additional hints) still serves as the beacon of the argument. I have rarely noticed that any unreferenced half-baked idea in enWP has been attacked right after creation in such an unreflected manner. Fellow citizens: In a WP world where the bazillionth article on some version of run-of-the mill software is evolving unfettered, while a computational geometry heuristic ( - I grant you that - ) that might be new to some but is of practical relevance to countless others is attacked by individuals who overall do not appear to be involved in the daily praxis it should be a legitimate question whether you are not wasting your energy on something that might only be in need of a better name. Keep -- Kku 06:28, 17 October 2014 (UTC)

The edit history shows that the article was PRODed less than two hours after creation. --50.53.36.23 (talk) 06:47, 17 October 2014 (UTC)[reply]

@Kku: I would be happy to reverse my delete vote if you could provide both a clear definition of the concept of a concave hull and two reliable sources (such as selective peer-reviewed journals) that discuss the concept you define. --Sammy1339 (talk) 21:20, 17 October 2014 (UTC)[reply]

The requirement is for verifiable, reliable sources. Peer-review is nice, but not necessary. Anyway, the article already references Duckham, et al, which was published in the peer-reviewed journal Pattern Recognition. A free preprint version is here. NB: They use the term characteristic shape. --50.53.38.50 (talk) 02:15, 18 October 2014 (UTC)[reply]

Yes, that's why I said "such as." As for this paper, while (unlike some of the other references) it is coherent, the term "concave hull" does not appear in it at all. Once again, can you provide a definition of the term "concave hull" and two reliable sources that discuss the construction so-defined? --Sammy1339 (talk) 02:43, 18 October 2014 (UTC)[reply]

The article name can be changed and articles can accommodate name variants through redirects. The exact article name is almost irrelevant to the deletion discussion. Please say whether the definition of characteristic shape in Duckham, et al, meets your standards for a definition. Can you understand the definition? --50.53.38.50 (talk) 03:14, 18 October 2014 (UTC)[reply]

Delete: If the sources don't even agree on the same definition, then they can't be talking about the same subject, and it doesn't pass the GNG, done deal. As far as Kku's comments go, whether or not this concept - and do YOU have a definition? - is of practical relevance to "countless others" doesn't matter worth a diddly. It can keep on being of as much relevance to them as it was a year ago. It just doesn't get to have a Wikipedia article about it, that's all. Nha Trang 20:49, 17 October 2014 (UTC)[reply]

Please cite wikilaw saying that sources have to be in perfect agreement. Articles commonly say that sources disagree:

"There is no scholarly agreement on which are the most common motivations for war."(War)
"Sources disagree on whether North Vietnam played a direct role in aiding and organizing South Vietnamese rebels prior to 1960."(Vietnam War)

--50.53.38.50 (talk) 02:29, 18 October 2014 (UTC)[reply]

Comment: Some of the sources says that the problem is to find a polygon enclosing all points, which is a compromise between minimizing the perimeter and minimizing the area. Translated into mathematics, this means minimizing some function of the perimeter and the area. This opens two problems: 1/ Find an efficient algorithm for this optimization problem, hopefully independent of the choice of the compromise function. 2/ Determine the best compromise for the applications. This may depend on the application, and, at this level, is not a mathematical problem. None problem has been clearly addressed in the sources: the chosen compromise function, if any, is not even clearly described in the introductions, and there is no claim that the algorithms optimize something. IMO, these two problems are still open and could be a subject for a Ph.D. An open Ph.D. subject is certainly not a topic for a Wikipedia article. D.Lazard (talk) 08:36, 18 October 2014 (UTC)[reply]

That sounds like a reasonable way to set up a research problem, but Duckman, et al, say "There is no “correct” characteristic shape." (p. 2)

Here is a formalization based on this sentence from Duckman, et al: "For a finite set of input points P, the algorithm produces a simple, possibly non-convex polygon that contains all the points in P and is contained within and possibly equal to the convex hull." (p. 2)

Given a set of points P in the plane, a characteristic shape is any simply connected polygon S that contains P and is a subset of the convex hull H. Thus:

$P\subset S\subset H$

An additional constraint can specify that the vertices of S be in P (Do Duckman, et al, implicitly assume this?). This definition does not specify the length parameter that Duckman, et al, describe: "Changing the length parameter produces one of a finite family of totally ordered characteristic shapes, ranging from the convex hull at one extreme to a uniquely defined simple polygon with minimal area at the other extreme." (p. 30) Can you suggest a way to do that?

Does such a formalization constitute original research?

--50.53.55.68 (talk) 11:47, 18 October 2014 (UTC)[reply]

Delete In AfD, the main questions to answer are: is the topic notable and is the article improvable? Whether there is a precise, unique definition or solid mathematical foundations is irrelevant. In the area of sources, there are the primary papers by Moreira, et al, Park, et al, and Xu, et al. There are other papers on shape reconstruction from point clouds, such as Duckham, et al and the alpha shape literature, but they aren't specifically on concave hulls and as far as I can tell, don't mention concavity as the crucial concept. There are also many heuristic implementations in GIS systems, databases like Oracle, and statistical systems like R. It is clear that the topic exists, but what we don't have are reliable secondary sources describing and comparing the various heuristics and their relative importance and impact. The introductory sections of the three papers have some secondary content, but not enough to build a neutral article on this subject. It seems it is WP:TOOSOON for this topic to have proper reviews and surveys written. The topic fails notability guidelines per WP:GNG. I just hate deleting verifiable material and there is some in this subject, but I can't see any good targets on WP. When a shape reconstruction article is written, this topic could be a part of it, along with alpha shape and visual hull. But I must reluctantly recommend deletion. --Mark viking (talk) 13:17, 18 October 2014 (UTC)[reply]

The above discussion is preserved as an archive of the debate. Please do not modify it. Subsequent comments should be made on the appropriate discussion page (such as the article's talk page or in a deletion review). No further edits should be made to this page.