Return-Path: X-Original-To: apmail-commons-issues-archive@minotaur.apache.org Delivered-To: apmail-commons-issues-archive@minotaur.apache.org Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by minotaur.apache.org (Postfix) with SMTP id B305E11831 for ; Thu, 10 Jul 2014 21:23:05 +0000 (UTC) Received: (qmail 10454 invoked by uid 500); 10 Jul 2014 21:23:05 -0000 Delivered-To: apmail-commons-issues-archive@commons.apache.org Received: (qmail 10360 invoked by uid 500); 10 Jul 2014 21:23:05 -0000 Mailing-List: contact issues-help@commons.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: issues@commons.apache.org Delivered-To: mailing list issues@commons.apache.org Received: (qmail 10348 invoked by uid 99); 10 Jul 2014 21:23:05 -0000 Received: from arcas.apache.org (HELO arcas.apache.org) (140.211.11.28) by apache.org (qpsmtpd/0.29) with ESMTP; Thu, 10 Jul 2014 21:23:05 +0000 Date: Thu, 10 Jul 2014 21:23:05 +0000 (UTC) From: "Thomas Neidhart (JIRA)" To: issues@commons.apache.org Message-ID: In-Reply-To: References: Subject: [jira] [Commented] (MATH-1135) Bug in MonotoneChain: a collinear point landing on the existing boundary should be dropped (patch) MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 7bit X-JIRA-FingerPrint: 30527f35849b9dde25b450d4833f0394 [ https://issues.apache.org/jira/browse/MATH-1135?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14057980#comment-14057980 ] Thomas Neidhart commented on MATH-1135: --------------------------------------- Ah, this is quite an embarrassing bug, but thanks a lot for the report and especially for a reproducible test case. > Bug in MonotoneChain: a collinear point landing on the existing boundary should be dropped (patch) > -------------------------------------------------------------------------------------------------- > > Key: MATH-1135 > URL: https://issues.apache.org/jira/browse/MATH-1135 > Project: Commons Math > Issue Type: Bug > Affects Versions: 3.3 > Reporter: Guillaume Marceau > Priority: Minor > Labels: patch > Attachments: MonotoneChain_testCollinnearPointOnExistingBoundary.patch > > > The is a bug on the code in MonotoneChain.java that attempts to handle the case of a point on the line formed by the previous last points and the last point of the chain being constructed. When `includeCollinearPoints` is false, the point should be dropped entirely. In common-math 3,3, the point is added, which in some cases can cause a `ConvergenceException` to be thrown. > In the patch below, the data points are from a case that showed up in testing before we went to production. > {code:java} > Index: src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/MonotoneChain.java > =================================================================== > --- src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/MonotoneChain.java (revision 1609491) > +++ src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/MonotoneChain.java (working copy) > @@ -160,8 +160,8 @@ > } else { > if (distanceToCurrent > distanceToLast) { > hull.remove(size - 1); > + hull.add(point); > } > - hull.add(point); > } > return; > } else if (offset > 0) { > Index: src/test/java/org/apache/commons/math3/geometry/euclidean/twod/hull/ConvexHullGenerator2DAbstractTest.java > =================================================================== > --- src/test/java/org/apache/commons/math3/geometry/euclidean/twod/hull/ConvexHullGenerator2DAbstractTest.java (revision 1609491) > +++ src/test/java/org/apache/commons/math3/geometry/euclidean/twod/hull/ConvexHullGenerator2DAbstractTest.java (working copy) > @@ -204,6 +204,24 @@ > } > > @Test > + public void testCollinnearPointOnExistingBoundary() { > + final Collection points = new ArrayList(); > + points.add(new Vector2D(7.3152, 34.7472)); > + points.add(new Vector2D(6.400799999999997, 34.747199999999985)); > + points.add(new Vector2D(5.486399999999997, 34.7472)); > + points.add(new Vector2D(4.876799999999999, 34.7472)); > + points.add(new Vector2D(4.876799999999999, 34.1376)); > + points.add(new Vector2D(4.876799999999999, 30.48)); > + points.add(new Vector2D(6.0959999999999965, 30.48)); > + points.add(new Vector2D(6.0959999999999965, 34.1376)); > + points.add(new Vector2D(7.315199999999996, 34.1376)); > + points.add(new Vector2D(7.3152, 30.48)); > + > + final ConvexHull2D hull = generator.generate(points); > + checkConvexHull(points, hull); > + } > + > + @Test > public void testIssue1123() { > > List points = new ArrayList(); > {code} -- This message was sent by Atlassian JIRA (v6.2#6252)