एल्गोरिदम स्वयं-छेड़छाड़ किए गए पथ 2 डी को अलग-अलग आत्म-अंतर वाले पथों में विभाजित करने के लिए नहीं?

Question

मुझे एक आकार में आत्म-चौराहे से छुटकारा पाने की आवश्यकता है। आकार बिंदुओं की एक सरणी से बनाया गया है, इसलिए उस आकार के सभी खंड रेखाएं हैं। (केवल लाइनों, नहीं घटता और आर्क्स)

इससे पहले, मैं से कि अंक, इसमें से एक क्षेत्र का निर्माण, और फिर मैं कई Path2Ds, जो किसी भी तरह पिछले की उपपथ थे बनाई गई अपनी PathIterator का उपयोग कर Path2D बनाने की कोशिश की पथ, और इसलिए आत्म-घुसपैठ चले गए थे। लेकिन यह कुछ पथों के लिए काम नहीं कर रहा है - आत्म-चौराहे अभी भी वहां रहती है।

तो क्या आप मुझे किसी ऐसे स्थान पर इंगित कर सकते हैं जहां मुझे समान काम करने के लिए अच्छा एल्गोरिदम मिल सकता है?

संपादित करें: मुझे कहीं भी कुछ भी उपयोगी नहीं मिला है, इसलिए मैंने अपना स्वयं का एल्गोरिदम लिखा है। जवाब देखें।

Answer 1

तो Area आप के लिए काम नहीं कर रहा है, तो आप अपने Shape त्रिकोण, या (GL_LINE_LOOP विकल्प का उपयोग) के एक सेट में सिर्फ सीमा किनारों विघटित करने के लिए एक GLUtessellator उपयोग करने का प्रयास कर सकता है।

Answer 2

इसलिए, चूंकि मैं वेब पर ऐसा कुछ नहीं ढूंढ पाया, इसलिए मैंने अपना स्वयं का एल्गोरिदम लिखा।

यह बेहद अप्रभावी हो सकता है, लेकिन यह मेरे लिए पर्याप्त तेज़ काम करता है।

यहाँ यह जाता है:

/** 
* Takes a polygon, defined by a list of lines, and splits it into several 
* paths on points of intersection. If non-self-intersected path is passed in, 
* the same path is returned. 
* @param path 
* @return 
*/ 
public static List<List<Line2D>> splitPath(List<Line2D> lines) { 
    List<List<Line2D>> splitted = new ArrayList<List<Line2D>>(); 
    // find intersections. 
    loop1: 
    for (Line2D l1 : lines) { 
     for (Line2D l2 : lines) { 
      if (l1 == l2) continue; 
      Point2D intr; 
      if ((intr = linesIntersect(l1, l2)) != null) { 
       // creating two splitted subpaths 
       int i1 = lines.indexOf(l1); 
       int i2 = lines.indexOf(l2); 

       List<Line2D> subpath1 = new ArrayList<Line2D>(); 
       subpath1.addAll(lines.subList(0, i1)); 
       subpath1.add(new Line2D.Double(l1.getP1(), intr)); 
       subpath1.add(new Line2D.Double(intr, l2.getP2())); 
       subpath1.addAll(lines.subList(i2 + 1, lines.size())); 
       splitted.addAll(splitPath(subpath1)); 

       List<Line2D> subpath2 = new ArrayList<Line2D>(); 
       subpath2.add(new Line2D.Double(intr, l1.getP2())); 
       subpath2.addAll(lines.subList(i1 + 1, i2)); 
       subpath2.add(new Line2D.Double(l2.getP1(), intr)); 
       splitted.addAll(splitPath(subpath2)); 
       break loop1; 
      } 
     } 
    } 
    if (splitted.size() > 0) { 
     return splitted; 
    } else { 
     return Collections.singletonList(lines); 
    } 
} 

/** 
* Returns point of intersection of this line segments. 
* @param l1 
* @param l2 
* @return 
*/ 
public static Point2D linesIntersect(Line2D l1, Line2D l2) { 
    if (l1.getP1().equals(l2.getP2()) || l1.getP2().equals(l2.getP1())) return null; 
    Point2D inter = lineIntersection(l1, l2); 
    if (inter == null) return null; 
    double infS = HEADER.infS; 
    double x = inter.getX(); 
    if (((l1.getX1() > l1.getX2()) ? (x + infS > l1.getX2() && x - infS < l1.getX1()) : (x - infS < l1.getX2() && x + infS > l1.getX1())) && 
      ((l2.getX1() > l2.getX2()) ? (x + infS > l2.getX2() && x - infS < l2.getX1()) : (x - infS < l2.getX2() && x + infS > l2.getX1()))) { 
     return inter; 
    } else { 
     return null; 
    } 
} 

/** 
* Returns point of lines intersection, or null if they are parallel. 
* @param l1 
* @param l2 
* @return 
*/ 
public static Point2D lineIntersection(Line2D l1, Line2D l2) { 
    double a1 = l1.getY2() - l1.getY1(); 
    double b1 = l1.getX1() - l1.getX2(); 
    double c1 = a1*l1.getX1() + b1*l1.getY1(); 
    double a2 = l2.getY2() - l2.getY1(); 
    double b2 = l2.getX1() - l2.getX2(); 
    double c2 = a2*l2.getX1() + b2*l2.getY1(); 
    double det = a1*b2 - a2*b1; 
    if (det != 0) { 
     double x = (b2*c1 - b1*c2)/det; 
     double y = (a1*c2 - a2*c1)/det; 
     return new Point2D.Double(x, y); 
    } else { 
     // lines are parallel 
     return null; 
    } 
} 

Answer 3

मैं अपने प्रश्न/उत्तर मामले में मैं कुछ इसी तरह अपने आप को लागू करने के लिए किया था बुकमार्क किए गए, लेकिन फिर मैं GEOS परियोजना जो इस को प्राप्त करने का एक आसान तरीका है पाया। मैं पाइथन/डीजेगो से जीईओएस को बुला रहा हूं, लेकिन पूरी बात JTS (Java Topology Suite) पर आधारित है, इसलिए मैं वहां से शुरू करूंगा और निम्नलिखित पायथन को psuedo-code के रूप में मानूंगा।

असल में, यूनिअन आपरेशन बस जुड़े भागों में एक पंक्ति विभाजित करेगा कि क्या यह बस जुड़ा हुआ नहीं है (here समझाया गया है), इसलिए लाइन UNIONing साथ यह पहली बात है करता है कि हम क्या जरूरत है:

line = LineString(list_of_lines_x_y_coordinates) 
# union with first point splits into MultiLineString containing segments 
segments = line.union(line[0])