Combining two polygons into one polygon

Questions about the LÖVE API, installing LÖVE and other support related questions go here.
Forum rules
Before you make a thread asking for help, read this.
Post Reply
User avatar
darkfrei
Party member
Posts: 1168
Joined: Sat Feb 08, 2020 11:09 pm

Combining two polygons into one polygon

Post by darkfrei »

Hi all!

I've tried to find a good solution how to union any (except self-crossing) two polygons, but I cannot find an easy and safe solution.
Here are some merge problems by by two polygons:
polygon-problems.png
polygon-problems.png (47.62 KiB) Viewed 3439 times
Some of them are simple, but it's very hard to solve them all, I cannot make elegant solution at all. :x

Do you have some experience by polygon merging?
:awesome: in Lua we Löve
:awesome: Platformer Guide
:awesome: freebies
pkhead
Prole
Posts: 2
Joined: Fri Nov 11, 2022 11:49 pm

Re: Combining two polygons into one polygon

Post by pkhead »

I found this Wikipedia page: https://en.wikipedia.org/wiki/Boolean_o ... n_polygons

Seems useful. Other than that I don't know much about this.
User avatar
pgimeno
Party member
Posts: 3541
Joined: Sun Oct 18, 2015 2:58 pm

Re: Combining two polygons into one polygon

Post by pgimeno »

Also this library: https://github.com/AngusJohnson/Clipper2 (for C++, Delphi and Csharp)
User avatar
darkfrei
Party member
Posts: 1168
Joined: Sat Feb 08, 2020 11:09 pm

Re: Combining two polygons into one polygon

Post by darkfrei »

But how Löve can accept polygons with holes?
:awesome: in Lua we Löve
:awesome: Platformer Guide
:awesome: freebies
User avatar
ivan
Party member
Posts: 1911
Joined: Fri Mar 07, 2008 1:39 pm
Contact:

Re: Combining two polygons into one polygon

Post by ivan »

I cannot find an easy and safe solution
It is not "easy" at all.
But how Löve can accept polygons with holes?
It doesn't.

These sort of operations are non-trivial and require complex algorithms involving polygon clipping and triangulation.
In general, these sorts of operations are slow and rarely performed in real-time.
In addition to Clipper there is also the Poly2Tri library
User avatar
darkfrei
Party member
Posts: 1168
Joined: Sat Feb 08, 2020 11:09 pm

Re: Combining two polygons into one polygon

Post by darkfrei »

So the result of the function must be a special structure with array of polygons as areas _and_ array of polygons as outline?
First draw all polygons (triangulated for concave) and than render all outlines.
:awesome: in Lua we Löve
:awesome: Platformer Guide
:awesome: freebies
User avatar
ivan
Party member
Posts: 1911
Joined: Fri Mar 07, 2008 1:39 pm
Contact:

Re: Combining two polygons into one polygon

Post by ivan »

First and foremost you must run your complex polygon through poly clipper to ensure you are working exclusively with simple polygons.
You may need to check or modify the windings of your polygons to determine where the holes are.
Next, you need to triangulate those simple polygons.
The actual structures depend on the method involved.
For example, poly2tri uses a scanline algorithm that automatically handles polygons with holes and will output a list of triangles.
On the other hand love.triangulate uses an ear clipping algorithm which is slower and does not work with holes. The holes must be "cut" ahead of time using a special hole cutting algorithm that outputs a simple polygon with two or more shared edges:
Image
If you want to draw the outline of a polygon, you are talking about polygon offsetting:
https://2dengine.com/?p=polygons#Polygon_offsetting
A while ago I wrote an SVG parser for love2d so yes it is possible to get something working.
The main problem is making sure that your code is robust and optimized which is very difficult and requires a lot of knowledge.
In short, it is possible but it is a big and complex project and not worth running the Lua code in real-time.
It may be better to just build Lua bindings for clipper and poly2tri.
On a side note, HTML5 canvas can handle both clipping and triangulation without the need for third party libraries.
User avatar
Bigfoot71
Party member
Posts: 287
Joined: Fri Mar 11, 2022 11:07 am

Re: Combining two polygons into one polygon

Post by Bigfoot71 »

If it helps I just published a library in pure Lua for boolean operations on polygon taken from another JS library. I just performed all the tests that passed so I can share it, here it is: https://github.com/Bigfoot71/2d-polygon-boolean-lua

On the other hand I have not tested what it gives on complex polygons, indeed it will surely be necessary to find a reliable way to detect and correct it but you can try anyway.
My avatar code for the curious :D V1, V2, V3.
Post Reply

Who is online

Users browsing this forum: No registered users and 17 guests