Hsiang, T., Arkin, E., Bender, M., Fekete, S., Mitchell, J.: Algorithms for Rapidly Dispersing Robot Swarms in Unknown Environments. Hoffmann, F., Icking, C., Klein, R., Kriegel, K.: The Polygon Exploration Problem. The Electronic Journal of Combinatorics (2009) Computational Geometry 43(2), 148–168 (2010)įriedman, E.: Packing Unit Squares in Squares: A Survey and New Results. Journal of Combinatorial Optimization, 393–402 (2010)įekete, S.P., Schmidt, C.: Polygon Exploration with Time-Discrete Vision. 153–156 (2010)įekete, S.P., Mitchell, J., Schmidt, C.: Minimum Covering with Travel Cost. In: Proceedings of the 25th European Workshop on Computational Geometry, pp. Springer, Heidelberg (2011)įekete, S.P., Kamphans, T., Kröller, A., Schmidt, C.: Robot Swarms for Exploration and Triangulation of Unknown Environments. In: Goldberg, L.A., Jansen, K., Ravi, R., Rolim, J.D.P. Springer, Heidelberg (2008)įekete, S.P., Kamphans, T., Kröller, A., Mitchell, J.S.B., Schmidt, C.: Exploring and Triangulating a Region by a Swarm of Robots. Computer Science Review 5(1), 57–68 (2011)Įfrat, A., Fekete, S.P., Gaddehosur, P.R., Mitchell, J.S.B., Polishchuk, V., Suomela, J.: Improved Approximation Algorithms for Relay Placement. Springer, Heidelberg (2008)ĭegener, B., Fekete, S., Kempkes, B., Meyer auf der Heide, F.: A Survey on Relay Placement with Runtime and Approximation Guarantees.
IEEE/ACM Transactions on Networking (TON) 18(1), 216–228 (2010)īrunner, J., Mihalák, M., Suri, S., Vicari, E., Widmayer, P.: Simple Robots in Polygonal Environments: A Hierarchy. Computing in Euclidean Geometry 1, 23–90 (1992)īredin, J., Demaine, E., Hajiaghayi, M., Rus, D.: Deploying Sensor Networks with Guaranteed Fault Tolerance. Based on optimal solutions for small squares, we establish a competitive factor of \(\frac\approx 0.3849\), and argue that this is asymptotically optimal.īern, M., Eppstein, D.: Mesh Generation and Optimal Triangulation. In this paper, we study the OMRTP for polygons without such bottlenecks: polyominoes, i.e., orthogonal polygons with integer edge lengths. Both problems have been studied before, with a competitive factor of 3 for the OMRTP in general polygons, and an unbounded competitive factor for the OMATP the latter holds for polygons with very narrow corridors. For an unknown polygonal region P, the Online Minimum Relay Triangulation Problem (OMRTP) asks for an exploration strategy that maintains a triangulation with limited edge length and achieves a minimum number of robots (relays), such that the triangulation covers P for a given number n of robots, the Online Maximum Area Triangulation Problem (OMATP) asks for maximizing the triangulated area. At the end of this (after I get further in my project and make sure this battle tested) I will put up a nice happy Poly2Tri repo for Unity that is easy to integrate into projects and can be called with 1 line from C# and JS.We consider the problem of exploring and triangulating a region with a swarm of robots with limited vision and communication range.
#Dmesh triangulator how to#
Yes, there is room for improvement, but this is good enough for now.Īs someone who spends most of his time in JS, there was a good learning curve here of how to get this all set up and working. Then I factor in that point data as steiner points to get this as the final! This leaves me with this (points being shown with spheres) I am currently generating a grid of points based on the bounds of the mesh, then I check if they are inside or outside the shape, and delete the ones that are outside. So I scratched that and decided to use steiner points as suggested, so now the task was to figure out where to place the steiner points.Ī good visual example of how steiner points work is with this web demo it does take about 5 seconds to work on the desktop, so that made me think its probably a bit overkill for a mobile project. They were however, added in the C version of poly2tri within the past year, dubbed the Delaunay Terminator Īnother side note, Adobe After Effects puppet tool has a really boss triangulation algorithm.I have no idea but would guess it uses one of these algorithms or something similar. These are awesome algorithms, but are not included in any of the c# poly2tri implementations out there, and I am also not sure if mobile can hang with them.
They are kinda fascinating, if you wanna read more. It turns out, Delaunay Triangulation by itself is a good start, but the link to the research paper I posted before is for Delaunay REFINEMENT algorithms, which take place after the original Delaunay triangulation and are very iterative, going through and cleaning up non ideal triangles and so forth. Thanks I know you are all on the edge of your seat for this, so here it goes.
0 kommentar(er)
