1

I'm currently implememting a really general trapezoid map https://ibb.co/THsqnYz , and have to resolve the following occasions:

  • vertex coincidence
  • edge coincidence (say edge from (0,0) to (0,1) and edge from (0,-1) to (0,2), or (0,0) to (0,1))
  • edge intersection
  • zero length edge

I had googled and read many PDFs but none of them explained this in DETAIL.

Could someone teach me how to do? (external materials are also OK)

Ripi2
  • 7,031
  • 1
  • 17
  • 33
Nekomiya Kasane
  • 13
  • 5
  • What have you achieved so far? Do you know how to calculate two edges intersection? – Ripi2 Jul 17 '23 at 19:43
  • @Ripi2 Yes. I have implemented a version which allows to append non-intersecting segements. I used a vector to cache 4 neighbor trapezoids of a trapezoid and do the update for each insertion. It's quite easy for non-crossing segments. – Nekomiya Kasane Jul 18 '23 at 05:49
  • See [segments intersection](https://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect) – Ripi2 Jul 18 '23 at 18:08
  • @Ripi2 I know how to calculate the intersection, but what I don't know is how to update the trapezoid map when encounter intersections and coincidences. – Nekomiya Kasane Jul 19 '23 at 07:28
  • At this point I need an image to see the issue. Can you post one? – Ripi2 Jul 19 '23 at 17:37
  • Sure. https://ibb.co/Qpmtmgb, https://ibb.co/THsqnYz. I took the simplest intersecting occasion as the example (right column) – Nekomiya Kasane Jul 20 '23 at 01:46
  • Moreover, since the trapezoid map is dependent on the insertion order of vertices and edges, handling insertion seems annoying since new vertices will be introduced. – Nekomiya Kasane Jul 20 '23 at 01:49
  • This [link to pdf](https://www.cs.umd.edu/class/fall2021/cmsc754/Lects/lect08-trap-map.pdf) and this [link to pdf](https://www.cs.umd.edu/class/spring2020/cmsc754/Lects/lect09-pt-loc.pdf) will give enough info & samples – Ripi2 Jul 20 '23 at 19:17
  • Notice that if you allow intersecting edges then the whole idea of space partition gives away. what you can do is **1)** Find all intersections, and insert new vertices. **2)** Overlapped edges with no other segments in between can be treated by getting the 4 vertices, unless they are repeated. **3)** Segments in between require inserting vertices. If you need the original data you may keep a track of the edges modified or inserted. – Ripi2 Jul 20 '23 at 19:24
  • @Ripi2 Thank you for the helpful comments! Furtherly, I have some detailed questions: **1)** If I find the intersections first, I need to implement a segment set intersection algorithm, so I wonder is there any possible method to allow finding intersections while adding segments (and maintain the trapezoid map at the same time). **2)** what should I do if the overlapped edges are repeated? **3)** As for "Segments in between require inserting vertices", could you please make it clearer on how to do in detail? I'm not sure about this. – Nekomiya Kasane Jul 24 '23 at 02:51
  • When you add a segment you must check for intersections with all previous segments. This is slow, but can be some optimized. If it intersects you must split both segments and add the intersection point, and change the map/tree accordingly. Overlapped edges are like intersections, split segments and add the endpoint inner to the oher segment, perhaps two insertions. Repeated edges must be discarded (but you can store its original data, so as to say "this point lies at right of segments XX and YY) – Ripi2 Jul 24 '23 at 17:51
  • Perhaps you want to first check all intersections (search algorithms like "Sweep Line") and later begin with the map. – Ripi2 Jul 24 '23 at 17:51

1 Answers1

1

Vertex Coincidence: Vertex coincidence occurs when two vertices have the same coordinates. To handle this case, you can add a check in your data structure to prevent duplicate vertices from being created. When adding a new vertex, compare its coordinates with existing vertices, and if there is a match, use the existing vertex instead of creating a new one.

Edge Coincidence: Edge coincidence occurs when two edges have the same start and end vertices or the same coordinates. To handle this case, you can implement a data structure to store edges uniquely based on their start and end vertices. When adding a new edge, check if an edge with the same start and end vertices already exists. If it does, you can choose to update the existing edge or ignore the new edge.

Edge Intersection: Edge intersection occurs when two edges cross each other. This is a more complex case and requires advanced algorithms like line intersection algorithms or sweep line algorithms. You'll need to keep track of the edges' orientations and intersections to handle this case properly. The Bentley-Ottmann algorithm is commonly used to handle edge intersections efficiently in computational geometry.

Zero-Length Edge: A zero-length edge occurs when the start and end vertices of an edge coincide. This case can lead to degenerate polygons or invalid data. To handle this, you can add a check when adding edges to ensure that their start and end vertices are not the same.

Here are some resources:

"Computational Geometry: Algorithms and Applications" by Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars. This book covers computational geometry concepts, including trapezoid maps and algorithms for handling edge intersections.

"A Simple Trapezoid Map Implementation" by Steven Fortune. This paper provides a detailed explanation of a trapezoid map implementation using the sweep line algorithm.

"Trapezoidal Map" Wikipedia page: The Wikipedia page on trapezoidal maps provides a good overview and references to further resources.

Additional Links:

Wakil Ahmed
  • 1,053
  • 1
  • 8
  • 16