Topic: Redraw Polygons on Tileset with no intersecting lines

Currently, in tileset mode, if a polygon is drawn with intersecting lines, the polygon gets tangled and not all the area is filled.

I am wondering if this could be solved by changing the order in which the markers are placed on the map and then using the area size calculation to find the polygon with the largest area.

It's just a guess, but perhaps if the markers are placed in the right order, then a polygon can be created without any intersecting lines. If so, it seems like the angles of the joints might also be at their widest, at least in aggregate. If that turns out to be the case, then perhaps the polygon with no intersecting lines would have largest area of all the combinations. 

If that is true, then what if you loop through all the possible combinations of marker placement orders until the largest area was found? I'm hoping that might deliver a polygon that is completely filled in. 

Does that sound like it would work? If so, is this a feature you guys would be willing to work on? I would imagine a lot of people would like to be able to create normal looking polygons easily.

Anyway, just my 2 cents.

And again, thanks for this amazing asset!

-cousin isaac

Re: Redraw Polygons on Tileset with no intersecting lines

Hello.

The correct triangulation of intersecting lines is very difficult.
One polygon with intersections should be divided into N polygons without intersections.
Sounds easy, but it's not.
There are a lot of special cases and theoretical problems (which will necessarily happen). Even triangulation in such serious products as 3ds Max has many artifacts.
The current version of drawing has been very difficult for us, and I'm sure that we will not be able to improve it.

We do not force you to use the built-in drawing API. If you know another good API that can give you what you want, or you have the experience to create your own implementation, just use it.

Kind Regards,
Infinity Code Team

Re: Redraw Polygons on Tileset with no intersecting lines

Gotcha. But what I am saying is, what if you order the sequence in which the markers are placed so that there simply are no intersecting lines? Imagine 5 markers. They can form a star shape, in which all the lines overlap or they can form a pentagon in which none overlap.

I think it is simply a matter of the order in which the markers are placed. 

Without knowing how many points there will be or where they will be placed, the current method simply draws a line from one to the next. At least that is how it seems when I do it manually.

So, what I am suggesting is that if you take the final set of points and place them on the map in various orders, calculating the area each time (which  the CalcArea script does already) the shape with the biggest area might just be the one that has no intersecting lines. It’s just a theory- but I think it makes sense because the angles of the intersections will likely be wider in aggregate when there are no intersections.

Worth a try anyway, no?

Re: Redraw Polygons on Tileset with no intersecting lines

This will not work.
Look at the screenshot.
These two figures have the same points, but different views and different areas.

Post's attachments

Attachment icon img1.png 25.52 kb, 8 downloads since 2017-06-24 

Kind Regards,
Infinity Code Team

Re: Redraw Polygons on Tileset with no intersecting lines

I see. For my purposes that would actually be good enough. It would pick the one with biggest area and it would still be a hell of a lot better than a tangled mess with some areas filled in and some without. Would be interesting to find out if other users have this need or not.

6 (edited by cousinisaac 2017-07-10 23:20:54)

Re: Redraw Polygons on Tileset with no intersecting lines

Update: I have been playing around with this and researching solutions. Again, my feature request is just to be able to draw polygons that don't look messed up because of crossed edges.

To this end,  I tried using recursion / brute force to find the permutations of the order of markers which produce a polygon with no crossed lines, but it is too time consuming for polygons with more than just a few markers.  However there are permutation classes available that don't use brute force out there such as the one described here: https://www.codeproject.com/Articles/26 … -using-C-G  which could prove faster.

Another thought is that this can also be considered a Traveling Salesman Problem-  (see https://en.wikipedia.org/wiki/Travellin … an_problem )  and there are a number of solutions to that out there as well which should also produce a polygon with no intersecting lines as far as I can tell.

EDIT 1:
Actually, what would really do the trick is a Graham Scan, but alas it might be slow....
https://en.wikipedia.org/wiki/Graham_scan   

EDIT 2: Hmm.. it just might work... see this example: http://www.habrador.com/tutorials/linea … nvex-hull/