Penyederhanaan Poligon Lossless?

8

Apakah ada algoritma standar / yang direkomendasikan untuk menyederhanakan poligon tanpa mengecilkan batas aslinya?

Saat ini saya menggunakan TopologyPreservingSimplifer dalam JTS dan mengalami masalah di aplikasi saya ketika saya menemukan poligon "lossy". Idealnya, saya ingin memproduksi poligon yang disederhanakan yang lebih kecil dari lambung cembung tetapi tetap menjadi superset dari poligon asli saya.

disederhanakan

Memperbarui:

Saya akhirnya menemukan algoritma yang diakui tidak sempurna yang menempatkan "wrapper" di sekitar poligon input, menyusutnya hingga tidak ada area berlebih yang melebihi persentase dari total area input, kemudian menjalankan penyederhanaan garis dengan ambang batas yang jauh lebih halus untuk dilepas setiap titik redundan sepanjang garis lurus. 100% tergantung data, tapi saya melihat 80% kompresi vertex dengan area kelebihan minimal. Semua umpan balik / komentar dihargai:

public class LosslessPolygonSimplifier {
protected final static Logger logger = Logger.getLogger(LosslessPolygonSimplifier.class.getName());

public static Polygon simplify(Polygon input) {
    final double AREA_THRESHOLD = 0.005; // allow excesses up to half a percent of total original area
    final double LINE_THRESHOLD = 0.0001; // fine threshold to strip straight lines
    try {
        if (!input.isSimple()) {
            logger.warning("Attempting to simplify complex polygon!");
        }
        Polygon simple = simplifyInternal(input, AREA_THRESHOLD, LINE_THRESHOLD);
        return simple;
    }
    catch (Exception e) {
        logger.log(Level.WARNING, "Failed to simplify. Resorting to convex hull.\n " + input.toText(), e);
        try {
            // worst case scenario - fall back to convex hull
            // probably a result of a bow-tie LINESTRING that doubles back on itself due to precision loss?
            return (Polygon) input.convexHull();
        }
        catch (Exception e2) {
            // Is this even possible? Polygons that cross the anti-meridian?
            logger.log(Level.SEVERE, "Failed to simplify to convex hull: " + input.toText(), e2);
            return input; // Garbage In, Garbage Out
        }
    }
}

// TODO avoid creating triangles on long straight edges
public static Polygon simplifyInternal(Polygon original, double areaThreshold, double lineThreshold) {
    GeometryFactory gf = new GeometryFactory();
    Geometry excesses, excess, keepTotal, keepA, keepB, chA, chB, keep = null, elim = null;
    Polygon simplified = null, wrapper = (Polygon) original.convexHull();
    try {
        boolean done = false;
        while (!done) {
            done = true;
            excesses = wrapper.difference(original);
            for (int i = 0; i < excesses.getNumGeometries(); i++) {
                excess = excesses.getGeometryN(i);
                if (excess.getArea() / original.getArea() > areaThreshold) {
                    done = false; // excess too big - try to split then shrink
                    keepTotal = excess.intersection(original);
                    keepA = gf.createGeometryCollection(null);
                    keepB = gf.createGeometryCollection(null);
                    for (int j = 0; j < keepTotal.getNumGeometries(); j++) {
                        if (j < keepTotal.getNumGeometries() / 2) {
                            keepA = keepA.union(keepTotal.getGeometryN(j));
                        }
                        else {
                            keepB = keepB.union(keepTotal.getGeometryN(j));
                        }
                    }
                    chA = keepA.convexHull();
                    chB = keepB.convexHull();
                    keep = gf.createMultiPolygon(null);
                    if (chA instanceof Polygon) {
                        keep = keep.union(chA);
                    }
                    if (chB instanceof Polygon) {
                        keep = keep.union(chB);
                    }
                    elim = excess.difference(keep);
                    wrapper = (Polygon) wrapper.difference(elim);
                }
            }
        }
        new Assert(wrapper.getArea() >= original.getArea());
        new Assert(wrapper.getArea() <= original.convexHull().getArea());
        simplified = (Polygon) com.vividsolutions.jts.simplify.TopologyPreservingSimplifier.simplify(wrapper, lineThreshold);
        new Assert(simplified.getNumPoints() <= original.getNumPoints());
        new Assert(simplified.getNumInteriorRing() == 0);
        new Assert(simplified.isSimple());
        return simplified;
    }
    catch (Exception e) {
        if (original.isSimple()) {
            StringBuilder sb = new StringBuilder();
            sb.append("Failed to simplify non-complex polygon!");
            sb.append("\noriginal: " + original.toText());
            sb.append("\nwrapper: " + (null == wrapper ? "" : wrapper.toText()));
            sb.append("\nsimplified: " + (null == simplified ? "" : simplified.toText()));
            sb.append("\nkeep: " + (null == keep ? "" : keep.toText()));
            sb.append("\nelim: " + (null == elim ? "" : elim.toText()));
            logger.log(Level.SEVERE, sb.toString());
        }
        throw e;
    }
}

}

pengguna1538028
sumber
5
1. Mengapa Anda menyebutnya penyederhanaan tanpa kerugian? Saya pikir jika Anda menyederhanakan batas, Anda kehilangan detail. 2. Anda dapat menyederhanakan batas dan memiliki area tanpa kerugian , tetapi itu akan mematahkan kriteria Anda untuk tidak menyusut batas. 3. Mengapa Anda ingin mengizinkan batas untuk diperluas dan tidak menyusut? Atau apakah saya salah mengerti sesuatu?
Martin F
1
Data saya mewakili batas politik. Saya baik-baik saja dengan ekstensi kecil dari area asli jika membantu menurunkan jumlah titik. Saya ingin menghindari pemusnahan orang dari daerah asli. Benar, saya tertarik pada penyederhanaan area lossless .
user1538028

Jawaban:

6

Anda bisa saja menyatu dengan poligon asli setelah penyederhanaan.

flitmonkey
sumber
1
Meskipun ini berhasil, mungkin lebih buruk daripada poligon aslinya!
whuber
Bisakah ini lebih buruk? Saya tidak dapat memikirkan contoh yang lebih buruk - tebak bahwa mungkin ada satu contoh. Secara umum meskipun itu akan menjadi penyederhanaan yang dibatasi oleh lambung cembung.
flitmonkey
1
Itu tergantung pada algoritma yang digunakan oleh "penyederhanaan topologi." Beberapa penyederhanaan mungkin tidak mempertahankan simpul mana pun di sepanjang busur, sehingga penyatuan versi yang disederhanakan dengan yang asli tentu akan memiliki lebih banyak simpul daripada yang asli. Dengan demikian, untuk mengetahui apakah rekomendasi Anda bermanfaat atau sebaliknya, orang perlu memahami detail penyederhanaan.
whuber
4
Ini mungkin jawaban yang bagus untuk pertanyaan "tepat" yang diajukan, tetapi saya tidak yakin pertanyaan yang tepat diajukan atau karena alasan yang tepat.
Martin F
1

Jika TopologyPreservingSimplifer didasarkan pada algoritma Douglas-Peucker, seperti yang dikatakan di vividsolutions (pencipta JTS), ia umumnya tidak akan mengubah area poligon. Namun, setiap poligon harus menghasilkan urutan untung dan rugi kecil (menyeimbangkan keseluruhan).

Jika Anda berfokus pada satu poligon, atau sekelompok kecil poligon, dan Anda membiarkannya berkembang tetapi tidak menyusut (dengan mengorbankan tetangga mereka) maka Anda memasukkan bias ke dalam analisis Anda.

tambahan

Jadi, saya percaya pilihan awal Anda, TopologyPreservingSimplifer, adalah solusi yang tepat.

Martin F
sumber
Ini adalah komentar yang bagus - tetapi mereka membaca komentar seperti bukan jawaban atas pertanyaan. Jika Anda mungkin mencoba (agak hati-hati) untuk mengusulkan Douglas-Peucker sebagai solusinya, harap pertimbangkan untuk membuat rekomendasi itu sedikit lebih jelas.
whuber
1
@whuber, saya pasti tidak berusaha untuk berhati-hati dan menambahkan kesimpulan sesuai saran Anda - bahkan setelah pembaruan OP yang tidak menambah pemahaman saya tentang masalah atau alasan.
Martin F