Polygon and MultiPolygon support?

[Dexus]

Hello, is there anything in the works? Unfortunately it's not implemented yet.

Would love to help, but rust is currently in the early stages for me. Would be very helpful if things could move forward here.

Many thanks & regards

[JeroenGar]

Hello,

I do not have time to implement this right now, but plan to do so in the future.
I already have a pretty good idea how to implement support for both:

Support for polygons with holes can be added relatively easily by converting them in preprocessing to simple polygons.
You can achieve this by connecting each hole to the outer boundary with a degenerate edge.
Similar to what is described here: https://en.wikipedia.org/wiki/Polygon_with_holes#Conversion_to_ordinary_polygon

For MultiPolygons, the partial polygons can simply be individually queried/registered by the CDE. An additional preprocessing step could be to merge polygons that are "touching", again by adding a degenerate edge.

[Dexus]

Would be nice to have then, a new propperty Name/Filename for the Items, that are also given out on the result. Only for the safty definition, I have sometimes the problem that the index is not the correct one form the input, when I try to work with 2 Apps that read the result, because the JSON is maybe parsed different. I need to check that.

[Dexus]

I have played around with it in Javascript and then asked the ChatGPT if he can Translate me the code to Rust:

JS: https://jsfiddle.net/zwg83qje/

use std::f64;

type Point = (f64, f64);

/// Berechnet die Fläche eines Polygons, um die Laufrichtung zu bestimmen.
fn calculate_polygon_area(points: &Vec<Point>) -> f64 {
    let mut area = 0.0;
    for i in 0..points.len() - 1 {
        let (x1, y1) = points[i];
        let (x2, y2) = points[i + 1];
        area += x1 * y2 - x2 * y1;
    }
    area / 2.0
}

/// Dreht die Punkte eines Polygons um.
fn reverse_polygon(points: &mut Vec<Point>) {
    points.reverse();
}

/// Berechnet einen Punkt auf einer Linie mit minimaler Trennung.
fn interpolate_point(p1: Point, p2: Point, t: f64) -> Point {
    (p1.0 + t * (p2.0 - p1.0), p1.1 + t * (p2.1 - p1.1))
}

/// Berechnet die Distanz zwischen zwei Punkten.
fn distance(p1: Point, p2: Point) -> f64 {
    ((p1.0 - p2.0).powi(2) + (p1.1 - p2.1).powi(2)).sqrt()
}

/// Verknüpft ein Loch mit der äußeren Umrandung eines Polygons.
fn connect_hole_to_outer(
    mut outer_ring: Vec<Point>,
    mut hole: Vec<Point>,
    separation: f64,
) -> Vec<Point> {
    // Sicherstellen, dass die Laufrichtungen korrekt sind
    if calculate_polygon_area(&outer_ring) < 0.0 {
        reverse_polygon(&mut outer_ring); // Äußere Umrandung CCW
    }
    if calculate_polygon_area(&hole) > 0.0 {
        reverse_polygon(&mut hole); // Loch CW
    }

    let mut min_distance = f64::INFINITY;
    let mut closest_outer_point = (0.0, 0.0);
    let mut closest_hole_point = (0.0, 0.0);
    let mut outer_index = 0;

    // Finde die engsten Punkte zwischen Loch und äußerem Ring
    for (i, &outer_point) in outer_ring.iter().enumerate() {
        for &hole_point in &hole {
            let dist = distance(outer_point, hole_point);
            if dist < min_distance {
                min_distance = dist;
                closest_outer_point = outer_point;
                closest_hole_point = hole_point;
                outer_index = i;
            }
        }
    }

    // Erstelle zwei Verbindungspunkte mit minimalem Abstand
    let next_outer_point = outer_ring[(outer_index + 1) % outer_ring.len()];
    let connection_point1 = interpolate_point(closest_outer_point, next_outer_point, separation);
    let connection_point2 = interpolate_point(closest_outer_point, next_outer_point, -separation);

    // Neues Polygon durch Hinzufügen der Verbindungspunkte erstellen
    let mut updated_polygon = vec![];
    updated_polygon.extend(&outer_ring[..=outer_index]); // Äußere Punkte bis zur Verbindung
    updated_polygon.push(connection_point1); // Erster Verbindungspunkt
    updated_polygon.push(closest_hole_point); // Punkt vom Loch
    updated_polygon.extend(hole); // Punkte des Lochs
    updated_polygon.push(closest_hole_point); // Zurück zum Punkt vom Loch
    updated_polygon.push(connection_point2); // Zweiter Verbindungspunkt
    updated_polygon.extend(&outer_ring[outer_index + 1..]); // Rest des äußeren Rings

    updated_polygon
}

/// Konvertiert Punkte in eine Path-Syntax (SVG-kompatibel).
fn points_to_path(points: &Vec<Point>) -> String {
    points
        .iter()
        .map(|&(x, y)| format!("{:.6},{:.6}", x, y))
        .collect::<Vec<_>>()
        .join(" ")
}

fn main() {
    // Beispiel: Äußerer Ring und Loch
    let outer_ring = vec![
        (10.0, 10.0),
        (90.0, 10.0),
        (90.0, 90.0),
        (10.0, 90.0),
        (10.0, 10.0),
    ];
    let hole = vec![
        (40.0, 40.0),
        (60.0, 40.0),
        (60.0, 60.0),
        (40.0, 60.0),
        (40.0, 40.0),
    ];

    // Konvertiere in ein einfaches Polygon
    let simple_polygon = connect_hole_to_outer(outer_ring, hole, 1e-8);

    // Ausgabe als SVG-Pfad
    let path_data = points_to_path(&simple_polygon);
    println!("<path d=\"M {} Z\" fill=\"blue\" stroke=\"black\" stroke-width=\"0.5\" />", path_data);
}

}

Would this work like this?

[JeroenGar]

Consider the following multi polygon, with each of its points marked with a letter:

Initially the points of the outer polygon are ordered as: [A,B,C,D].
While the inner is [E,F,G,H].

The resulting converted simple polygon should have the following order of edges: [A, E, G, H, F, E, A, B, C, D]
Both polygons are connected to each other with a degenerate edge: A->E & E->A (2 edges).
This ensures the inside of the inner polygon will be seen as exterior.

I do not think your example code produces this ordering of edges? (not sure though).

One caveat is that you also need to ensure the set of "connecting edges" do not cross any of the existing edges in the shape (self-intersections are not allowed).

Hopefully this made it a bit more clear.