Community
Participate
Working Groups
Due to several design flaws within the current geomtry API (mostly related to the integration of non-precision and precision API) and due to an additional lack of functionality (e.g. bug #307278) it makes sense to come up with a new double-precision geometry API, which - to make it consumable outside GEF as well - should be created in its own plug-in (org.eclipse.gef4.geometry).
Checked in an initial contribution (which is not yet feature-complete) in the form of two plugins (org.eclipse.gef4.geometry and org.eclipse.gef4.geometry.tests), whose code-base is partially based on code transferred from org.eclipse.draw2d.geometry and org.eclipse.draw2d.test (I transferred all copyright notices and added author tags - inferred from history - where code was reused from Draw2d). Checked in both plugins into cvs HEAD (under a newly created module GEF4).
Created attachment 202484 [details] Implementation of the ellipse.getIntersections(Line l) method. A non-optimized first implementation of the ellipse.getIntersections(Line l) method. The method is too big, maybe it can be split up into several parts. But it works! \o/
Created attachment 202501 [details] Implementation of the getIntersections(...) methods in the Ellipse class Adds implementations for the ellipse.getIntersections(Line line), ellipse.getIntersections(Rectangle rect), ellipse.getIntersections(Polygon polygon) and ellipse.getIntersections(Polyline polyline) methods.
(In reply to comment #3) > Created attachment 202501 [details] > Implementation of the getIntersections(...) methods in the Ellipse class > > Adds implementations for the ellipse.getIntersections(Line line), > ellipse.getIntersections(Rectangle rect), ellipse.getIntersections(Polygon > polygon) and ellipse.getIntersections(Polyline polyline) methods. Thanks Matthias! Can you please confirm that: (a) you wrote 100% of the code (b) that you have the right to contribute the code to Eclipse under the terms of the EPL
(In reply to comment #4) > (In reply to comment #3) > > Created attachment 202501 [details] [details] > > Implementation of the getIntersections(...) methods in the Ellipse class > > > > Adds implementations for the ellipse.getIntersections(Line line), > > ellipse.getIntersections(Rectangle rect), ellipse.getIntersections(Polygon > > polygon) and ellipse.getIntersections(Polyline polyline) methods. > > Thanks Matthias! Can you please confirm that: > (a) you wrote 100% of the code > (b) that you have the right to contribute the code to Eclipse under the terms > of the EPL Yes, I wrote 100% of the code and I have the right to contribute the code to Eclipse under the terms of the EPL.
(In reply to comment #5) > (In reply to comment #4) > > (In reply to comment #3) > > > Created attachment 202501 [details] [details] [details] > > > Implementation of the getIntersections(...) methods in the Ellipse class > > > > > > Adds implementations for the ellipse.getIntersections(Line line), > > > ellipse.getIntersections(Rectangle rect), ellipse.getIntersections(Polygon > > > polygon) and ellipse.getIntersections(Polyline polyline) methods. > > > > Thanks Matthias! Can you please confirm that: > > (a) you wrote 100% of the code > > (b) that you have the right to contribute the code to Eclipse under the terms > > of the EPL > > Yes, I wrote 100% of the code and I have the right to contribute the code to > Eclipse under the terms of the EPL. Thanks. Patch committed to cvs.
Created attachment 205718 [details] containment/intersection methods for the existing shapes and quadratic and cubic bézier curves with intersection methods This patch provides implementations for the quadratic and cubic bézier curves. Furthermore it introduces a new angle/rotation interface which consists of an Angle class that provides unit conversion from/to degrees/radians. All methods that require an angle parameter, now require an Angle object instead. All methods that return an angle, now return an Angle object instead. This is done to prevent the user from working with angles in the incorrect unit. Moreover, this patch implements many containment/intersection methods for the existing shapes. The Ellipse/Ellipse intersection is delegated to the new cubic bézier curve's intersection methods. There were some difficult corner cases for the comparison tests in the PrecisionUtils class. That's why a new mechanism is implemented which uses a tolerance for the comparisons that is adjustable by the user.
Comment on attachment 205718 [details] containment/intersection methods for the existing shapes and quadratic and cubic bézier curves with intersection methods Looks good! Thank's very much. Copyright header look fine. You already know the game... can you pleas confirm that: (a) you have written 100% of the code and (b) that you have the right to contribute the code under the terms of the EPL?
(In reply to comment #8) > Comment on attachment 205718 [details] > containment/intersection methods for the existing shapes and quadratic and > cubic bézier curves with intersection methods > > Looks good! Thank's very much. Copyright header look fine. You already know > the game... can you pleas confirm that: > > (a) you have written 100% of the code and > (b) that you have the right to contribute the code under the terms of the EPL? Yes, I wrote 100% of the code and I have the right to contribute the code to Eclipse under the terms of the EPL.
(In reply to comment #9) > (In reply to comment #8) > > Comment on attachment 205718 [details] [details] > > containment/intersection methods for the existing shapes and quadratic and > > cubic bézier curves with intersection methods > > > > Looks good! Thank's very much. Copyright header look fine. You already know > > the game... can you pleas confirm that: > > > > (a) you have written 100% of the code and > > (b) that you have the right to contribute the code under the terms of the EPL? > > Yes, I wrote 100% of the code and I have the right to contribute the code to > Eclipse under the terms of the EPL. Fine. As the contribution is larger than 250 LOC, I will have to open an IPZilla for this.
(In reply to comment #10) > (In reply to comment #9) > > (In reply to comment #8) > > > Comment on attachment 205718 [details] [details] [details] > > > containment/intersection methods for the existing shapes and quadratic and > > > cubic bézier curves with intersection methods > > > > > > Looks good! Thank's very much. Copyright header look fine. You already know > > > the game... can you pleas confirm that: > > > > > > (a) you have written 100% of the code and > > > (b) that you have the right to contribute the code under the terms of the EPL? > > > > Yes, I wrote 100% of the code and I have the right to contribute the code to > > Eclipse under the terms of the EPL. > > Fine. As the contribution is larger than 250 LOC, I will have to open an > IPZilla for this. Done, opened https://dev.eclipse.org/ipzilla/show_bug.cgi?id=5768 to keep track of this.
(In reply to comment #11) > (In reply to comment #10) > > (In reply to comment #9) > > > (In reply to comment #8) > > > > Comment on attachment 205718 [details] [details] [details] [details] > > > > containment/intersection methods for the existing shapes and quadratic and > > > > cubic bézier curves with intersection methods > > > > > > > > Looks good! Thank's very much. Copyright header look fine. You already know > > > > the game... can you pleas confirm that: > > > > > > > > (a) you have written 100% of the code and > > > > (b) that you have the right to contribute the code under the terms of the EPL? > > > > > > Yes, I wrote 100% of the code and I have the right to contribute the code to > > > Eclipse under the terms of the EPL. > > > > Fine. As the contribution is larger than 250 LOC, I will have to open an > > IPZilla for this. > > Done, opened https://dev.eclipse.org/ipzilla/show_bug.cgi?id=5768 to keep track > of this. As CQ has been resolved, committed patch to cvs, having removed superfluous polygon test from tests, having adjusted contribution comments, and having re-organized imports. Thank's for the contribution Matthias.
Created attachment 206845 [details] several bug fixes and many new tests This patch adds many tests for the Angle, Dimension, Line, PointListUtils, Point, Polygon, PolynomCalculationUtils, Rectangle, Straight and Vector classes. It also contains several bug fixes for erroneous behaviour that is covered by the new tests. The bezier curve intersection finding algorithm is not yet stable enough. It will be added later with another patch. I wrote 100% of the code and I have the right to contribute the code to Eclipse under the terms of the EPL.
(In reply to comment #13) > Created attachment 206845 [details] > several bug fixes and many new tests > > This patch adds many tests for the Angle, Dimension, Line, PointListUtils, > Point, Polygon, PolynomCalculationUtils, Rectangle, Straight and Vector > classes. It also contains several bug fixes for erroneous behaviour that is > covered by the new tests. > > The bezier curve intersection finding algorithm is not yet stable enough. It > will be added later with another patch. > > I wrote 100% of the code and I have the right to contribute the code to > Eclipse under the terms of the EPL. Thanks! It seems the test case for EllipseTest fails now (I checked it was a false positive before), but as Ellipse intersection depends on Bezier Curve intersection internally, I think that is something we can live with for the moment.
(In reply to comment #14) > (In reply to comment #13) > > Created attachment 206845 [details] [details] > > several bug fixes and many new tests > > > > This patch adds many tests for the Angle, Dimension, Line, PointListUtils, > > Point, Polygon, PolynomCalculationUtils, Rectangle, Straight and Vector > > classes. It also contains several bug fixes for erroneous behaviour that is > > covered by the new tests. > > > > The bezier curve intersection finding algorithm is not yet stable enough. It > > will be added later with another patch. > > > > I wrote 100% of the code and I have the right to contribute the code to > > Eclipse under the terms of the EPL. > > Thanks! It seems the test case for EllipseTest fails now (I checked it was a > false positive before), but as Ellipse intersection depends on Bezier Curve > intersection internally, I think that is something we can live with for the > moment. AngleTest and PointListUtilsTests are still lacking valid copyright headers. Could you add them please?
Created attachment 206852 [details] several bug fixes and many new tests (headers added) I added the headers and removed some debug output.
Comment on attachment 206852 [details] several bug fixes and many new tests (headers added) Ok, that looks better.
(In reply to comment #17) > Comment on attachment 206852 [details] > several bug fixes and many new tests (headers added) > > Ok, that looks better. As the related CQ 5800 has been approved, committed patch to cvs HEAD, setting EllipseTest to @Ignore until we have fixed that issue.
Created attachment 207479 [details] a few bug fixes and a new CurveUtils class that implements commonly used curve operations This patch fixes a few bugs and provides a new utility class for commonly used curve operations. The bugs fixed are mainly in the PolynomCalculationUtils' getCubicRoots() method, where polynomial root calculation of cubic polynoms includes two incorrect short cuts. The CurveUtils class is now used to calculate common curve operations. It uses homogeneous coordinates to calculate lines and intersections of lines and it contains the implementation of a Bezier clipping algorithm to compute the intersection points of two Bezier curves. Moreover, it abstracts the subdivision and parameter evaluation algorithms for arbitrary Bezier curves and the containment check algorithm for up to degree three Bezier curves.
(In reply to comment #19) > Created attachment 207479 [details] > a few bug fixes and a new CurveUtils class that implements commonly used curve > operations > > This patch fixes a few bugs and provides a new utility class for commonly used > curve operations. > > The bugs fixed are mainly in the PolynomCalculationUtils' getCubicRoots() > method, where polynomial root calculation of cubic polynoms includes two > incorrect short cuts. > > The CurveUtils class is now used to calculate common curve operations. It uses > homogeneous coordinates to calculate lines and intersections of lines and it > contains the implementation of a Bezier clipping algorithm to compute the > intersection points of two Bezier curves. Moreover, it abstracts the > subdivision and parameter evaluation algorithms for arbitrary Bezier curves and > the containment check algorithm for up to degree three Bezier curves. Oh, I forgot: I wrote 100% of the code and I have the right to contribute the code to Eclipse under the terms of the EPL.
Created attachment 207484 [details] a few bug fixes and a new CurveUtils class that implements commonly used curve operations (header added) I just noticed, that I forgot to add the copyright header. This is fixed now.
Comment on attachment 207484 [details] a few bug fixes and a new CurveUtils class that implements commonly used curve operations (header added) It seems like the Bezier clipping algorithm makes wrong assumptions about the signed distance of a point to a line. I am going to fix this flaw and create a new patch.
Created attachment 208179 [details] a few bug fixes and a new CurveUtils class that implements commonly used curve operations It turned out, that the signed distance calculation worked as it should, but the Bézier clipping algorithm did not do the fat line clipping correctly in some cases. These have been fixed now. It does not suffer from imprecise polynomial root calculation anymore, because it does not calculate polynomial roots anymore :) Tests have been added for the CurveUtils class. The implementations of the containment check and the intersection points calculation are now independent of each other. Moreover, another algorithm is used to perform the containment check, which works for arbitrary Bézier curves. The Bézier clipping algorithm uses an impure short cut to robustly find end point intersections. It simply adds the end points to the list of intersection points if they are equal and the areas of the bounding boxes of both curves are below a small constant value. This is done, because floating point errors prevent the algorithm from finding these points of intersections in some cases.
(In reply to comment #23) > Created attachment 208179 [details] I wrote 100% of the code and I have the right to contribute the code to Eclipse under the terms of the EPL.
(In reply to comment #24) > (In reply to comment #23) > > Created attachment 208179 [details] [details] > > I wrote 100% of the code and I have the right to contribute the code to > Eclipse under the terms of the EPL. Thanks again Matthias. As this is again larger as 250 LOC, it will required an IPZilla...
Created attachment 208923 [details] missing intersection routines and robust bezier clipping Added all missing getIntersections(...) routines. The Geometry interface will probably get this method, so that you can use it generally with two Geometry objects. Corrected the Bézier-Clipping algorithm: . Added a second Fat-Line-Clipping to the algorithm. The second Fat-Line is the Fat-Line perpendicular to the first Fat-Line. . Changed the curve-splitting fall-back. It does now exclude a very small parameter range between the two intervals. Fat-Line-Clipping: . Do only check the convex hull of the control polygon of the Bézier curve for intersections with the Fat-Line-Bounds. . Do only account real intersections. A point of intersection is only calculated if the bounds are crossed. I wrote 100% of the code and I have the right to publish it under the terms of the right to contribute the code to Eclipse under the terms of the EPL.
Comment on attachment 208923 [details] missing intersection routines and robust bezier clipping Thanks Matthias, looks good. As this contains all changes of its predecessor (whose IPZilla is not yet processed), I have updated CQ 5876 accordingly.
(In reply to comment #28) > Comment on attachment 208923 [details] > missing intersection routines and robust bezier clipping > > Thanks Matthias, looks good. As this contains all changes of its predecessor > (whose IPZilla is not yet processed), I have updated CQ 5876 accordingly. CQ has been approved. Committed all changes to cvs HEAD: Thanks again Matthias!
Created attachment 212739 [details] Complete refactoring of the geometry API Adjusted abstraction interfaces with respect to intersection and containment tests. You can test two IGeometry objects for at least one point in common, by using the IGeometry.touches(IGeometry) method. For ICurve objects, intersects() and overlaps() exists to test for a finite and infinite number of intersections, as well as getIntersections(ICurve) which computes the individual points of intersection. For IShape objects, contains(IGeometry) serves to test if an IShape fully contains an arbitrary IGeometry object. The IPolyCurve does now extend the ICurve interface, so that you can use its methods for an IPolyCurve, too. The PolyBezier is used as the generic outline of any IShape. Removed a lot of duplicate code by generic abstract base classes and generic utility methods. Rotation, translation and scaling short-cut methods are lifted to the AbstractRectangleBasedGeometry and AbstractPointListBasedGeometry classes. The CurveUtils package provides utility methods to compute intersection points, and to evaluate the intersects() and contains() tests. Arbitrary Bezier curves are available using the BezierCurve class. Enhanced the javadoc documentation. Added more tests. Added examples. The examples shipped with this patch are only embryonic, but you can already use them to visualize the functionality of the geometry API.
> Created attachment 212739 [details] > Complete refactoring of the geometry API I forgot... I wrote 100% of the code and I have the right to contribute the code to Eclipse under the terms of the EPL.
Thanks Matthias. Could you please ensure that all files contain the appropriate copyright headers. Those that you created seem to miss a file header (at least within the examples plug-in). Also, those already existing files that you "touched" should contain your name under the contributions entry. Could you please adjust that and upload a modified patch afterwards?
(In reply to comment #32) > Thanks Matthias. Could you please ensure that all files contain the appropriate > copyright headers. Those that you created seem to miss a file header (at least > within the examples plug-in). Also, those already existing files that you > "touched" should contain your name under the contributions entry. > > Could you please adjust that and upload a modified patch afterwards? Matthias, the examples seem to contain the Bean Shell (bsh-2.0b4.jar). This is licensed under LPGL and I am not sure we can bundle this. Could you please remove the REPL example (and the related lib) for now. We can then check how to integrate this after having applied this contribution.
Created attachment 212771 [details] Complete refactoring of the geometry API Added the copyright headers and removed the .repl and .overview examples (including bsh-2.0b4.jar).
Created attachment 212775 [details] Complete refactoring of the geometry API Conformed the patch to the new encoding and line ending specifications.
Created attachment 212776 [details] Complete refactoring of the geometry API After uploading the last patch, I encountered an easy-to-fix bug in the QuadraticCurve.toPath() method. This is fixed in this new version of the patch.
Thanks Matthais, looks good! I will open a CQ to handle this contribution.
(In reply to comment #37) > Thanks Matthais, looks good! I will open a CQ to handle this contribution. Created CQ 6363 to keep track of the contribution.
(In reply to comment #38) > (In reply to comment #37) > > Thanks Matthais, looks good! I will open a CQ to handle this contribution. > > Created CQ 6363 to keep track of the contribution. Matthias, the test case within CurveUtilsTests that makes use of the example data provided in http://web.mit.edu/hyperbook/Patrikalakis-Maekawa-Cho/node111.html seems to be problematic w.r.t. to IP. Can you please remove it and re-create the patch?
Created attachment 213615 [details] Complete refactoring of the geometry API I changed the respective test case to not use the data from that source but rather compute appropriate data in the test itself.
(In reply to comment #40) > Created attachment 213615 [details] > Complete refactoring of the geometry API > > I changed the respective test case to not use the data from that source but > rather compute appropriate data in the test itself. OK, CQ has finally been approved, so I have applied the patch and pushed all changes to origin/master. Thanks for the contribution, Matthias!
Created attachment 216278 [details] Implements Region and Ring and adds transformation interfaces and their implementations This patch implements the IPolyShapes Region and Ring. Moreover, interfaces for the various transformation short-cut methods are introduced. For all *.planar classes an implementation of the respective transformation interfaces is given. A Region combines multiple Rectangle objects. These can be queried as a whole. Analogous, a Ring combines multiple Polygon objects. The new transformation interfaces ITranslatable, IScalable, IRotatable and IRotatableInPlace consist of the individual short-cut methods for translation, scaling and rotation, respectively. Additionally, this patch includes many java-doc enhancements, a greater test suite and several bug fixes: Polygon.contains(Line), Straight.getParameterAt(Point), BezierCurve.getOverlap(BezierCurve) and several arc computations. Besides, the code is partially restructured and optimized for performance (better algorithms) so that most of the BezierCurve functionality is faster now. New utility functions are added/modified, too: Polygon.getTriangulation(), PointListUtils.rotate(...), PointListUtils.translate(...), PointListUtils.scale(...). I wrote 100% of the code and I have the right to contribute the code to Eclipse under the terms of the EPL.
Thanks Matthias, unfortunately I am not able to apply the patch to the master branch because of the following issues: error: patch failed: org.eclipse.gef4.geometry/src/org/eclipse/gef4/geometry/planar/Arc.java:7 error: org.eclipse.gef4.geometry/src/org/eclipse/gef4/geometry/planar/Arc.java: patch does not apply error: patch failed: org.eclipse.gef4.geometry/src/org/eclipse/gef4/geometry/planar/CubicCurve.java:14 error: org.eclipse.gef4.geometry/src/org/eclipse/gef4/geometry/planar/CubicCurve.java: patch does not apply error: patch failed: org.eclipse.gef4.geometry/src/org/eclipse/gef4/geometry/planar/Pie.java:7 error: org.eclipse.gef4.geometry/src/org/eclipse/gef4/geometry/planar/Pie.java: patch does not apply error: patch failed: org.eclipse.gef4.geometry/src/org/eclipse/gef4/geometry/planar/QuadraticCurve.java:13 error: org.eclipse.gef4.geometry/src/org/eclipse/gef4/geometry/planar/QuadraticCurve.java: patch does not apply error: patch failed: org.eclipse.gef4.geometry/src/org/eclipse/gef4/geometry/planar/Region.java:7 error: org.eclipse.gef4.geometry/src/org/eclipse/gef4/geometry/planar/Region.java: patch does not apply error: patch failed: org.eclipse.gef4.geometry/src/org/eclipse/gef4/geometry/planar/Ring.java:7 error: org.eclipse.gef4.geometry/src/org/eclipse/gef4/geometry/planar/Ring.java: patch does not apply Can you please check that the patch can be applied appropriately to the latest origin/master?
Sorry, was a problem on my side (I copied the contents of the patch into a file instead of downloading it here; it seems something has gone wrong this way). I will take a look into it and open a CQ as appropriate. (In reply to comment #43) > Thanks Matthias, unfortunately I am not able to apply the patch to the master > branch because of the following issues: > > error: patch failed: > org.eclipse.gef4.geometry/src/org/eclipse/gef4/geometry/planar/Arc.java:7 > error: org.eclipse.gef4.geometry/src/org/eclipse/gef4/geometry/planar/Arc.java: > patch does not apply > error: patch failed: > org.eclipse.gef4.geometry/src/org/eclipse/gef4/geometry/planar/CubicCurve.java:14 > error: > org.eclipse.gef4.geometry/src/org/eclipse/gef4/geometry/planar/CubicCurve.java: > patch does not apply > error: patch failed: > org.eclipse.gef4.geometry/src/org/eclipse/gef4/geometry/planar/Pie.java:7 > error: org.eclipse.gef4.geometry/src/org/eclipse/gef4/geometry/planar/Pie.java: > patch does not apply > error: patch failed: > org.eclipse.gef4.geometry/src/org/eclipse/gef4/geometry/planar/QuadraticCurve.java:13 > error: > org.eclipse.gef4.geometry/src/org/eclipse/gef4/geometry/planar/QuadraticCurve.java: > patch does not apply > error: patch failed: > org.eclipse.gef4.geometry/src/org/eclipse/gef4/geometry/planar/Region.java:7 > error: > org.eclipse.gef4.geometry/src/org/eclipse/gef4/geometry/planar/Region.java: > patch does not apply > error: patch failed: > org.eclipse.gef4.geometry/src/org/eclipse/gef4/geometry/planar/Ring.java:7 > error: > org.eclipse.gef4.geometry/src/org/eclipse/gef4/geometry/planar/Ring.java: patch > does not apply > > Can you please check that the patch can be applied appropriately to the latest > origin/master?
Matthias, quite nice contribution. I found two small things we would have to correct before creating a CQ: First, RingExample and TriangulationExample are missing the required copyright headers. Second, from the comments given, I would expect IRotatable to use IGeometry as return type instead of the generic type T, or am I missing something there? In this context I think I would also opt to remove the IRotatableInPlace interface. I think it would be sufficient to have the IRotatable alone.
Created attachment 216482 [details] Implements Region and Ring and adds transformation interfaces and their implementations I added the missing copyright headers, enhanced the javadoc comments, deleted the IRotatableInPlace interface and fixed a Polygon.contains(Line) bug. The generic type is used in the transformation interfaces, so that you do not have to cast the return values of the translation, rotation, and scaling methods. I wrote 100% of the code and I have the right to contribute the code to Eclipse under the terms of the EPL.
Comment on attachment 216482 [details] Implements Region and Ring and adds transformation interfaces and their implementations Thanks Matthias, looks fine now. I opened CQ 6545 to keep track of this contribution.
(In reply to comment #47) > Comment on attachment 216482 [details] > Implements Region and Ring and adds transformation interfaces and their > implementations > > Thanks Matthias, looks fine now. I opened CQ 6545 to keep track of this > contribution. CQ is now fully approved, so I applied the patch and pushed changes to origin/master. Thanks again for the contribution Matthias!
Created attachment 217706 [details] Adds a cubic Bezier interpolation method to the PolyBezier class This patch adds a static method to construct a new PolyBezier object from a list of Points so that the resulting PolyBezier passes through all those Points. Additionally, an example application demonstrates the new functionality. I wrote 100% of the code and I have the right to contribute the code to Eclipse under the terms of the EPL.
Thanks again Matthias, I have created CQ 6610 to keep track of this contribution.
Factored out all SWT dependencies into own plug-ins and features, which are optionally included. As soon as CQ 6610 is resolved, we may close this one as well.
(In reply to comment #51) > Factored out all SWT dependencies into own plug-ins and features, which are > optionally included. > > As soon as CQ 6610 is resolved, we may close this one as well. CQ 6610 is now approved and the code has found its way into the origin/master, so we may resolve this as fixed.
