Compute area of path #16859

brunobeltran · 2020-03-20T22:26:34Z

PR Summary

Add method to .Path that can compute the exact (signed) area of the path "fast" (i.e. without any integrations or discretization required) using the simple analytical formula for general Bezier curves.

Required for implementation of "equal area" markers (my current proposal for dealing with #15703).

Roadmap:
#16812 (*) <- #16832 (*) <- (This PR) (*) <- #16891 (MarkerStyle improvements!)

"<-" means "depends on", and "(*)" marks PRs whose implementations are complete and fully ready for review.

PR Checklist

Has Pytest style unit tests
Code is Flake 8 compliant
New features are documented, with examples if plot related
Documentation is sphinx and numpydoc compliant
Added an entry to doc/users/next_whats_new/ if major new feature (follow instructions in README.rst there)
Documented in doc/api/api_changes.rst if API changed in a backward-incompatible way

brunobeltran

Some comments that might be useful to a reviewer.

lib/matplotlib/bezier.py

brunobeltran · 2020-03-31T01:27:57Z

lib/matplotlib/tests/test_bezier.py

+        dr = dB(t).T
+        n = np.array([dr[1], -dr[0]])
+        return (B(t).T @ n) / 2
+    return scipy.integrate.quad(integrand, 0, 1)[0]


Testing our area formula (bezier.BezierSegment.arc_area) is most naturally done by comparing to the naive integral implementation. However, this required me to add scipy to the testing dependencies.

I already test this formula (indirectly) in test_path.test_signed_area_curve and test_path.test_signed_area_unit_rectangle, so if we prefer to not add any dependency on scipy at all, I can simply remove this test.

It was agreed on a call back in June that it's okay to add this Scipy dependency as long as it's just an optional testing dependency.

brunobeltran · 2020-09-01T01:50:45Z

I didn't fully read all the math yet, but I think some of them could be \bm{B} or \vec{B} to differentiate the vectors from the x/y components.

@QuLogic when you get tired of working with the Mac stuff, this is rebased and the math should now render fully (making it marginally easier to review), and I incorporated all of your recommendations.

github-actions · 2023-07-14T02:10:49Z

Since this Pull Request has not been updated in 60 days, it has been marked "inactive." This does not mean that it will be closed, though it may be moved to a "Draft" state. This helps maintainers prioritize their reviewing efforts. You can pick the PR back up anytime - please ping us if you need a review or guidance to move the PR forward! If you do not plan on continuing the work, please let us know so that we can either find someone to take the PR over, or close it.

greglucas · 2024-10-29T22:05:27Z

This was a lot of good work that seems useful to get in. I just rebased this PR and replaced the manual combinatorial function with math.comb now that we are beyond 3.7 support.

timhoffm

Overall, I'm +/-0 on adding this. Do we really need the area? It was pitched for equal-area markers. But I'm not sure on the cost/benefit. As mentioned above there are some potential rabbit holes if we provide this as a public interface. If the primary use would be equal-area markers, I suggest to make this private for now.

timhoffm · 2024-10-30T11:59:02Z

lib/matplotlib/bezier.py

+
+        Notes
+        -----
+        An analytical formula is possible for arbitrary bezier curves.


Is there some external resource we can link to that describes the formula?
While it's reasonable to have it documented here, I'd also anchor to some public description if possible.

I added a link to a publicly accessible course notes on computer graphics. The terminology is slightly different, but the approach looks the same to me.
https://scholarsarchive.byu.edu/facpub/1/

timhoffm · 2024-10-30T12:13:29Z

lib/matplotlib/path.py

+        prev_point = None
+        prev_code = None
+        start_point = None
+        for B, code in self.iter_bezier():


Would it be reasonable to calculate the area on a shifted path, which has it's "center" in the origin? If we are far away from the origin, we add and subtract a lot of long-and-small areas. I can imagine that this could significantly reduce numerical precision.

timhoffm · 2024-10-30T12:14:15Z

lib/matplotlib/tests/test_path.py

    # a point
-    Path([[1, 2]], [Path.MOVETO]),
+    _ExampleCurve(Path([[1, 2]], [Path.MOVETO]), extents=(1., 2., 1., 2.),
+                  area=0.),
 ]


Test a simple non-curved polygon such as a triangle:

Suggested change

]

_ExampleCurve(Path([[1, 1], [2, 1], [1.5, 2]]), extents=(1, 1, 2, 2), area=1/3),

]

Side-remark: Not an expert, but I believe there are more efficient formulas for simple polygons without Bezier segments.

I agree, but looking through this it is all vectorized and over the degree-1 shapes I'm guessing it isn't that expensive. I think this should also be a good way for someone to later come in and add a fast-path for those cases: if CURVE == ...: simple formula. Starting with this seems reasonable to me.

Digression, but this is apparently messing up mypy stubtest which I think is due to the float in here vs int in all the other paths. Changing this to tuple(point) instead satisfies mypy. Seems like typing gone wrong here.

Do we really need to be running mypy over the test suite?

I don't have a strong opinion on mypy on tests. I assume the added value would be that we check for reasonable typing of our interfaces by exercising calls to these interfaces.

greglucas · 2024-10-30T15:13:22Z

@timhoffm, I share some of your concern, but overall feels like this is an improvement worth adding. If someone wants more complex geometry handling they should likely move over to Shapely and GEOS. But this has the work put into it and I could see people not wanting to have to convert a Matplotlib Path over to Shapely and go back and forth if they can avoid it.

For the equal area markers: I think that is one of the most requested scatter marker "features", so I think people definitely would want it.

timhoffm · 2024-10-30T16:10:30Z

@timhoffm, I share some of your concern, but overall feels like this is an improvement worth adding. If someone wants more complex geometry handling they should likely move over to Shapely and GEOS. But this has the work put into it and I could see people not wanting to have to convert a Matplotlib Path over to Shapely and go back and forth if they can avoid it.

We have to be careful what we offer. If we provide a public functionality it should "just work" and we need to document it's scope and limitations. This is more work than just writing it for internal usage.

For example, the current contains() implementation depends on the visibility #23875. I assume this has been implemented for event handling, but is very surprising if a user uses contains as an abstract concept. While this could be labelled a design issue, having it public surfaces the problem to the user.

Similarly, marker paths are typically defined in the vicinity of the origin, so we would not have to care for the possible numeric issue with far-away paths. Also, the precision requirements for reasonable equal-area markers are low. A few percent deviation are tolerable for our use case, but it may not in user applications.
Note also that we could decide to go other routes for equal-area markers. At least for the builtins, we could pre-calculate size-to-area ratios (if need be even through counting covered pixels for a large rendered marker), which would get us 90% the way for equal-area markers without any geometry code.

Generally, geometric calculations are not trivial. I'm quite afraid we provide half-baked solutions, that do not satisfy user needs and will result in follow-up requests to improve on that functionality, which is not our core business.

story645 · 2024-10-31T21:54:56Z

This is more work than just writing it for internal usage.

The ROSES 2024 grant has path transformations as an area of focus.

@greglucas if this issue is part of the work that will help w/ that, could you create a roadmap issue of what should be implemented in Matplotlib to facilitate that work?

greglucas · 2024-11-01T15:31:58Z

@greglucas if this issue is part of the work that will help w/ that, could you create a roadmap issue of what should be implemented in Matplotlib to facilitate that work?

No this isn't related to that. The PR after this (path_length) would be more related, but not directly as that work is all done within Cartopy.

I don't personally have a direct benefit from this at this point in time, so I will just leave the rebased version here in case someone else wants to advocate for it again in the future or use it as a reference, I don't feel strongly enough to advocate for this right now.

brunobeltran force-pushed the path_area branch 7 times, most recently from ee0a30c to 3394535 Compare March 20, 2020 23:53

QuLogic added the status: waiting for other PR label Mar 21, 2020

brunobeltran force-pushed the path_area branch from 365e566 to 82c9210 Compare March 21, 2020 14:06

brunobeltran mentioned this pull request Mar 21, 2020

Correctly compute path extents #16832

Merged

6 tasks

brunobeltran commented Mar 21, 2020

View reviewed changes

lib/matplotlib/bezier.py Outdated Show resolved Hide resolved

lib/matplotlib/bezier.py Outdated Show resolved Hide resolved

lib/matplotlib/bezier.py Outdated Show resolved Hide resolved

lib/matplotlib/bezier.py Show resolved Hide resolved

brunobeltran force-pushed the path_area branch 2 times, most recently from 296baeb to 37d533f Compare March 22, 2020 03:21

brunobeltran mentioned this pull request Mar 22, 2020

Bezier/Path API Cleanup: fix circular import issue #16812

Merged

6 tasks

brunobeltran force-pushed the path_area branch 2 times, most recently from cb14bb2 to aebcbc7 Compare March 23, 2020 19:02

This was referenced Mar 23, 2020

Path length #16888

Open

Path center of mass #16889

Draft

Equal area markers #16891

Draft

brunobeltran force-pushed the path_area branch 4 times, most recently from 4c80f38 to 08e61bc Compare March 30, 2020 21:35

brunobeltran force-pushed the path_area branch 3 times, most recently from 1c30420 to 4a41a2f Compare March 31, 2020 01:23

brunobeltran commented Mar 31, 2020

View reviewed changes

brunobeltran force-pushed the path_area branch 3 times, most recently from 4cf12f3 to 0037abd Compare March 31, 2020 01:40

brunobeltran removed the status: needs rebase label Aug 31, 2020

brunobeltran force-pushed the path_area branch from b683e93 to 87e21f6 Compare September 1, 2020 01:47

brunobeltran force-pushed the path_area branch from 87e21f6 to d22bac1 Compare September 8, 2020 18:30

brunobeltran mentioned this pull request Dec 23, 2020

Fix scatter edgecolor for unfilled points #10008

Closed

6 tasks

brunobeltran added the status: needs review label Jan 6, 2021

jklymak added the status: needs rebase label May 2, 2021

jklymak marked this pull request as draft May 8, 2021 20:07

jklymak removed the status: needs review label May 10, 2021

github-actions bot added the status: inactive Marked by the “Stale” Github Action label Jul 14, 2023

greglucas force-pushed the path_area branch from d22bac1 to 1bb9562 Compare October 29, 2024 22:01

github-actions bot removed the status: needs rebase label Oct 29, 2024

greglucas marked this pull request as ready for review October 29, 2024 22:02

greglucas force-pushed the path_area branch 2 times, most recently from 7054e98 to 40275b8 Compare October 29, 2024 22:22

timhoffm reviewed Oct 30, 2024

View reviewed changes

greglucas force-pushed the path_area branch 3 times, most recently from cdf05fe to df8ea60 Compare October 30, 2024 15:07

greglucas force-pushed the path_area branch 2 times, most recently from 70f327d to a489cbe Compare October 30, 2024 15:55

add function to compute (signed) area of path

eb92405

greglucas force-pushed the path_area branch from a489cbe to eb92405 Compare October 30, 2024 15:58

github-actions bot removed the status: inactive Marked by the “Stale” Github Action label Oct 31, 2024

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Compute area of path #16859

Compute area of path #16859

brunobeltran commented Mar 20, 2020 •

edited

Loading

brunobeltran left a comment

brunobeltran Mar 31, 2020

brunobeltran Aug 31, 2020

brunobeltran commented Sep 1, 2020 •

edited

Loading

github-actions bot commented Jul 14, 2023

greglucas commented Oct 29, 2024

timhoffm left a comment

timhoffm Oct 30, 2024

greglucas Oct 30, 2024

timhoffm Oct 30, 2024

timhoffm Oct 30, 2024

greglucas Oct 30, 2024

greglucas Oct 30, 2024

timhoffm Oct 30, 2024

greglucas commented Oct 30, 2024

timhoffm commented Oct 30, 2024 •

edited

Loading

story645 commented Oct 31, 2024

greglucas commented Nov 1, 2024

	]
	_ExampleCurve(Path([[1, 1], [2, 1], [1.5, 2]]), extents=(1, 1, 2, 2), area=1/3),
	]

Compute area of path #16859

Are you sure you want to change the base?

Compute area of path #16859

Conversation

brunobeltran commented Mar 20, 2020 • edited Loading

PR Summary

PR Checklist

brunobeltran left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

brunobeltran commented Sep 1, 2020 • edited Loading

github-actions bot commented Jul 14, 2023

greglucas commented Oct 29, 2024

timhoffm left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

greglucas commented Oct 30, 2024

timhoffm commented Oct 30, 2024 • edited Loading

story645 commented Oct 31, 2024

greglucas commented Nov 1, 2024

brunobeltran commented Mar 20, 2020 •

edited

Loading

brunobeltran commented Sep 1, 2020 •

edited

Loading

timhoffm commented Oct 30, 2024 •

edited

Loading