From 81bce1d38758d3a7d000b3fdf0b1821621885782 Mon Sep 17 00:00:00 2001 From: Charlotte Pabst Date: Wed, 17 Jan 2024 21:18:38 +0100 Subject: --- .gitignore | 1 + 1.svg | 81 ++++++ Cargo.lock | 137 ++++++++++ Cargo.toml | 13 + Utah teapot (solid) - 852078.zip | Bin 0 -> 917444 bytes src/main.rs | 545 +++++++++++++++++++++++++++++++++++++++ utahteapot/LICENSE.txt | 1 + utahteapot/README.txt | 1 + utahteapot/files/utahteapot.stl | Bin 0 -> 471984 bytes utahteapot/images/teapot_stl.jpg | Bin 0 -> 194795 bytes utahteapot/images/utahteapot.png | Bin 0 -> 249715 bytes x.dot | 40 +++ x.svg | 227 ++++++++++++++++ 13 files changed, 1046 insertions(+) create mode 100644 .gitignore create mode 100644 1.svg create mode 100644 Cargo.lock create mode 100644 Cargo.toml create mode 100644 Utah teapot (solid) - 852078.zip create mode 100644 src/main.rs create mode 100644 utahteapot/LICENSE.txt create mode 100644 utahteapot/README.txt create mode 100644 utahteapot/files/utahteapot.stl create mode 100644 utahteapot/images/teapot_stl.jpg create mode 100644 utahteapot/images/utahteapot.png create mode 100644 x.dot create mode 100644 x.svg diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..ea8c4bf --- /dev/null +++ b/.gitignore @@ -0,0 +1 @@ +/target diff --git a/1.svg b/1.svg new file mode 100644 index 0000000..5ca96b9 --- /dev/null +++ b/1.svg @@ -0,0 +1,81 @@ + + + + + + +DCEL + + + +0 + +0 + + + +edge_0 + + + + +0->edge_0 + +0 + + + +1 + +far + + + +edge_1 + + + + +1->edge_1 + +1 + + + +edge_0->1 + + + + + +edge_0->edge_1 + + + +twin + + + +edge_0->edge_1 + + +next + + + +edge_1->0 + + + + + +edge_1->edge_0 + + +next + + + diff --git a/Cargo.lock b/Cargo.lock new file mode 100644 index 0000000..3ca3525 --- /dev/null +++ b/Cargo.lock @@ -0,0 +1,137 @@ +# This file is automatically @generated by Cargo. +# It is not intended for manual editing. +version = 3 + +[[package]] +name = "autocfg" +version = "1.1.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "d468802bab17cbc0cc575e9b053f41e72aa36bfa6b7f55e3529ffa43161b97fa" + +[[package]] +name = "byteorder" +version = "1.5.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "1fd0f2584146f6f2ef48085050886acf353beff7305ebd1ae69500e27c67f64b" + +[[package]] +name = "cfg-if" +version = "1.0.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "baf1de4339761588bc0619e3cbc0120ee582ebb74b53b4efbf79117bd2da40fd" + +[[package]] +name = "dcel" +version = "0.1.0" +dependencies = [ + "either", + "ghost-cell", + "rand", + "stl_io", + "typed-arena", +] + +[[package]] +name = "either" +version = "1.9.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "a26ae43d7bcc3b814de94796a5e736d4029efb0ee900c12e2d54c993ad1a1e07" + +[[package]] +name = "float-cmp" +version = "0.9.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "98de4bbd547a563b716d8dfa9aad1cb19bfab00f4fa09a6a4ed21dbcf44ce9c4" +dependencies = [ + "num-traits", +] + +[[package]] +name = "getrandom" +version = "0.2.12" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "190092ea657667030ac6a35e305e62fc4dd69fd98ac98631e5d3a2b1575a12b5" +dependencies = [ + "cfg-if", + "libc", + "wasi", +] + +[[package]] +name = "ghost-cell" +version = "0.2.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "a5fdd3f2182d5fad2c97a25af8992c30e844a775f8fc7339dae5328377d164e6" + +[[package]] +name = "libc" +version = "0.2.152" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "13e3bf6590cbc649f4d1a3eefc9d5d6eb746f5200ffb04e5e142700b8faa56e7" + +[[package]] +name = "num-traits" +version = "0.2.17" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "39e3200413f237f41ab11ad6d161bc7239c84dcb631773ccd7de3dfe4b5c267c" +dependencies = [ + "autocfg", +] + +[[package]] +name = "ppv-lite86" +version = "0.2.17" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "5b40af805b3121feab8a3c29f04d8ad262fa8e0561883e7653e024ae4479e6de" + +[[package]] +name = "rand" +version = "0.8.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "34af8d1a0e25924bc5b7c43c079c942339d8f0a8b57c39049bef581b46327404" +dependencies = [ + "libc", + "rand_chacha", + "rand_core", +] + +[[package]] +name = "rand_chacha" +version = "0.3.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "e6c10a63a0fa32252be49d21e7709d4d4baf8d231c2dbce1eaa8141b9b127d88" +dependencies = [ + "ppv-lite86", + "rand_core", +] + +[[package]] +name = "rand_core" +version = "0.6.4" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "ec0be4795e2f6a28069bec0b5ff3e2ac9bafc99e6a9a7dc3547996c5c816922c" +dependencies = [ + "getrandom", +] + +[[package]] +name = "stl_io" +version = "0.7.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "d520eb03e632e666ac32f3c0cf018ac6dcd535ab0be1420937e2d896f44f7cf7" +dependencies = [ + "byteorder", + "float-cmp", +] + +[[package]] +name = "typed-arena" +version = "2.0.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "6af6ae20167a9ece4bcb41af5b80f8a1f1df981f6391189ce00fd257af04126a" + +[[package]] +name = "wasi" +version = "0.11.0+wasi-snapshot-preview1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "9c8d87e72b64a3b4db28d11ce29237c246188f4f51057d65a7eab63b7987e423" diff --git a/Cargo.toml b/Cargo.toml new file mode 100644 index 0000000..cdeda6f --- /dev/null +++ b/Cargo.toml @@ -0,0 +1,13 @@ +[package] +name = "dcel" +version = "0.1.0" +edition = "2021" + +# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html + +[dependencies] +either = "1.9.0" +ghost-cell = "0.2.3" +rand = "0.8.5" +stl_io = "0.7.0" +typed-arena = "2.0.2" diff --git a/Utah teapot (solid) - 852078.zip b/Utah teapot (solid) - 852078.zip new file mode 100644 index 0000000..ebf89fb Binary files /dev/null and b/Utah teapot (solid) - 852078.zip differ diff --git a/src/main.rs b/src/main.rs new file mode 100644 index 0000000..960c334 --- /dev/null +++ b/src/main.rs @@ -0,0 +1,545 @@ +#![allow(unused)] +// the cell! macro will expand to complex types but makes things easier to read for humans +// unlike type definitions, a macro can capture the 'brand and 'arena lifetimes from the scope +#![allow(clippy::type_complexity)] + +use either::Either::{self, *}; +use ghost_cell::{GhostBorrow, GhostCell, GhostToken}; +use typed_arena::Arena; + +type Id = Option; + +// trait for a kind of topological element (i.e. Vertex, HalfEdge, Face) +trait Kind { + type Init; + + fn new(id: usize, init: Self::Init) -> Self; + + fn is_alive(&self) -> bool { + self.get_id().is_some() + } + + fn get_id(&self) -> Id; + fn clear(&mut self); +} + +macro_rules! cell_t { + ($T:ty) => { + &'arena GhostCell<'brand, $T> + } +} + +macro_rules! cell { + ($T:ident) => { + &'arena GhostCell<'brand, $T<'brand, 'arena, V>> + }; +} + +macro_rules! impl_kind { + ($T:ident, $init_name:ident: $init_ty:ty $(, $($init_field:ident : $init_expr:tt),* )? $(; $($fields:ident),*)?) => { + impl<'brand, 'arena, V> Kind for $T<'brand, 'arena, V> { + type Init = $init_ty; + + fn get_id(&self) -> Id { + self.id + } + + fn new(id: usize, $init_name: $init_ty) -> Self { + Self { + id: Some(id), + $($($init_field: $init_expr,)*)? + $($($fields: Default::default(),)*)? + } + } + + fn clear(&mut self) { + self.id = Default::default(); + #[cfg(debug_assertions)] + { $($(self.$fields = Default::default();)*)? } + } + } + + impl<'brand, 'arena, V: Default> PartialEq for $T<'brand, 'arena, V> { + fn eq(&self, other: &Self) -> bool { + self.get_id() == other.get_id() + } + } + impl<'brand, 'arena, V: Default> Eq for $T<'brand, 'arena, V> {} + }; +} + +use std::fmt; + +trait DcelDebug<'brand> { + fn fmt( + &self, + long: bool, + token: &GhostToken<'brand>, + f: &mut fmt::Formatter<'_>, + ) -> Result<(), fmt::Error>; +} + +macro_rules! impl_debug { + ($T:ty) => { + impl<'brand> DcelDebug<'brand> for $T { + fn fmt( + &self, + long: bool, + token: &GhostToken<'brand>, + f: &mut fmt::Formatter<'_>, + ) -> Result<(), fmt::Error> { + fmt::Debug::fmt(self, f)?; + writeln!(f, "") + } + } + }; +} + +impl<'brand, T: DcelDebug<'brand>> DcelDebug<'brand> for Option { + fn fmt( + &self, + long: bool, + token: &GhostToken<'brand>, + f: &mut fmt::Formatter<'_>, + ) -> Result<(), fmt::Error> { + match self { + None => write!(f, "None"), + Some(x) => DcelDebug::fmt(x, long, token, f), + } + } +} + +macro_rules! impl_kind_debug { + ($T:ident $(, $($fields:ident),*)?) => { + impl<'brand, 'arena, V> DcelDebug<'brand> for &'arena GhostCell<'brand, $T<'brand, 'arena, V>> where V: DcelDebug<'brand> { + fn fmt( + &self, + long: bool, + token: &GhostToken<'brand>, + f: &mut fmt::Formatter<'_>, + ) -> Result<(), fmt::Error> { + writeln!(f, "{} {:?}", stringify!($T), self.borrow(token).id)?; + + if long { + $($( + write!(f, "\t{} = ", stringify!($fields))?; + DcelDebug::fmt(&self.borrow(token).$fields, false, token, f)?; + )*)? + } + + Ok(()) + } + } + }; +} + +// responsible for allocation of a certain Kind +struct Container<'brand, 'arena, T: Kind> { + next_id: usize, + arena: &'arena Arena, + elements: Vec, + freelist: Vec, +} + +impl<'brand, 'arena, T: Kind> Container<'brand, 'arena, T> { + fn new(arena: &'arena Arena) -> Self { + Self { + next_id: 0, + arena, + elements: Vec::new(), + freelist: Vec::new(), + } + } + + fn alloc( + &mut self, + token: &mut GhostToken<'brand>, + init: T::Init, /*f: impl FnOnce(Id) -> T*/ + ) -> cell_t!(T) { + let id = self.next_id; + self.next_id += 1; + + let t = Kind::new(id, init); + + if let Some(cell) = self.freelist.pop() { + *cell.borrow_mut(token) = t; + cell + } else { + let cell = GhostCell::from_mut(self.arena.alloc(t)); + self.elements.push(cell); + cell + } + } + + fn free(&mut self, token: &mut GhostToken<'brand>, cell: cell_t!(T)) { + debug_assert!(!cell.borrow(token).is_alive(), "double free"); + cell.borrow_mut(token).clear(); + self.freelist.push(cell); + } +} + +#[derive(Default)] +struct DcelAllocator<'brand, 'arena, V> { + edge: Arena>, + vertex: Arena>, + face: Arena>, +} + +struct Dcel<'brand, 'arena, V: Default> { + token: GhostToken<'brand>, + half_edges: Container<'brand, 'arena, HalfEdge<'brand, 'arena, V>>, + vertices: Container<'brand, 'arena, Vertex<'brand, 'arena, V>>, + faces: Container<'brand, 'arena, Face<'brand, 'arena, V>>, +} + +struct Vertex<'brand, 'arena, V> { + id: Id, + data: V, + outgoing: Option, +} +//type VertexRef<'brand, 'arena, V> = &'arena GhostCell<'brand, Vertex<'brand, 'arena, V>>; +impl_kind!(Vertex, init: V, data: init; outgoing); +impl_kind_debug!(Vertex, data, outgoing); + +struct HalfEdge<'brand, 'arena, V> { + id: Id, + next: Option, + origin: Option, + twin: Option, + face: Option, + prev: Option, +} +//type HalfEdgeRef<'brand, 'arena, V> = &'arena GhostCell<'brand, HalfEdge<'brand, 'arena, V>>; +impl_kind!(HalfEdge, init: (); origin, twin, face, next, prev); +impl_kind_debug!(HalfEdge, origin, twin, face, next, prev); + +/* +struct FaceL<'brand, 'arena, V> { + id: Id, + outer: Vec, + inner: Vec, + solid: Option, +} + +struct Solid<'brand, 'arena, V> { + id: Id, + faces: Vec, + half_edges: Vec, +}*/ + +struct Face<'brand, 'arena, V> { + id: Id, + outer: Vec, + inner: Vec, +} +//type FaceRef<'brand, 'arena, V> = &'arena GhostCell<'brand, Face<'brand, 'arena, V>>; +impl_kind!(Face, init: (); outer, inner); +impl_kind_debug!(Face); + +impl<'brand, 'arena, V: Default> Dcel<'brand, 'arena, V> { + fn new(token: GhostToken<'brand>, alloc: &'arena DcelAllocator<'brand, 'arena, V>) -> Self { + Self { + token, + half_edges: Container::new(&alloc.edge), + vertices: Container::new(&alloc.vertex), + faces: Container::new(&alloc.face), + } + } + + pub fn mvsf(&mut self, data: V) -> (cell!(Vertex), cell!(Face)) { + let f = self.faces.alloc(&mut self.token, ()); + let v = self.vertices.alloc(&mut self.token, data); + + (v, f) + } + + pub fn mevvls(&mut self, data: [V; 2]) -> (cell!(HalfEdge), [cell!(Vertex); 2], cell!(Face)) { + let [d1, d2] = data; + + let l = self.faces.alloc(&mut self.token, ()); + let v1 = self.vertices.alloc(&mut self.token, d1); + let v2 = self.vertices.alloc(&mut self.token, d2); + let a = self.half_edges.alloc(&mut self.token, ()); + let b = self.half_edges.alloc(&mut self.token, ()); + + self.twin(a, b); + self.follow(a, b); + self.follow(b, a); + self.origin(v1, a); + self.origin(v2, b); + + (a, [v1, v2], l) + } + + #[inline(always)] + fn twin(&mut self, a: cell!(HalfEdge), b: cell!(HalfEdge)) { + a.borrow_mut(&mut self.token).twin = Some(b); + b.borrow_mut(&mut self.token).twin = Some(a); + } + + #[inline(always)] + fn origin(&mut self, v: cell!(Vertex), h: cell!(HalfEdge)) { + v.borrow_mut(&mut self.token).outgoing = Some(h); + h.borrow_mut(&mut self.token).origin = Some(v); + } + + #[inline(always)] + fn follow(&mut self, prev: cell!(HalfEdge), next: cell!(HalfEdge)) { + next.borrow_mut(&mut self.token).prev = Some(prev); + prev.borrow_mut(&mut self.token).next = Some(next); + } + + pub fn mve( + &mut self, + edge: cell!(HalfEdge), + data: V, + ) -> Option<(cell!(HalfEdge), cell!(Vertex))> { + // before: + // + // fa + // / a3 + // a1 -> + // v1 v v2 + // <- b1 + // \ b3 + // fb + // + // after: + // + // fa + // / a3 + // a1 -> a2 -> + // v1 v v2 + // <- b1 <- b2 + // \ b3 + // fb + + let v = self.vertices.alloc(&mut self.token, data); + let a2 = self.half_edges.alloc(&mut self.token, ()); + let b2 = self.half_edges.alloc(&mut self.token, ()); + + let a1 = edge; + let v1 = a1.borrow(&self.token).origin?; + //let fa = a1.borrow(&self.token).face?; + + let b1 = a1.borrow(&self.token).twin?; + let v2 = b1.borrow(&self.token).origin?; + //let fb = b1.borrow(&self.token).face?; + + let mut a3 = a1.borrow(&self.token).next?; + if a3.borrow(&self.token) == b1.borrow(&self.token) { + a3 = b2; + } + + let mut b3 = b1.borrow(&self.token).prev?; + if b3.borrow(&self.token) == a1.borrow(&self.token) { + b3 = a2; + } + + self.twin(a2, b2); + + self.origin(v, a2); + self.origin(v, b1); + self.origin(v2, b2); + + self.follow(a1, a2); + self.follow(a2, a3); + + self.follow(b3, b2); + self.follow(b2, b1); + + Some((a1, v)) + } + + pub fn mel(&mut self, v1: cell!(Vertex), v2: cell!(Vertex)) -> Option<()> { + Some(()) + } + + fn mev( + &mut self, + from: cell!(Vertex), + data: V, + ) -> (cell!(Vertex), cell!(HalfEdge), cell!(HalfEdge)) { + let v = self.vertices.alloc(&mut self.token, data); + let a = self.half_edges.alloc(&mut self.token, ()); + let b = self.half_edges.alloc(&mut self.token, ()); + + self.twin(a, b); + + self.origin(v, a); + self.origin(from, b); + + self.follow(a, b); + self.follow(b, a); + + (v, a, b) + } +} + +struct DcelDotOptions { + pub twin: bool, + pub next: bool, + pub prev: bool, +} + +impl DcelDotOptions { + fn none() -> Self { + Self { + twin: false, + next: false, + prev: false, + } + } + + fn all() -> Self { + Self { + twin: true, + next: true, + prev: true, + } + } +} + +fn dcel_write_dot( + dcel: &Dcel<(&'static str, [i64; 2])>, + f: &mut fmt::Formatter<'_>, + opt: DcelDotOptions, +) -> fmt::Result { + use rand::Rng; + use std::collections::HashSet; + + writeln!(f, "digraph DCEL {{")?; + writeln!(f, "node [shape = circle]")?; + //writeln!(f, "nodesep = 1")?; + + let mut rank = Vec::new(); + + for v in dcel.vertices.elements.iter() { + let v = v.borrow(&dcel.token); + if let Some(id) = v.id { + // writeln!(f, "\t{id} [pos=\"{},{}!\"]", v.data.0, v.data.1)?; + writeln!( + f, + "{id} [label=\"{}\", pos=\"{},{}!\"]", + v.data.0, v.data.1[0], v.data.1[1] + ); + rank.push(id); + } + } + + /* + write!(f, "{{ rank=same; ")?; + for r in rank { + write!(f, "{r}; ")?; + } + writeln!(f, "}}");*/ + + for h in dcel.half_edges.elements.iter() { + let h = h.borrow(&dcel.token); + if let Some(id) = h.id { + let twin = h.twin.unwrap().borrow(&dcel.token); + let twin_id = twin.id.unwrap(); + + let a_v = h.origin.unwrap().borrow(&dcel.token); + let b_v = twin.origin.unwrap().borrow(&dcel.token); + + let mut vec = [ + -(b_v.data.1[1] - a_v.data.1[1]) as f64, + (b_v.data.1[0] - a_v.data.1[0]) as f64, + ]; + + let len = (vec[0] * vec[0] + vec[1] * vec[1]).sqrt(); + vec[0] *= 0.2 / len; + vec[1] *= 0.2 / len; + + let mid = [ + (a_v.data.1[0] + b_v.data.1[0]) as f64 / 2.0 + vec[0], + (a_v.data.1[1] + b_v.data.1[1]) as f64 / 2.0 + vec[1], + ]; + + let a = a_v.id.unwrap(); + let b = b_v.id.unwrap(); + + writeln!( + f, + "edge_{id} [pos=\"{},{}!\", shape=point, width=0.01, height=0.01]", + mid[0], mid[1] + )?; + writeln!(f, "{a} -> edge_{id} [arrowhead=none]")?; + writeln!(f, "edge_{id} -> {b} [label=\"{id}\"]")?; + + if opt.twin { + writeln!(f, "edge_{id} -> edge_{twin_id} [color=\"red\"]")?; + } + + if opt.next { + writeln!( + f, + "edge_{id} -> edge_{} [color=\"green\"]", + h.next.unwrap().borrow(&dcel.token).id.unwrap() + )?; + } + + if opt.prev { + writeln!( + f, + "edge_{id} -> edge_{} [color=\"blue\"]", + h.prev.unwrap().borrow(&dcel.token).id.unwrap() + )?; + } + } + } + + writeln!(f, "}}") +} + +impl_debug!(i32); + +struct DisplayFn(T); +impl) -> fmt::Result> fmt::Display for DisplayFn { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + self.0(f) + } +} + +fn main() { + GhostToken::new(|token| { + let alloc = DcelAllocator::default(); + let mut dcel = Dcel::new(token, &alloc); + + let h0 = dcel.mevvls([("S", [0, 0]), ("E", [9, 0])]).0; + let h2 = dcel.mve(h0, ("P1", [6, 0])).unwrap().0; + dcel.mve(h2, ("P2", [3, 0])).unwrap(); + + dcel.mev(h0.borrow(&dcel.token).origin.unwrap(), ("B", [0, 3])); + + print!( + "{}", + DisplayFn(|f: &mut fmt::Formatter<'_>| dcel_write_dot( + &dcel, + f, + DcelDotOptions { + prev: false, + next: true, + twin: false, + } + )) + ); + + /* + print!( + "{}", + DisplayFn(|f: &mut fmt::Formatter<'_>| { + for v in dcel.vertices.elements.iter() { + DcelDebug::fmt(v, true, &dcel.token, f)?; + } + + for h in dcel.half_edges.elements.iter() { + DcelDebug::fmt(h, true, &dcel.token, f)?; + } + + Ok(()) + }) + );*/ + }); +} diff --git a/utahteapot/LICENSE.txt b/utahteapot/LICENSE.txt new file mode 100644 index 0000000..7421e49 --- /dev/null +++ b/utahteapot/LICENSE.txt @@ -0,0 +1 @@ +This thing was created by Thingiverse user zzubnik, and is licensed under Creative Commons - Public Domain Dedication \ No newline at end of file diff --git a/utahteapot/README.txt b/utahteapot/README.txt new file mode 100644 index 0000000..19d4877 --- /dev/null +++ b/utahteapot/README.txt @@ -0,0 +1 @@ +Utah teapot (solid) by zzubnik on Thingiverse: https://www.thingiverse.com/thing:852078 \ No newline at end of file diff --git a/utahteapot/files/utahteapot.stl b/utahteapot/files/utahteapot.stl new file mode 100644 index 0000000..d225918 Binary files /dev/null and b/utahteapot/files/utahteapot.stl differ diff --git a/utahteapot/images/teapot_stl.jpg b/utahteapot/images/teapot_stl.jpg new file mode 100644 index 0000000..1d091f1 Binary files /dev/null and b/utahteapot/images/teapot_stl.jpg differ diff --git a/utahteapot/images/utahteapot.png b/utahteapot/images/utahteapot.png new file mode 100644 index 0000000..ae8f786 Binary files /dev/null and b/utahteapot/images/utahteapot.png differ diff --git a/x.dot b/x.dot new file mode 100644 index 0000000..77dea66 --- /dev/null +++ b/x.dot @@ -0,0 +1,40 @@ +digraph DCEL { +node [shape = circle] +0 [label="S", pos="0,0!"] +1 [label="E", pos="9,0!"] +2 [label="P1", pos="6,0!"] +3 [label="P2", pos="3,0!"] +4 [label="B", pos="0,3!"] +edge_0 [pos="1.5,0.2!", shape=point, width=0.01, height=0.01] +0 -> edge_0 [arrowhead=none] +edge_0 -> 3 [label="0"] +edge_0 -> edge_4 [color="green"] +edge_1 [pos="1.5,-0.2!", shape=point, width=0.01, height=0.01] +3 -> edge_1 [arrowhead=none] +edge_1 -> 0 [label="1"] +edge_1 -> edge_0 [color="green"] +edge_2 [pos="7.5,0.2!", shape=point, width=0.01, height=0.01] +2 -> edge_2 [arrowhead=none] +edge_2 -> 1 [label="2"] +edge_2 -> edge_3 [color="green"] +edge_3 [pos="7.5,-0.2!", shape=point, width=0.01, height=0.01] +1 -> edge_3 [arrowhead=none] +edge_3 -> 2 [label="3"] +edge_3 -> edge_5 [color="green"] +edge_4 [pos="4.5,0.2!", shape=point, width=0.01, height=0.01] +3 -> edge_4 [arrowhead=none] +edge_4 -> 2 [label="4"] +edge_4 -> edge_2 [color="green"] +edge_5 [pos="4.5,-0.2!", shape=point, width=0.01, height=0.01] +2 -> edge_5 [arrowhead=none] +edge_5 -> 3 [label="5"] +edge_5 -> edge_1 [color="green"] +edge_6 [pos="0.2,1.5!", shape=point, width=0.01, height=0.01] +4 -> edge_6 [arrowhead=none] +edge_6 -> 0 [label="6"] +edge_6 -> edge_7 [color="green"] +edge_7 [pos="-0.2,1.5!", shape=point, width=0.01, height=0.01] +0 -> edge_7 [arrowhead=none] +edge_7 -> 4 [label="7"] +edge_7 -> edge_6 [color="green"] +} diff --git a/x.svg b/x.svg new file mode 100644 index 0000000..16f61db --- /dev/null +++ b/x.svg @@ -0,0 +1,227 @@ + + + + + + +DCEL + + + +0 + +S + + + +edge_0 + + + + +0->edge_0 + + + + +edge_7 + + + + +0->edge_7 + + + + +1 + +E + + + +edge_3 + + + + +1->edge_3 + + + + +2 + +P1 + + + +edge_2 + + + + +2->edge_2 + + + + +edge_5 + + + + +2->edge_5 + + + + +3 + +P2 + + + +edge_4 + + + + +3->edge_4 + + + + +edge_1 + + + + +3->edge_1 + + + + +4 + +B + + + +edge_6 + + + + +4->edge_6 + + + + +edge_0->3 + + +0 + + + +edge_0->edge_4 + + + + + +edge_4->2 + + +4 + + + +edge_4->edge_2 + + + + + +edge_1->0 + + +1 + + + +edge_1->edge_0 + + + + + +edge_2->1 + + +2 + + + +edge_2->edge_3 + + + + + +edge_3->2 + + +3 + + + +edge_3->edge_5 + + + + + +edge_5->3 + + +5 + + + +edge_5->edge_1 + + + + + +edge_6->0 + + +6 + + + +edge_6->edge_7 + + + + + +edge_7->4 + + +7 + + + +edge_7->edge_6 + + + + + -- cgit v1.2.3