Optimizing Polygon Intersections with Subdivide(findenergy.com)

Optimizing Polygon Intersections with Subdivide

https://findenergy.com/optimizing-polygon-intersections-with-subdivide/

6 comments

I've only skimmed the article so their solution seems like a totally valid way to do polygon intersections for their purposes, but for people that want to do this in a more rigorous way, there's something called the Vatti clipping algorithm which does boolean operations on arbitrary 2D polygons (in polynomial time).

To find polygon intersections, one can do a boolean "intersect" operation to see if the resulting operation has any results. If so, the polygons intersect. If not, then they're disjoint.

Angus Johnson has created ClipperLib [1] which implements Vatti's algorithm and is available in a variety of languages, including C++, with ports to Javascript by others [2].

CGAL [3] can do polygon clipping but, from my own experience, ClipperLib is about 400 times faster.

[0] https://en.wikipedia.org/wiki/Vatti_clipping_algorithm

[1] http://www.angusj.com/clipper2/Docs/Overview.htm

[2] https://github.com/junmer/clipper-lib

[3] https://www.cgal.org/

vonadz4 anni fa

Thanks for posting this! I'll look into testing ClipperLib as well. If it's 400x faster, that would be great.

mistrial94 anni fa

What is "Find Energy" ?.. is this like far-away smart people digging through your garage to "find" tools ?

vonadz4 anni fa

> What is "Find Energy" ?

We take a bunch of data relating to electricity, natural gas, and solar, make it understandable, then compile it all together on our website so people can get a good idea of the national/local energy landscape.

> is this like far-away smart people digging through your garage to "find" tools ?

Although some would consider us "far-away smart people" (depending on their geographic location), rest assured that we're definitely not digging through your garage for anything.

mistrial94 anni fa

What is the public benefit here for open data? Where is your code/pipeline published? What is being done with this data? Who is benefiting and/or paying for this "research" on critical USA infrastructure?

edit it seems that 3 months ago, we both commented on this https://news.ycombinator.com/item?id=31555938

vonadz4 anni fa

> What is the public benefit here for open data?

We believe that everyone benefits from knowing more about how, where, and by whom electricity is generated. My personal opinion is that there's a lot of BS in the electricity industry and making the actual data available is the best way to clear the stink.

> Where is your code/pipeline published?

Our code/pipeline isn't published anywhere. https://findenergy.com/data/ gives a general idea of where all of the data is coming from (spoiler, it's all from the US government). I'm currently working on an internal tool that'll help us map data from source to where/how it's used on our site, but it's a pretty big undertaking and might take a while. In the mean time, we answer any and all specific questions that are submitted through the website (https://findenergy.com/contact/).

> What is being done with this data?

Currently it's just being shown on the website. We also have reporters, students, and companies reaching out to us asking to use the data for articles, research, and reports respectively.

> Who is benefiting and/or paying for this "research" on critical USA infrastructure?

We're hoping consumers are benefiting. No one is paying us for this work. We're just a couple of guys that are passionate about this data, think it should be available to consumers, and are trying to figure out how to make carrying out that service sustainable financially.

> edit it seems that 3 months ago, we both commented on this https://news.ycombinator.com/item?id=31555938

Yup! Your comment on marketed rates vs actual rates is very true. We calculate our rates by dividing the company's revenues by kWhs sold, so it should technically be closer to the actual rate.