Polygone break ... not broken ?

[Lecrapouille]

Hi! Last time I made a portage of your road envelope in C++ and SFML (I'm not yet sharing because broken. It almost working but I've some bugs that, by missing time not been fully investigated). When implementing the C++ I noticed an issue in my code concerning the break polygon function. I'm not a JS dev, so I'm not sure to understand how memory is managed, I'm thinking as a C++ dev maybe.

https://github.com/gniziemazity/virtual-world/blob/b9482cf3ec387c9d46b0b7c7a5976e85e91d0f72/4.%20Roads/js/primitives/polygon.js#L42-L65

• 1st question: poly1.segments how segments are internally implemented? Linked list or array?
• 1st issue: const segs1 = poly1.segments; is segs1 a pointer on poly1.segments or a full copy ? I guess this is a pointer since there is no poly1.segments = segs1 at the end of the function. Why const if it is spliced later in the function?
• 2nd issue: for (let i = 0; i < segs1.length; i++) should be iterated maybe backward but using poly1.segments and segs a copy of the original array, because when splicing segs1 you add one element in the array and you iterating on the new size. Let's suppose this adds every time a new element, you end with an infinite loop (not your case, but my case). I guess we do not need to iterate on newly split segments for getIntersection, right? I dunno why my C++ code is buggy with your code or my changes. I think I also have different behavior from you when I iterate on an "L" road: the intersection of circles when offset == 0 or 1.
• just an idea: I know Polygon is a single-usage instance, and points are used only for drawing but when splitting segments, you could update this.points to match segments in the case the polygon is still used for later usage.

[gniziemazity]

1. A structure with 2 points (p1 and p2). In C++ you can consider these pointers to points from the graph itself (an array holds all the points).
2. JavaScript doesn't have pointers, but segs1 is indeed, a reference here. Changing it's properties will affect poly1.segments. Const, in JavaScript means something that you don't want (can't) reassign to something else. Not that you can't change it's properties. Weird, I know...
3. Hard to wrap my mind around this now, but... I think you are right, now we consider the added segment again... I suspect the reason why my code isn't breaking is that that 'reconsidered' segment is outside... and in your case, it might be inside, causing some kind of infinite loop (?) no idea... just a hunch, that it may depend on the order of the points in the polygon (or the segments).
4. You are right, that would make for better code. I took few shortcuts here and there... so that if something wasn't needed / causing trouble, I didn't implement it... So that tutorial isn't too long... Still ended up long :-D

[Lecrapouille]

Tanks you for your answer ! Ok for the JS const not working like C++const ! If I remember well there is also something weird with Julia lang :) I'll test your code and log and compare with me, this will make me practice a little JS ;)

[Lecrapouille]

EDIT: I had time to investigate carefully. My code has still bugs (missing kept segments, potential infinite loop, or missing segments detection depending if you use float or double), https://github.com/Lecrapouille/BacASable/tree/master/GameEngine/SFML/Roads

I could just investigate today:

• JS as C++ have the same behavior: the seg1 and seg2 array length will increase during the iteration of for-loops.
• I solved my issue, iterating on original segments and inserting new segments in the copied array (before loops). EDIT: this does not work: split segments shall be added in the loop because, effectively, they shall be tested against other segments. I had missing split segments. Your algo is correct.
• EDIT: the getIntersection(A, B, C, D) has some issue on border case: for example segment ((0,0), (10,0)) and segment ((10,0), (20,0)) intersect at (10,0) but the function does not find it (I did not test but saw with C++ code and checked manually). I used https://cp-algorithms.com/geometry/lines-intersection.html and https://cp-algorithms.com/geometry/segments-intersection.html
• I don't know why the C++ insert() does not work like your splice(), in my case. I simply push_back() segments since we do not need them ordered and pushing back avoid displacing the other elements. EDIT: C++ insert() works well. The reason why I added an infinite loop is that I removed the && int.offset != 1 && int.offset != 0) { and split segments have a common intersection, so the getIntersection() was always true, and a new segment was added at each iteration and since the for-loops are iterating on a growing array they never stop. BUT this method does not work well if two roads intersect perpendicularly on their semicircles: vertices on circles on both roads are superposed and the offset check make them discarded.
• Anyway, a more complex algorithm could be used: https://www.youtube.com/watch?v=qkhUNzCGDt0 and https://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm O((n+k)log(n)) but I guess for small number of segments naive O(n^2) is fine. EDIT: I will test this algo In this project https://github.com/valenpe7/bentley-ottmann you will see the guy use your method and the algorithm has conditions to work correctly.
• Will you add traffic jam without ML like https://github.com/volkhin/RoadTrafficSimulator or http://lo-th.github.io/root/traffic/ https://github.com/lo-th/root/tree/gh-pages/traffic